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

3000 软件学报 2024 年第 35 卷第 6 期

的区别. 其不同在于每条边不再仅关联两个点, 而可能关联更多的点. 因此原有的普通图上的一些基础定义和独立
集定义等需要在超图上重新诠释. 在现有的相关研究中, 更多的图挖掘算法是针对普通图上的, 由于超图与普通图
的结构差异, 很多普通图算法无法直接应用于超图.
而最大独立集问题是图算法中最重要的问题之一, 与一些基本的图问题 [1−4] 密切相关, 如最大诱导子图、最小
顶点覆盖、图着色和最大公共边子图等. 例如, 它已被用于计算社交网络覆盖率和到达率 [5] , 研究无线网络中的最
大加权独立集问题, 方便以分层方式组织网络的节点 [6] 等. 由于计算精确的最大独立集的复杂度非常高, 现有的算
法多采用启发式技术来近似计算最大独立集, 在实践中性能良好.
因此本文希望能结合超图的特性和普通图上最大独立集算法的搜索思想, 提出一种新的高效的启发式超图最
大独立集算法.
本文的主要贡献在于提出一种新的超图上的独立集和最大独立集的定义, 并基于对超图性质和独立集定义的
分析, 提出两种启发式的近似超图最大独立集算法.
本文第 1 节介绍超图和独立集的相关方法和研究现状. 第 2 节介绍本文所需的基础知识, 包括超图独立集和
超点度的定义. 第 3 节介绍超图邻接关系的存储格式. 第 4 节介绍超图独立集的性质分析. 第 5 节介绍一种超图最
大独立集的基础算法. 第 6 节介绍一种超图最大独立集的改进算法. 第 7 节分析算法的复杂度. 第 8 节通过实验验
证所提算法的有效性. 最后总结全文.

1 相关工作
对于超图的特征, 许多学者进行了深入的研究. Lee 等人 [7] 定义了 26 个超图基序 (h-motif), 以描述 3 个连通超
边 (而不是节点) 的连通性模式. 每个连接模式都是由一个独特的 h-motif 描述的, 独立于超边的大小. 文献统计了
来自 5 个不同域的 11 个真实世界超图中每个 h-motif 的实例数. 然后, 通过比较 h-motif 在每个超图中的实例数与
适当随机的超图中的实例数来衡量每个 h-motif 在每个超图中的显著性. 最后, 计算每个超图的特征轮廓 (定义为
每个 h-motif 的归一化显著性向量). 通过比较不同超图的计数和特征轮廓, 可以得出真实世界超图的结构设计原
则可由不同 h-motif 的频率捕获, 与随机超图的结构设计原则明显不同. 来自相同域的超图具有相似的特征轮廓,
而来自不同域的超图具有不同的特征轮廓. , Bable 等人
文献 [8−10] 不是直接处理超图的复杂性, 而是将超图简化为普通图的集合, 这些普通图包含超图的部分或全
部信息, 然后使用定义良好的图度量来识别这些图的性质. 最基本的方法是将一个超图转换为具有相同节点集和
相同边集的图, 将每个超边替换为一个团, 称为 2-投影图. 在 2-投影图上, 科研人员研究了单纯闭包, 将三元闭包
推广到超图 [11,12] , 定义了子超图中心性, 并将聚类系数的概念推广到超图 [13,14] . 这个简单的抽象被扩展到 n 投影图
和 n 级分解图, 它们旨在以不同的方式捕获 n 个节点子集之间的交互. Do 等人 [15] 提出, 由实超图得到的 n 级分解
图保留了 5 种结构模式: 巨连通分量、重尾度分布、小直径、高聚类系数和偏奇值分布. 除此以外, 人们还研究了
超边缘的子集相关性、近因偏差和重复模式的动态模式 [16] 和更多关于扩散和同步的模式 [17] . Kook 等人 [9] 研究了
超图的 7 个结构和动力学性质. 并定义了新的度量标准, 将普通图属性的扩展到了超图.
最大独立集问题是图论中经典的组合优化问题, 在生物信息学, 网络通信, 传输调度以及社交网络分析等领域
有着非常广泛的实际应用. Carraghan 等人 [18] [19] , Östergård 等人 [20] , Li 等人 [21] 提出了几种精确算法, 其
核心都是基于分支界定策略. 这种方法通过探索所有可能的情况来获得精确解. 每个顶点 u 可以包含在独立集中,
也可以不包含在独立集中. 则对于边 (u, v) 有 3 种情况, 选择 u, v 或者都不选 [22] . 枚举所有的可能, 最终获得精确
解. 此外还可利用动态规划、染色、覆盖等方法加速剪枝的过程, 可以提高算法的速度 [23] . 尽管如此, 在图上精确
求解最大独立集始终是个 NP-Hard 问题 [24] , 并且图的规模越大, 最大独立集算法的时间复杂度越高, 这使得精确
求解是不实际的.
因此许多学者开发了启发式的近似算法, 这些算法虽不能保证得到精确的最大独立集, 但其搜索速度快, 在解
决规模较大的图上的最大独立集搜索问题时具有极高的性价比. 目前应用比较广泛的启发式算法有贪婪算法 [25] ,