| 摘要: |
| 极大二团枚举问题是二部图分析中的一个基本研究问题. 然而, 在实际应用中, 传统二团模型要求子图必须为完全二部图的约束往往过于严格, 因此需要一些更为宽松的二团模型作为代替. 为此, 提出一种新的称之为k-缺陷二团的松弛二团模型. 该模型允许二部图子图与完全子图二团最多相差k条边. 由于极大k-缺陷二团枚举问题属于NP-难问题, 设计高效的枚举算法是一项极具挑战性的任务. 为解决此问题, 提出一种基于对称集合枚举的算法. 该算法的思想是通过k-缺陷二团中缺失边的数量约束来控制子分支的数量. 为进一步提高计算效率, 还提出一系列优化技术, 包括基于排序的子图划分方法、基于上界的剪枝方法、基于线性时间的更新技术以及分支的优化方法. 此外, 提出的优化算法的时间复杂度与${\\mathrm{O}}(\\gamma _k^n) $有关, 其中${\\gamma _k} \\lt 2 $, 突破了传统${\\mathrm{O}}({2^n}) $的时间复杂度. 最后, 大量的实验结果表明, 在大部分参数条件下所提方法的效率相较于传统分支定界方法提高了100倍以上. |
| 关键词: 二部图 稠密子图挖掘 k-缺陷二团 |
| DOI：10.13328/j.cnki.jos.007270 |
| 分类号: |
| 基金项目:新一代人工智能国家科技重大专项(2020AAA0108503); 国家自然科学基金(U2241211, 62072034); 中国博士后创新人才支持计划(BX20240467); 中国博士后科学基金(2023M740245); 广东省哲学社会科学规划项目(GD21CYj21); 深圳市教育科学“十四五”规划: 2023年度项目(rgzn23021) |
|
| Efficient Algorithms for Maximal Defective Biclique Enumeration on Bipartite Graphs |
|
DAI Qiang-Qiang1, YU Han-Wen1, LI Rong-Hua1,2, LI Zhen-Jun2, WANG Guo-Ren1
|
|
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. |
| Key words: bipartite graph cohesive subgraph mining k-defective biclique |
