软件学报

作者：徐兰天，李荣华，戴永恒，王国仁

单位：徐兰天，北京理工大学 计算机学院, 北京 10008111,李荣华，北京理工大学 计算机学院, 北京 10008102,戴永恒，电科云北京科技有限公司, 北京 10004303,王国仁，北京理工大学 计算机学院, 北京 10008104

关键词：超图;最大独立集;启发式算法

基金：国家重点研发计划(2021YFB3301301); 国家自然科学基金(U2241211, 62072034)

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

来源：2024年第6期

《软件学报》期刊编辑部

查看软件学报杂志2024年第6期