面向二部图的极大缺陷二团高效枚举算法

作     者：代强强 于瀚文 李荣华 李振军 王国仁 

作者机构：北京理工大学计算机学院 深圳城市职业技术学院信息与通信学院 

出 版 物：《软件学报》 (Journal of Software)

年 卷 期：2025年

核心收录：

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：新一代人工智能国家科技重大专项(2020AAA0108503) 国家自然科学基金(U2241211,62072034) 中国博士后创新人才支持计划(BX20240467) 中国博士后科学基金(2023M740245) 广东省哲学社会科学规划项目(GD21CYj21) 深圳市教育科学“十四五”规划:2023年度项目(rgzn23021) 

主　　题：二部图 稠密子图挖掘 k-缺陷二团 

摘      要：极大二团枚举问题是二部图分析中的一个基本研究问题.然而,在实际应用中,传统二团模型要求子图必须为完全二部图的约束往往过于严格,因此需要一些更为宽松的二团模型作为代替.为此,提出一种新的称之为k-缺陷二团的松弛二团模型.该模型允许二部图子图与完全子图二团最多相差k条边.由于极大k-缺陷二团枚举问题属于NP-难问题,设计高效的枚举算法是一项极具挑战性的任务.为解决此问题,提出一种基于对称集合枚举的算法.该算法的思想是通过k-缺陷二团中缺失边的数量约束来控制子分支的数量.为进一步提高计算效率,还提出一系列优化技术,包括基于排序的子图划分方法、基于上界的剪枝方法、基于线性时间的更新技术以及分支的优化方法.此外,提出的优化算法的时间复杂度与O（γk~n）有关,其中γk2,突破了传统O（2~n）的时间复杂度.最后,大量的实验结果表明,在大部分参数条件下所提方法的效率相较于传统分支定界方法提高了100倍以上.