Page 259 - 《软件学报》2024年第4期

李贺 等: 基于顶点组重分配的动态增量图划分算法 1837

验中, 我们固定 40% 的动态变化, 其中 30% 是顶点或者边的插入, 10% 是顶点或者边的删除, 并且设置分区的数
量 k 为 8. 我们分别评估了运行 PageRank 和 SSSP 的执行时间 (s) 和通信成本 (GB). 为了保持一致性, 我们将
PageRank 的迭代次数设置为 100, 并且选用拥有最大度的顶点作为 SSSP 的源顶点.
表 3 给出了 PageRank 和 SSSP 在所有数据集上的执行时间 (s) 和通信成本 (GB). 从表 3 中可知: (1) 本文提出
的 ED-IDGP 算法在所有数据集上的划分结果使得 PageRank 和 SSSP 的执行时间 (s) 和通信成本 (GB) 最低, 分布
式图计算任务 PageRank 和 SSSP 获得了最好的性能. (2) Streaming 算法得到的划分结果总体上获得了最差的性
能, 这主要是因为 Streaming 算法用于划分图的时间开销低, 但它所获得的图划分质量较差, 所以将 PageRank 和
SSSP 运行在 Streaming 算法的划分结果上得到了最差的性能. (3) 对于分布式图计算任务 PageRank, 在数据集
RoadNet-PA 上, ED-IDGP 算法的执行时间分别比 CCP、IncKGGGP 和 Streaming 低 13.03%、33.25% 和 50.38%.
ED-IDGP 算法的通信成本分别比 CCP、IncKGGGP 和 Streaming 低 11.85%、34.25% 和 40.8%. (4) 对于分布式图
计算任务 SSSP, 在数据集 Orkut 上, ED-IDGP 算法的执行时间分别比 CCP、IncKGGGP 和 Streaming 低 7.41%、
11.11% 和 29.82%. ED-IDGP 算法的通信成本分别比 CCP、IncKGGGP 和 Streaming 低 3.02%、4.89% 和 52.55%.
(5) 对于分布式图计算任务 PageRank, 对于所有的数据集, ED-IDGP 算法的执行时间平均比 CCP、IncKGGGP 和
Streaming 低 13.06%、17.42% 和 36.09%. ED-IDGP 算法的通信成本平均比 CCP、IncKGGGP 和 Streaming 低
13.58%、17.59% 和 47.23%. (6) 对于分布式图计算任务 SSSP, 对于所有的数据集, ED-IDGP 算法的执行时间平均
比 CCP、IncKGGGP 和 Streaming 低 11.25%、17.51% 和 37.42%. ED-IDGP 算法的通信成本平均比 CCP、
IncKGGGP 和 Streaming 低 17.49%、25.39% 和 55.27%.

表 3 图计算任务 PageRank 和 SSSP 的执行时间和通信成本

图发生动态变化后G+∆G的划分 P ′
图计算任务 数据集 度量指标
Streaming IncKGGGP CCP ED-IDGP
执行时间 (s) 34.2 24.0 22.1 19.1
DBLP
通信成本 (GB) 0.262 0.160 0.152 0.139
执行时间 (s) 65.9 49.0 37.6 32.7
RoadNet-PA
通信成本 (GB) 0.201 0.181 0.135 0.119
执行时间 (s) 78.6 55.5 55.4 46.7
Youtube
通信成本 (GB) 0.802 0.562 0.561 0.421
PageRank
执行时间 (s) 843.1 754.8 721.9 683.9
LiveJournal
通信成本 (GB) 8.789 5.078 5.099 4.767
执行时间 (s) 2 102.2 1 910.1 1 812.1 1 775.8
Orkut
通信成本 (GB) 3.678 1.915 1.876 1.868
执行时间 (s) 82 891.5 53 956.5 61 678.9 43 919.5
Twitter
通信成本 (GB) 288.971 179.621 191.234 135.441
执行时间 (s) 4.3 3.1 2.7 2.6
DBLP
通信成本 (GB) 0.009 3 0.005 6 0.003 9 0.003 4
执行时间 (s) 11.2 9.2 8.1 6.3
RoadNet-PA
通信成本(GB) 0.007 2 0.006 2 0.004 3 0.001 8
执行时间 (s) 14.9 12.6 12.5 10.1
Youtube
通信成本 (GB) 0.026 9 0.018 1 0.017 9 0.013 9
SSSP
执行时间 (s) 112.8 89.8 85.2 81.6
LiveJournal
通信成本 (GB) 0.283 1 0.160 9 0.154 3 0.149 8
执行时间 (s) 243.8 192.5 184.8 171.1
Orkut
通信成本(GB) 1.321 9 0.659 5 0.646 7 0.627 2
执行时间 (s) 4 567.9 2 688.1 2 477.9 2 212.3
Twitter
通信成本 (GB) 9.100 5.383 9 5.288 6 4.987 7