Page 390 - 《软件学报》2025年第4期

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
2025,36(4):1796−1810 [doi: 10.13328/j.cnki.jos.007270] [CSTR: 32375.14.jos.007270] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

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

代强强 1 , 于瀚文 1 , 李荣华 1,2 , 李振军 2 , 王国仁 1

1
(北京理工大学 计算机学院, 北京 100081)
2
(深圳城市职业技术学院 信息与通信学院, 广东 深圳 518038)
通信作者: 李荣华, E-mail: lironghuabit@126.com

摘 要: 极大二团枚举问题是二部图分析中的一个基本研究问题. 然而, 在实际应用中, 传统二团模型要求子图必
须为完全二部图的约束往往过于严格, 因此需要一些更为宽松的二团模型作为代替. 为此, 提出一种新的称之为 k-
缺陷二团的松弛二团模型. 该模型允许二部图子图与完全子图二团最多相差 k 条边. 由于极大 k-缺陷二团枚举问
题属于 NP-难问题, 设计高效的枚举算法是一项极具挑战性的任务. 为解决此问题, 提出一种基于对称集合枚举的

算法. 该算法的思想是通过 k-缺陷二团中缺失边的数量约束来控制子分支的数量. 为进一步提高计算效率, 还提出
一系列优化技术, 包括基于排序的子图划分方法、基于上界的剪枝方法、基于线性时间的更新技术以及分支的优
n
n O(2 ) 的时间复杂度. 最后, 大
化方法. 此外, 提出的优化算法的时间复杂度与 O(γ ) 有关, 其中 γ k < 2 , 突破了传统
k
量的实验结果表明, 在大部分参数条件下所提方法的效率相较于传统分支定界方法提高了 100 倍以上.
关键词: 二部图; 稠密子图挖掘; k-缺陷二团
中图法分类号: TP311

中文引用格式: 代强强, 于瀚文, 李荣华, 李振军, 王国仁. 面向二部图的极大缺陷二团高效枚举算法. 软件学报, 2025, 36(4):
1796–1810. http://www.jos.org.cn/1000-9825/7270.htm
英文引用格式: Dai QQ, Yu HW, Li RH, Li ZJ, Wang GR. Efficient Algorithms for Maximal Defective Biclique Enumeration on
Bipartite Graphs. Ruan Jian Xue Bao/Journal of Software, 2025, 36(4): 1796–1810 (in Chinese). http://www.jos.org.cn/1000-9825/7270.
htm

Efficient Algorithms for Maximal Defective Biclique Enumeration on Bipartite Graphs
1,2
1
2
1
DAI Qiang-Qiang , YU Han-Wen , LI Rong-Hua , LI Zhen-Jun , WANG Guo-Ren 1
1
(School of Computer Science and Technology, Beijing Institute of Technology, Beijing 100081, China)
2
(School of Information and Communication, Shenzhen City Polytechnic, Shenzhen 518038, China)
Abstract: Maximal biclique enumeration is a fundamental research problem in the bipartite graph analysis field. However, the traditional
biclique model, which requires the subgraph to be a complete bipartite graph, is often overly constrained in practical applications, and thus
some looser biclique models are needed to substitute. In this study, a new relaxation biclique model called k-defective biclique is proposed.
This model allows a bipartite subgraph to differ from a complete bipartite subgraph biclique by up to k edges. Since enumerating maximal
k-defective bicliques is NP-hard, designing efficient enumeration algorithms is a challenging task. To solve this problem, an algorithm
based on symmetric set enumeration is proposed. The idea of this algorithm is to control the number of sub-branches through a constraint
on the number of missing edges in the k-defective bicliques. To further improve the computational efficiency, a series of optimization
techniques are also proposed, including ordering-based subgraph partitioning method, upper-bound based pruning method, linear time-based
updating technique, and optimization method for branching. In addition, the time complexity of the proposed optimization algorithms is
related to, where breaks through the traditional limitation. Finally, a large number of experimental results show that the efficiency of the
proposed method is over a hundred times higher than that of the traditional branch-and-bound approach for most parameter settings.

* 基金项目: 新一代人工智能国家科技重大专项 (2020AAA0108503); 国家自然科学基金 (U2241211, 62072034); 中国博士后创新人才支
持计划 (BX20240467); 中国博士后科学基金 (2023M740245); 广东省哲学社会科学规划项目 (GD21CYj21); 深圳市教育科学“十四五”
规划: 2023 年度项目 (rgzn23021)
收稿时间: 2024-05-10; 修改时间: 2024-06-27; 采用时间: 2024-08-02; jos 在线出版时间: 2025-01-08
CNKI 网络首发时间: 2025-01-15