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

徐兰天 等: 面向超图数据的最大独立集算法 3009

0.18
0.16 BA 60 000 BA
运行时间 (s) 0.12 MA2 算法内存占用 (KB) 40 000 MA1
0.14
50 000
MA1
MA2
0.10
30 000
0.08
0.06
0.04 20 000
0.02 10 000
0 0
Primary High Email Bills NDC Primary High Email Bills Math NDC
700 1 200 000
BA
600 MA1 1 000 000 BA
运行时间 (s) 400 MA2 算法内存占用 (KB) 800 000 MA2
MA1
500
600 000
300
200 400 000
100 200 000
89 382
0 0
Math DAWN Stack MAG DBLP DAWN Stack MAG DBLP
图 9 运行时间及内存占用

表 3 展示了 4 种剪枝策略在 10 个超图数据集上的应用效果. 剪枝 1 在较为稠密的图上的效果有限, 比如
contact-primary-school 和 contact-high-school, 这两个图中没有 one-degree 点, 则剪枝 1 失效. 而在较为稀疏的
coauth-DBLP 和 coauth-MAG-Geology 图上, 剪枝 1 可以在不损失准确度的情况下, 快速将 one-degree 点加入独立
集并将包含 one-degree 点的边删除来减小后续的搜索空间. 剪枝 2 是 4 种剪枝中唯一的一种近似剪枝, 为了保重
算法的效率和准确性, 剪枝 2 既需要删除高度点来为精确的剪枝 3 和剪枝 4 创造使用条件, 又需要尽量少的使用,
避免产生更多的误差. 在多数情况下, 剪枝 3 的删边数量要高于剪枝 4, 这是由于剪枝 3 的使用条件在搜索时更容
易满足. 剪枝 3 和 4 可以精确的剪边和降低高度点的度, 使得剪枝 2 删点时可以选择更准确的高度点.

表 3 4 种剪枝的效果

数据集 剪枝1删边 剪枝2删点 剪枝3删边 剪枝4删边
contact-primary-school 0 224 106 838 25
contact-high-school 0 278 171 848 142
email-Eu 46 597 219 076 1 556
congress-bills 1 1 626 259 939 176
tags-math-sx 36 957 659 429 1 194
DAWN 296 747 575 795 3 822
NDC-substances 1 063 706 32 178 35 484
tags-stack-overflow 2 045 21 331 8 247 828 60 194
coauth-MAG-Geology 516 790 26 348 134 611 168 942
coauth-DBLP 683 676 693 472 444 166

图 10 展示了 3 种算法搜索到的最大独立集点数与真实结果的比值. 从图中可以看出在所有搜索过程中的, 3
种算法的准确率都超过了 50%. 同时在所有超图数据集上, MA1 和 MA2 算法的准确率都大幅超过了 BA 算法, 在
数据集 congress-bills 上准确率的差异甚至达到了 40% 左右. 而 BA 算法在不同数据集上的表现不太稳定, 差异较
大, 在 congress-bills 上的准确率只有不足 55%, 而在数据集 DAWN 上则可超过 90%. MA1 和 MA2 算法则比 BA
算法稳定的多, 在所有的数据集上的准确率都超过了 90%, 甚至在一些数据规模较小的数据集上可以接近 100%,
比如数据集 contact-primary-school.