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

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

表 1 真实二部图数据

数据集 |L| |R| m d 1max d 2max
Youtube 94 238 30 087 293 360 1 035 7 591
ActMovies 127 823 383 640 1 470 404 294 646
IMDB 303 617 896 302 3 782 463 1 334 1 590
Wiki-Cat 1 853 493 182 947 3 795 796 54 11 593
Twitter 175 214 530 418 4 664 605 968 19 805
DBLP 1 953 085 5 624 219 12 282 059 1 386 287

(3) 参数设置: 所有的算法均包含了两个参数 k 和 q , 其 q 表示极大 k-缺陷二团的顶点数量的阈值, 即任何所
输出的 k-缺陷二团 (A,B) 均满足 |A| ⩾ q 且 |B| ⩾ q . 本文选择 k 为 1–4 的整数, 其默认值为 1; q 为 8–16 的整数. 由
于 ActMovies 和 DBLP 中的极大 k-缺陷二团比较小, 本文针对该数据设置 q 的取值范围为 5–10 的整数.
5.2 实验结果
实验 1: 算法的性能分析. 本文首先测试了各个算法枚举大小约束的极大 k-缺陷二团时的性能. 图 5 展示了各
个算法在分别变化参数 k 和 q 时处理不同真实二部图的运行时间. 值得注意的是, 本实验限定各个算法的运行时
间为 24 h, 当超过约束时间时, 其运行时间将设置为 INF. 从图 5 的实验结果可以看出, 基准算法 Basic 在绝大部分
参数情况下的运行时间均超过了 24 h 的时间限制, 而且除了少数参数所有算法均能高效计算外, 所提出的优化分
支算法 iMDCE 的运行时间均远低于所提出的 MDCE 算法. 例如, 在 IMDB 二部图中, 当 k = 1 以及 q = 14 时,
iMDCE 的运行时间为 37.99 s, 但是 MDCE 和 Basic 在相同条件下的运行时间为 606.83 s 和 60 279.2 s. 表明了所
提出的分支技术相较于传统分枝定界方法在减少冗余计算方面具有极大的性能优势. 此外, 当 k 较大或者 q 较小
时, 所提算法 iMDCE 相较于 MDCE 具有更高的加速比. 例如, 在二部图 IMDB 中, 当 k = 1 q = 14 时, iMDCE 相
,
较于 MDCE 的加速比为 15.9, 但是当 q = 12 时, iMDCE 相较于 MDCE 的加速比超过了 300 倍. 该实验进一步表
明提出的优化分支技术在减少冗余分支方面的优越性.

INF INF INF iMDCE INF iMDCE
MDCE MDCE
10 4 10 4 10 4 Basic 10 4 Basic
时间 (s)
时间 (s) 10 3 时间 (s) 10 3 时间 (s) INF
10 3
10 3
10 2
10 2
MDCE
MDCE
10 1 iMDCE 10 1 iMDCE 10 2 10 2
Basic Basic
10 0 10 0 10 1 10 1
8 10 12 14 16 1 2 3 4 5 6 7 8 9 10 1 2 3 4
q k q k
(a) Youtube (k=1) (b) Youtube (q=16) (c) ActMovies (k=1) (d) ActMovies (q=10)
INF INF INF INF
iMDCE iMDCE iMDCE iMDCE
10 4 MDCE 10 4 MDCE 10 4 MDCE 10 4 MDCE
时间 (s) 10 3 时间 (s) 10 3 时间 (s) 10 3 时间 (s) 10 3
Basic
Basic
Basic
Basic
10 2 10 2 10 2 10 2
10 1 10 1
10 1 10 1
8 10 12 14 16 1 2 3 4 8 10 12 14 16 1 2 3 4
q k q k
(e) IMDB (k=1) (f) IMDB (q=16) (g) Wiki-Cat (k=1) (h) Wiki-Cat (q=16)
INF INF
10 4
10 4 10 4 10 4 iMDCE iMDCE
时间 (s) 10 3 时间 (s) 10 3 时间 (s) 10 3 Basic 时间 (s) 10 3 Basic
MDCE
MDCE
10 2 iMDCE 10 2 iMDCE 10 2 10 2
MDCE
MDCE
Basic Basic
10 1 10 1 10 1 10 1
8 10 12 14 16 1 2 3 4 5 6 7 8 9 10 1 2 3 4
q k q k
(i) Twitter (k=1) (j) Twitter (q=16) (k) DBLP (k=1) (l) DBLP (q=10)
图 5 不同算法在真实二部图上的运行时间

实验 2: 优化技术的效果. 为了测试所提优化技术对所提算法性能的影响, 本实验还测试了所提算法在排除各
个优化技术时的运行时间. 表 2 和表 3 展示了算法 iMDCE 在不包含不同优化技术条件下变化参数 k 和 q 时枚举