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

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

局部搜索 [26] 和禁忌搜索 [27−29] 等. 贪婪算法按一定的顺序逐次扩充解的集合, 直至顺序搜索结束, 最终获得一个可
行解. Liu 等人 [30] 提出了逐步地添加最小度数的顶点到最大独立集中的解决方案. Lamm 等人 [31] 提出了优先选择
更可能加入最大独立集的点的进化算法. 局部搜索对可行解的局部邻域进行搜索, 来提高已知解的质量. Andrade
等人 [32] 提出的局部搜索算法, 用已获得的独立集中的点与非独立集点交换来扩展最大独立集大小. Dahlum 等人 [33]
提出了局部搜索与进化规则相结合的算法. 禁忌搜索是一种改进的局部搜索算法, 通过设立“禁忌列表”来避免循
环搜索, 可以快速跳出循环并搜索新的区域. Gao 等人 [34] 提出了在动态图上维护最大独立集的近似算法, Liu 等人 [35]
基于 Pay-and-Recycle 模型, 提出了包含指定点集的类最大独立集算法. 此外, 在前人的研究中, 还提出了许多有效
的剪枝规则, 如折叠和镜像规则, 二度路径剪枝规则等 [36,37] . 这些剪枝策略有助于在不牺牲解决方案质量的情况下
减少问题的规模.
然而, 目前国内外还没有出现如本文定义的超图最大独立集的搜索算法, 这也说明本文的研究是十分有意义的.
2 基础知识

假如 G=(V, E) 是一个超图, V(|V|=n) 表示图 G 对应的点集, E(|E|=m) 表示图 G 对应的边集.
xadj、adjncy、eptr、eind
定义 1. 超图独立集和最大独立集. 超图独立集 S 是超图 G 中的一个超点子集, 使得超图独立集 S 中的任意两
个不同的超点都不能被超图 G 中的同一超边所包含. 如果一个超图独立集的点数是图 G 中最多的, 则称为超图
G 的一个最大超图独立集. 用 α(G) 表示超图 G 最大独立集中的超点个数.
如图 1 所示, 图中有 3 条超边, 超边 a 包含点 0, 1, 2; 超边 b 包含点 2 和 3; 超边 c 包含点 0 和 3. 根据本文超
图独立集定义, 图中共有 5 个独立集, 分别为{0}, {1}, {2}, {3}, {1, 3}, 其中独立集{1, 3}是点数最多的独立集, 所
以是最大独立集.

0

c a
1

2
3
b
图 1 超图独立集

定义 2. 超边的大小和超点的度. 一条超边 e 的大小是超边 e 中包含的超点的个数, 记为 size(e). 一个超点 u 的
邻接边集包含所有超点 u 参与形成的超边, 记为 N u . 一个超点 u 的度是超点 u 参与形成的超边的数量, 记为
degree(u)=|N u |. 超点的平均度表示为 D, 超边的平均大小表示为 S.

3 超图邻接关系存储

本文采用改进的压缩存储格式 (improved compressed storage format, ICSF) [38] 来保存超图的点边邻接关系和边
点邻接关系. 图 2 给出了图 1 对应的 ICSF 存储格式, 这种邻接关系存储的格式没有用到指针和链表, 避免了复制
的指针操作和链表的维护工作, 结构比较简单, 方便维护, 并有效地避免了存储空间的浪费.
在 ICSF 存储格式中, 共包含 这 4 个数组. 其中 xadj 和 adjncy 保存超点对于超边的
邻接关系, eptr 和 eind 保存超边对于超点的包含关系. xadj 数组的长度为超图中的超点总数, 其保存的是 adjncy
数组的序号. 其中 xadj[i] 保存 i 号超点在 adjncy 数组中对应的起始位置. adjncy 数组的长度为所有超点的邻接超
边的个数之和, 其中保存的是超边序号. eptr 数组的长度为超图中的超边总数, 其保存的是 eind 数组的序号. 其中
eptr[j] 保存 j 号超边在 eind 数组中对应的起始位置. adjncy 数组的长度为所有超边中包含的超点的个数之和, 其
中保存的是超点序号.