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

1798 软件学报 2025 年第 36 卷第 4 期

为了进一步提高计算效率, 本文还研究了 k-缺陷二团的相关性质, 提出了一系列的优化技术, 包括基于子图划
分的预处理技术、基于上界的剪枝技术、线性时间的更新技术以及分支优化技术. 值得注意的是, 本文证明提出
n
n O(2 ) 的上界. 实验结果表明, 所提
的优化枚举算法的时间复杂度与 O(γ ) 有关, 其中 γ k < 2 , 突破了传统枚举方法
k
出的优化枚举算法, 相较于基准算法具有极大的性能提升, 即在大部分参数情况下, 优化枚举算法的时间性能要比
传统枚举算法高 100 倍以上. 此外, 具体的案例分析证明了所研究模型的有效性.
本文第 1 节介绍面向二部图的稠密子图挖掘的相关工作. 第 2 节介绍本文的符号与问题定义. 第 3 节介绍本
文提出的基于对称集合枚举技术的搜索算法. 第 4 节介绍所提算法的优化技术, 并证明优化算法的时间复杂度.
第 5 节通过大量的实验验证所提方法的高效性与有效性. 最后总结本文的研究工作.

1-缺陷
二团
存在大量的冗余计算导致其效率往往不高. 为此, 需要设计一种新的算法以提高其计算效率.
p 1 p 2 p 3 p 4 p 5 p 6 p 7 p 8 p 1 p 2 p 3 p 1 p 2 p 3 p 4
(a) 部分电影-演员网络 (b) 极大二团社区 (c) 3-缺陷二团社区
图 1 互联网电影资料库 (IMDB) 电影-演员网络中的社区

1 相关工作

二团表示一个完全二部图, 是二部图数据中一种基本的稠密子图结构. 近年来, 研究者针对极大二团的枚举问
题进行了广泛地研究, 并提出了一系列的高效算法 [14−20] . 其中, Zhang 等人 [16] 提出了一种基于集合枚举的算法备受
R 中递归枚举所有可能的子集. 因
关注, 该算法的主要思想是从给定二部图 G = (L,R,E) 中较小的顶点集合 L 或者
为对于任何子集 A ⊆ L , 若 B 是 A 的共同邻居, 则 (A,B) 组成的子图一定是一个二团. 同时, 作者证明该算法具有多
项式延迟的时间复杂度. 为进一步提高计算效率, Das 等人 [17] 提出了一种基于排序的子图划分技术以将原始任务
|L| ) 个子任务, Abidi 等人 [18] 提出了一种基于支配集的支撑点剪枝枚举技术, 以及 Chen 等人 [19] 基于
划分 |R| (或者
一种新的排序技术和批量支撑点技术, 提出了一种具有多项式延迟的枚举算法. 最近, Dai 等人 [20] 基于新定义的支
撑点技术开发了一种新的枚举框架, 并证明该框架同时具有接近最优的时间复杂度和多项式延迟的时间复杂度.
由于二团模型在某些特定情况下对稠密子图的限定过于严格, 为此研究者们还引入了一些典型的松弛二团模
型 [21−23] 用于挖掘二部图数据中的稠密子图社区. 例如, Cerinšek 等人 [21] 基于最小度定义了一种 (α, β)-核的概念;
Liu 等人 [26] 提出了一种在最优时间内查询 (α, β)-核的索引算法; 张毅豪等人 [27] 提出泛化距离的 (α, β)-核分解算法;
Zou 等人 [22] 基于蝴蝶 (2×2 的二团) 的数量定义了 k-bitruss 模型; Wang 等人 [28] 同时提出了一种 k-bitruss 分解的算
法以及 k-bitruss 的社区索引算法; Sim 等人 [23] 提出了基于非邻居的数量定义的 k-biplex 模型; Yu 等人 [29] 以及 Dai
等人 [20] 针对极大 k-biplex 枚举问题提出了一系列的改进算法; Ignatov 等人 [30] 提出了一种基于边密度定义的伪团
模型. 基于之前的分析, 上述松弛的二团模型在特定应用场景下仍然存在一定的缺陷性. 为此, 本文定义了一种新
的称之为 k-缺陷二团的稠密子图模型. 该模型表示与完全子图二团相差最多 k 条边的二部图子图. 据了解, 目前还
没有针对二部图数据的 k-缺陷二团搜索算法. 虽然利用传统的分支定界枚举方法可用于解决该问题, 但是该方法

2 问题定义

令 G = (L,R,E) 为一个无向无权的二部图, 其中 L 和 R 分别表示二部图中两个相互独立的顶点集, E 表示 G 的
u ∈ R ). 本文令 n 和 m 分别为 G 中的顶点数和边数,
边集, 则对于任何边 (u,v) ∈ E 都满足 u ∈ L 且 v ∈ R (或者 v ∈ L 且
,
即 n = |L|+|R| m = |E| . 给定 L 中的一个顶点 v , 本文用 N v (G) 表示 v 在 G 中的邻居集合, 即 N v (G) = {u ∈ R|(u,v) ∈ E} ,
则 v 在 G 中的度表示为 d v (G) = |N v (G)| . 给定图 G 中的顶点集合 (A,B) , 本文用 G(A,B) = (A,B,E (A,B) ) 表示 G 由