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

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2024,35(6):2999−3012 [doi: 10.13328/j.cnki.jos.006926] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

*
面向超图数据的最大独立集算法

徐兰天 1 , 李荣华 1 , 戴永恒 2 , 王国仁 1

1
(北京理工大学 计算机学院, 北京 100081)
2
(电科云北京科技有限公司, 北京 100043)
通信作者: 李荣华, E-mail: lironghuabit@126.com

摘 要: 超图是普通图的泛化表示, 在许多应用领域都很常见, 包括互联网、生物信息学和社交网络等. 独立集问
题是图分析领域的一个基础性研究问题, 传统的独立集算法大多都是针对普通图数据, 如何在超图数据上实现高
效的最大独立集挖掘是一个亟待解决的问题. 针对这一问题, 提出一种超图独立集的定义. 首先分析超图独立集搜
索的两个特性, 然后提出一种基于贪心策略的基础算法. 接着提出一种超图近似最大独立集搜索的剪枝框架即精
Key words: hypergraph; maximum independent set; heuristic algorithm
确剪枝与近似剪枝相结合, 以精确剪枝策略缩小图的规模, 以近似剪枝策略加快搜索速度. 此外, 还提出 4 种高效
的剪枝策略, 并对每种剪枝策略进行理论证明. 最后, 通过在 10 个真实超图数据集上进行实验, 结果表明剪枝算法
可以高效地搜索到更接近于真实结果的超图最大独立集.
关键词: 超图; 最大独立集; 启发式算法
中图法分类号: TP311

中文引用格式: 徐兰天, 李荣华, 戴永恒, 王国仁. 面向超图数据的最大独立集算法. 软件学报, 2024, 35(6): 2999–3012. http://www.
jos.org.cn/1000-9825/6926.htm
英 文 引 用 格 式 : Xu LT, Li RH, Dai YH, Wang GR. Maximum Independent Set Algorithm for Hypergraph Data. Ruan Jian Xue
Bao/Journal of Software, 2024, 35(6): 2999–3012 (in Chinese). http://www.jos.org.cn/1000-9825/6926.htm

Maximum Independent Set Algorithm for Hypergraph Data
1
1
2
XU Lan-Tian , LI Rong-Hua , DAI Yong-Heng , WANG Guo-Ren 1
1
(School of Computer Science and Technology, Beijing Institute of Technology, Beijing 100081, China)
2
(Diankeyun Technologies Co. Ltd., Beijing 100043, China)
Abstract: Hypergraphs are generalized representations of ordinary graphs, which are common in many application areas, including the
Internet, bioinformatics, and social networks. The independent set problem is a fundamental research problem in the field of graph
analysis. Most of the traditional independent set algorithms are targeted for ordinary graph data, and how to achieve efficient maximum
independent set mining on hypergraph data is an urgent problem to be solved. To address this problem, this study proposes a definition of
hypergraph independent sets. Firstly, two properties of hypergraph independent set search are analyzed, and then a basic algorithm based
on the greedy strategy is proposed. Then a pruning framework for hypergraph approximate maximum independent set search is proposed,
i.e., a combination of exact pruning and approximate pruning, which reduces the size of the graph by the exact pruning strategy and
speeds up the search by the approximate pruning strategy. In addition, four efficient pruning strategies are proposed in this study, and a
theoretical proof of each pruning strategy is presented. Finally, experiments are conducted on 10 real hypergraph data sets, and the results
show that the pruning algorithm can efficiently search for hypergraph maximum independent sets that are closer to the real results.

现实世界中的实体关系大多不能用简单地二元关系来表示, 而超图能更好地表示实体间的多元关系. 超图作
为一种比普通图承载更多信息, 也有更强大的表现能力的图表示形式, 有着重要的研究价值. 超图和普通图有明显

* 基金项目: 国家重点研发计划 (2021YFB3301301); 国家自然科学基金 (U2241211, 62072034)
收稿时间: 2022-06-21; 修改时间: 2022-08-28, 2022-11-10; 采用时间: 2023-03-05; jos 在线出版时间: 2023-08-23
CNKI 网络首发时间: 2023-08-28