Page 431 - 《软件学报》2024年第6期

徐兰天 等: 面向超图数据的最大独立集算法 3007

为 1 的邻接超边删除. 此时, 图中仅剩余一条由超点 0 和超点 9 组成的超边, 且已经没有度大于 1 的超点. 此时可
任取超点 0 和超点 9 中的一个加入 H. 算法结束, 最终得到的近似超图最大独立集为{2, 4, 6, 0}或{2, 4, 6, 9}.

2
1 3

4
6
8
5
7

0
改进算法最后需要遍历所有剩余超边, 最坏情况下会遍历

9
图 8 改进算法执行流程

7 算法分析

对于基础算法, 算法需要枚举所有 INITIAL 状态的超点, 并遍历修改他们邻接点的状态. 枚举所有 INITIAL 状
态的超点时, 前面被枚举的超点可能会影响后面超点的状态, 实际上这一步的枚举次数是少于 n 的. 而对于超图中
的一个 INITIAL 状态的超点 v, 他的平均邻接点的数量为 D×S. 则在最坏情况下, 算法 1 的时间复杂度不超过
O(n×D×S).
对于改进算法, 该算法需要计算按超点度的降序序列, 这一步的时间复杂度为 O(nlog 2 n). 然后算法执行 one-
degree 点剪枝, 需要遍历所有的度为 1 的超点, 并删除该超点所在的超边, 及边上的所有点. 则对于每个度为 1 的
超点, 它所在的超边的大小平均为 S, 对于边上的每个超点, 要遍历平均 D 条邻接边, 并遍历这些邻接边, 从中删除
相关的超点还需要再遍历 S 次. 则 one-degree 点剪枝最终的最坏时间复杂度为 O(n degree=1 ×D×S ).
2
接下来, 考虑对于 high-degree 超点的剪枝, 剪枝 2 与剪枝 3 和剪枝 4 是一个相辅相成的组合体. 对于两种 one-
size 边剪枝, 需要删除高度超点的邻接边中 size 为 1 的边, 对于每个高度超点, 删除邻接边最多需要查找 D 次. 而
对于 high-degree 近似点剪枝, 需要遍历高度点的平均 D 条超边, 并从每条平均长度为 S 的超边中删除高度点, 需
要的时间复杂度为 O(D×S). 由于精确剪枝的复杂度低于近似剪枝, 则在对于整个 high-degree 超点的剪枝过程, 最
坏时间复杂度为 O(n degree>1 ×D×S).
m 次. 则对于整个算法的时间复杂度为 O(nlog 2 n+
2
n degree=1 ×D×S +n degree>1 ×D×S).
在空间复杂度方面, 基础算法和改进算法的空间复杂度区别不大, 两者都是用 ICSF 存图, ICSF 空间大小为
O(n×D+m×S). 与基础算法相比, 改进算法只是多了一个维护 degree 排序的序列, 因此改进算法空间复杂度为

O(n×D+m×S+n).
8 实验分析

本节进行大量实验来证明改进的超图近似最大独立集算法的有效性. 本章实验环境硬件为 Intel(R) Xeon(R)
Gold5218R CPU@2.10 GHz, 内存为 96 GB, 硬盘为 500 GB, 操作系统为 Ubuntu 9.4.0, 开发软件为 g++, 开发语言