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

代强强 等: 面向二部图的极大缺陷二团高效枚举算法 1807

极大 k-缺陷二团的运行时间, 其中“-O”表示无排序优化, “-U”表示无上界优化, “-D”表示线性更新优化, “－”表示
算法在 24 h 的限定时间内无法完成计算. 值得注意的是, ActMovies 与 DBLP 中的极大 k-缺陷二团较小, 本实验对
这两数据集中的大小约束 q 设置为 6–10 的整数. 从表 2 或者表 3 中可以看出, 当不包含第 4 节中提出的任何一个
优化技术, 所提算法 iMDCE 的性能均会有所下降. 首先, 上界优化对所提算法的影响最大, 当不包含此项优化时,
所提算法在所有参数情况下均无法在 24 h 内完成计算. 其次, 排序优化在参数 q 相对较小或者 k 较大时具有明显
的性能优化, 例如, 在 ActMovies 中, 当 k = 3 q = 10 时, iMDCE 相较于不包含排序优化的 iMDCE 的运行时间加
,
速比超过 30 倍. 最后, 线性更新优化对枚举算法的影响最小, 但是在许多参数条件下仍然具有明显的加速. 该实验
结果表明所提出的优化技术对提高所提算法具有重要作用.

表 2 iMDCE 在 k=1 时使用不同优化技术的运行时间 (s)

q=8 (6) q=10 (7) q=12 (8) q=14 (9)
数据集
-O -U -D -O -U -D -O -U -D -O -U -D
Youtube 2 663.49 － 1 236.39 817.43 － 254.75 214.14 － 66.60 97.95 － 16.92
ActMovies 465.98 － 107.80 154.14 － 35.33 22.83 － 19.90 16.03 － 15.80
IMDB 5 897.60 － 1 352.31 980.88 － 310.12 291.47 － 109.82 57.08 － 39.54
Wiki-Cat 277.29 － 114.16 51.68 － 26.11 8.90 － 6.51 3.01 － 2.91
Twitter － － － － － 13 501.4 10 903.3 － 1 311.30 1 300.95 － 241.04
DBLP 18.64 － 17.86 14.42 － 14.21 14.48 － 14.29 14.08 － 14.03

表 3 iMDCE 在 q=16 (ActMovies 和 DBLP 为 10) 时使用不同优化技术的运行时间 (s)

k=1 k=2 k=3 k=4
数据集
-O -U -D -O -U -D -O -U -D -O -U -D
Youtube 28.95 － 4.91 1 391.11 － 167.98 － － 3 566.09 － － －
ActMovies 12.03 － 11.95 17.53 － 15.80 1 068.90 － 41.30 － － 16 815.2
IMDB 26.63 － 22.61 165.05 － 70.93 1 395.09 － 747.81 15 902.8 － 7 975.75
Wiki-Cat 2.78 － 2.76 3.16 － 2.94 5.68 － 4.82 32.27 － 19.70
－
－
－
－
－
Twitter 77.82 － 64.90 19 050.6 － 2 176.75 10 －
DBLP 14.36 － 13.80 14.08 － 13.84 14.21 － 13.90 15.58 － 14.85

实验 3: 可扩展性分析. 为研究所提算法的可扩展性, 本实验通过对二部图 Twitter 随机抽样 20%–80% 的顶点
和边以生成 8 个子图, 然后测试各个算法在这些图上的时间性能.图 6 展示了其实验结果. 可以看出, 除了所有算
法均能够快速计算的子图外, 提出的算法 iMDCE 和 MDCE 始终优于基准算法 Basic. 此外, 随着二部图数据的规
模增大, iMDCE 的运行时间平稳增长, 然而其他算法 (包括 MDCE 和 Basic) 的运行时间急剧增加. 例如, 在 k = 1 ,
iMDCE、MDCE 以及 Basic 在顶点抽样为 60% 的子图中的运行时间分别为 47.03 s, 52.32 s 以及 885.12 s. 然而当
顶点抽样增加到 80% 时, MDCE 和 Basic 的运行时间分别是 iMDCE 的 4.6 倍和超过 800 倍. 表明所提出的优化算
法具有较高的可扩展性, 可用于真实应用中的较大的二部图数据.

INF 4 iMDCE INF 4 iMDCE INF 4 INF 4
MDCE
MDCE
10
10
10
时间 (s) 10 3 2 Basic 时间 (s) 10 3 2 Basic 时间 (s) 10 3 2 时间 (s) 10 3 2
10
10
10
10
10 1 10 1 10 1 iMDCE 10 1 iMDCE
MDCE
MDCE
10 0 10 0 10 0 Basic 10 0 Basic
20 40 60 80 100 20 40 60 80 100 20 40 60 80 100 20 40 60 80 100
n (%) m (%) n (%) m (%)
(a) k=1 (b) k=1 (c) k=2 (d) k=2
图 6 可扩展性分析

实验 4: 算法内存消耗. 本实验还测试了各个算法在处理真实二部图数据时的内存消耗. 图 7 展示了各个算法
在变化参数 k 和 q 时最大的内存消耗. 可以看出所有算法 (包括 iMDCE、MDCE 以及 Basic) 的内存消耗几乎相