Page 432 - 《软件学报》2024年第6期

3008 软件学报 2024 年第 35 卷第 6 期

为 C/C++. 如表 1 所示, 展示了本节使用的 10 个真实世界的数据集 [10] , 这些数据集的规模大小, 稠密程度各不相
同. 这些数据集均可则在 https://www.cs.cornell.edu/~arb/data/下载.

表 1 数据集

数据集 简称 |E|=m |V|=n S D 数据集 简称 |E|=m |V|=n S D
contact-primary-school Primary 106 879 242 2.09 922 DAWN DAWN 2 272 433 2 558 1.58 1 406
contact-high-school High 172 035 327 2.05 1 076 NDC-substances NDC 112 405 5 556 1.85 38
email-Eu Email 234 760 1 005 2.33 544 tags-stack-overflow Stack 14 458 875 49 998 2.96 859
congress-bills Bills 260 581 1 718 3.66 555 coauth-MAG-Geology MAG 1 590 335 1 261 129 2.77 4
tags-math-sx Math 822 059 1 629 2.19 1 106 coauth-DBLP DBLP 3 700 067 1 930 378 2.78 5

下面展示不同超图近似最大独立集算法在各数据集上的效果. 其中 BA 对应算法 1 是基于贪心的基本算法,
MA2 对应算法 3, 是结合了 4 种剪枝策略的改进近似算法, MA1 表示在算法 3 中不执行 3–6 行, 即不采用 one-
degree 点剪枝, 只采用其他 3 种剪枝的算法.
以看出, 超图数据集中的点数越多, 平均超边大小越大, 点的平均
表 2 展示了 3 种算法在 10 个超图数据集上搜索出的近似超图最大独立集的点数情况. 从表中可以看出, 在所
有的 10 个超图数据集中, MA1 算法和 MA2 算法查找到的超图最大独立集结果均优于 BA 算法. 而 MA1 和 MA2
两个算法相比, 其找到的最大独立集的点数则区别不大. 当超图数据集比较小时, 找到的超图独立集的总点数也比
较少, 此时两种算法的结果相同或相差极小, 如数据集 contact-primary-school, contact-high-school, email-Eu 和
congress-bills. 然而当超图数据集比较大时, 找到的超图独立集的总点数也比较多, MA2 算法找到的最大独立集明
显优于 MA1 算法, 例如在数据集 coauth-DBLP 中, MA1 找到的最大独立集的大小为 949 239, 而 MA2 算法为 952 366.
而且从图中可以看出, 超图独立集的总点数越多, MA2 算法的结果优势越明显.

表 2 最大独立集点数

数据集 BA MA1 MA2
contact-primary-school 12 16 16
contact-high-school 38 45 45
email-Eu 229 300 299
congress-bills 41 73 76
tags-math-sx 413 519 522
DAWN 1 298 1 417 1 411
NDC-substances 2 825 3 067 3 074
tags-stack-overflow 16 686 23 242 23 252
coauth-MAG-Geology 525 316 627 979 629 283
coauth-DBLP 751 018 949 239 952 366

图 9 展示了 3 种算法在 10 个超图数据集上搜索出的近似超图最大独立集的运行时间及内存占用. 从图中可
degree 越大, 则算法完成搜索超图近似最大独立
集的时间越长. 此外, BA 算法在所有数据集上的搜索时间都是最短的, 即使是对于数据规模最大的 coauth-DBLP
数据集, 仍然可以在 0.5 s 左右完成搜索. 而 MA1 算法和 MA2 算法的运行时间则明显长于 BA 算法. 在超图的规
模较小时, 如数据集 contact-high-school, email-Eu 和 congress-bills, MA1 算法快于 MA2 算法. 而在超图的规模较
大时, 如数据集 tags-stack-overflow, coauth-MAG-Geology 和 coauth-DBLP, MA2 算法用时则明显少于 MA1 算法.
甚至对于数据集 coauth-DBLP, MA2 算法只需要 310 s, 而 MA1 算法需要 573 s, MA2 比 MA1 算法快了一倍. 在内
存占用方面, BA 算法只需保存超边和超点间的邻接关系, 其内存占用很小. 而 MA1 和 MA2 算法加入了新的数据
结构, 需要多维护一个所有超点按 degree 降序的有序序列, 其内存占用约为 BA 算法的一倍左右. 而 MA1 和 MA2
这两种改进算法相比, 由于采用了相同的数据结构, 其内存占用几乎相同.