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

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

同, 这主要是因为所提算法的内存消耗与分支数量无关, 仅与二部图数据的大小成线性关系. 此外所提算法的内存
消耗与二部图的存储大小仅相差数倍, 这是因为算法使用了额外的索引以判断顶点之间的邻居关系. 该实验表明
所提算法具有很高的空间效率.

10 4 Graph size MDCE
iMDCE
Basic
内存 (M) 10 3 2
10
10 1
Youtube ActMovies Wiki-Cat IMDB Twitter DBLP
图 7 内存消耗

实验 5: 案例研究. 此外, 本文还进一步展开了一项案例研究以分析所提出的极大 k-缺陷二团在社区挖掘方面
的效果. 本实验利用 DBLP 上的数据信息 (https://dblp.uni-trier.de/xml) 构建二部图数据, 其中顶点分别表示作者和
文章, 作者与文章之间的关系则表示为边. 本实验基于不同二部图稠密子图社区模型检测了包含“研究者 2”的社
O(γ k ) 有关, 其中
区 (为保护个人隐私, 本文仅以不同编号代替具体作者姓名), 其中参数 k 和 q 分别设置为 2 和 5. 值得注意的是, 极
大 k-biplex 模型在此参数条件下难以在限定时间内找出所需结果, (α, β)-核模型所检测的社区规模过于庞大, 顶点
数超过 100 个. 为此本实验忽略了这两个模型的搜索结果. 图 8 展示了由二团模型和 k-缺陷二团模型的搜索结果.
可以看出, 相较于二团模型, 基于极大 k-缺陷二团模型可以从该数据中搜索到更多具有价值的信息. 具体地, 二团
模型的结果不包含研究者“研究者 1”和“研究者 7”, 然而 k-缺陷二团模型能够成功找出这两名研究者. 通过查找
DBLP 原始数据可知, 这两名研究者确实与其他研究者也存在非常密切的合作关系, 表明所提出的极大 k-缺陷二
团在真实二部图中检测社区具有一定的意义.

研究 研究 研究 研究 研究 研究 研究
者 1 者 2 者 3 者 4 者 5 者 6 者 7

(1) (2) (3) (4) (5) (6)
二团
图 8 利用 k-缺陷二团搜索包含“研究者 2”的社区结果 ( k = 2 q = 5 )
,

6 总 结

本文研究了面向二部图数据的稠密子图挖掘问题. 由于传统二团模型的限制过于严格, 为此本文提出了一种
称之为 k-缺陷二团的松弛二团模型. 为解决极大 k-缺陷二团枚举问题, 本文首先提出了一种基于对称集合枚举的
搜索算法. 为进一步提高算法的性能, 本文还提出了一系列的优化方法, 主要包括基于排序的子图划分方法、基于
上界的剪枝方法、线性时间的更新方法以及分支优化方法. 本文证明所提出的优化方法具有非平凡的理论时间复
γ k < 2 . 最后, 大量的实验表明所提出的极大 k-缺陷二团枚举算法在大部分参数情况
杂度, 主要与
下相较于传统枚举方法速度提高了 100 倍以上.

References:
[1] Lancichinetti A, Fortunato S. Community detection algorithms: A comparative analysis. Physical Review E, 2009, 80(5): 056117. [doi:
10.1103/PhysRevE.80.056117]
[2] Harley E, Bonner A, Goodman N. Uniform integration of genome mapping data using intersection graphs. Bioinformatics, 2001, 17(6):
487–494. [doi: 10.1093/bioinformatics/17.6.487]