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

1836 软件学报 2024 年第 35 卷第 4 期

4.3.3 对不同动态变化规模的鲁棒性
在本实验中, 当动态更新∆G 的大小不同时, 我们讨论和分析本文提出的 ED-IDGP 算法的鲁棒性. 我们选择在
数据集 RoadNet-PA 和数据集 Orkut 上做评估, 并且设置分区的数量 k 为 8. 我们设置|∆G|从 20% 到 60%, 其中固
定 10% 的顶点或边的删除, 其他是顶点或边的插入. 在图 14 中展示了在数据集 RoadNet-PA 和数据集 Orkut 上,
不同的动态变化规模|∆G|所对应的标准化边切割 NEC. 从图 14(a) 和图 14(b) 中可知: (1) 在数据集 RoadNet-PA 和
数据集 Orkut 上, Streaming 算法对于所有的动态更新都有着最高的标准化边切割 NEC, 这与前面的实验结果一致.
(2) 在数据集 RoadNet-PA 上, 即使当动态更新规模|∆G|达到 60%, 本文提出的 ED-IDGP 算法有着最低的标准化边
切割 NEC. 类似地, 在数据集 Orkut 上, 与其他算法相比, ED-IDGP 算法始终拥有最低的标准化边切割 NEC. (3) 在
数据集 RoadNet-PA 上, 当|∆G|为 30% 时, ED-IDGP 算法的标准化边切割 NEC 分别比 CCP、IncKGGGP 和
Streaming 低 21.12%、32.57% 和 34.95%. 当|∆G|为 50% 时, ED-IDGP 算法的标准化边切割 NEC 分别比 CCP、
IncKGGGP 和 Streaming 低 26.18%、40.92% 和 43.72%. (4) 对于所有的数据集和不同的动态更新规模|∆G|, ED-IDGP
算法的标准化边切割 NEC 平均比 CCP、IncKGGGP 和 Streaming 低 18.9%、25.19% 和 48.06%.

0.30 0.55
ED-IDGP IncKGGGP CCP
Streaming
0.27 0.50
0.45
0.24 ED-IDGP IncKGGGP CCP
0.40 Streaming
NEC 0.21 NEC 0.35
0.18
0.30
0.15 0.25
0.12 0.20
20 30 40 50 60 20 30 40 50 60
动态更新规模 (%) 动态更新规模 (%)
(a) 在数据集 RoadNet-PA 上的结果 (b) 在数据集 Orkut 上的结果
图 14 不同的动态变化规模所对应的标准化边切割 NEC

4.3.4 分区数量的可收缩性分析
在本实验中, 我们讨论和分析当分区的数量 k 不同时, 本文提出的 IDGP 算法和 ED-IDGP 算法的可收缩性.
我们主要从划分质量和算法效率这两个方面对分区数量的可收缩性进行分析. 首先, 对于划分质量, 从第 4.3.1 节
的实验结果可知: (1) 如图 9 所示, 对于所有的算法, 随着分区的数量 k 增大, 标准化边切割 NEC 也会随着分区的
数量 k 的增大而增大. 这是合理的, 因为当分区的数量 k 增大时, 不同分区之间的通信成本会增加, 即边切割的数
量会增大. 当分区数 k 不同时, 与 CCP、IncKGGGP 和 Streaming 算法相比, ED-IDGP 算法的标准化边切割 NEC
更低或者是可比较的. (2) 如图 11(b) 所示, 在数据集 LiveJournal 上, 当分区数 k 为 4 时, 本文提出的 ED-IDGP 算
法的负载平衡改进值 LBI 分别比 CCP 和 IncKGGGP 高 6.51% 和 36.98%. 当分区数 k 为 16 时, 本文提出的 ED-IDGP
算法的负载平衡改进值 LBI 分别比 CCP 和 IncKGGGP 高 8.13% 和 30.89%. 然后, 对于算法效率, 从第 4.3.2 节的
实验结果可知, 如图 12 所示, 当分区的数量 k 从 2 增大到 16 时, 本文提出的 ED-IDGP 算法的划分时间总体都呈
下降趋势.
4.4 算法在分布式图计算任务中的效果分析
为了评估本文提出的 ED-IDGP 算法与其他比较方法相比在分布式图计算任务中的性能, 我们选用在图划分
领域中常见的用于评估图划分算法性能的两个图计算任务网页排名计算 (PageRank) 和单源最短路径 (SSSP). 我
们首先将 ED-IDGP、CCP、IncKGGGP 和 Streaming 算法得到的图发生动态变化后 G+∆G 的划分结果 P 作为输
′
入导入到分布式图处理系统 Giraph 中, 然后在 Giraph 平台上运行分布式图计算任务 PageRank 和 SSSP. 在本次实