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

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

9.59%、8.48% 和 32.89%. (4) 在所有的数据集和分区数 k 上, ED-IDGP 算法的边切割改进值 ECI 平均比 CCP、
IncKGGGP 和 Streaming 高 10.86%、10.75% 和 72.99%.

ED-IDGP CCP Streaming ED-IDGP CCP Streaming
0.6
0.5 IncKGGGP IncKGGGP
0.5
0.4
0.4
NEC 0.3 NEC
0.3
0.2 0.2

0.1
0.1
2 4 8 16 2 4 8 16
k k
(a) 在 Youtube 上的标准化边切割 NEC (b) 在 Twitter 上的标准化边切割 NEC
图 9 不同的分区数量 k 所对应的标准化边切割 NEC

0.6 ED-IDGP CCP IncKGGGP ED-IDGP CCP IncKGGGP
0.7
Streaming Streaming
0.5 0.6
0.4 0.5
ECI 0.3 ECI 0.4
0.3
0.2
0.2
0.1
0.1
0 0
2 4 8 16 2 4 8 16
k k
(a) 在 DBLP 上的边切割改进值 ECI (b) 在 LiveJournal 上的边切割改进值 ECI
图 10 不同的分区数量 k 所对应的边切割改进值 ECI

′
此外, 对于最小化负载平衡 LB(P ) 的目标, 我们在数据集 DBLP 和数据集 LiveJournal 上评估了负载平衡改进
值 LBI, 如后文图 11 所示. 在图 11(a) 和图 11(b) 中, 横坐标表示的是分区的数量 k, 纵坐标表示的是负载平衡改进
值 LBI. 从图 11 中可知: (1) Streaming 算法拥有最高的负载平衡改进值 LBI, 但是它的边切割改进值 ECI 却是最低的
(如图 10 所示), 这主要是由 Streaming 算法特性决定的. (2) 除了 Streaming 算法, 与其他算法相比, 本文提出的 ED-
IDGP 算法具有更高的或者可比较的负载平衡改进值 LBI, 这主要是因为我们提出的方法同时考虑了边切割和负
载平衡, 从而实现了边切割和负载平衡之间的自适应平衡. (3) 在数据集 LiveJournal 上, 当分区数 k 为 8 时, 本文提
出的 ED-IDGP 算法的负载平衡改进值 LBI 分别比 CCP、IncKGGGP 高 16.68%、73.84%. (4) 在所有的数据集和
分区数 k 上, ED-IDGP 算法的负载平衡改进值 LBI 平均比 CCP、IncKGGGP 高 19.2%、26.46%.
4.3.2 算法效率分析
我们使用了与第 4.3.1 节相同的实验环境. 我们在数据集 DBLP 和数据集 LiveJournal 上评估了划分动态图数
据∆G 的时间 (如图 12 所示), 并且在数据集 Youtube 和数据集 Twitter 上评估了顶点的迁移效率 (如图 13 所示).
对于划分时间, 从图 12 中可知: (1) 总体来说, Streaming 算法用于划分动态图数据∆G 的时间最少, 这主要是因为
Streaming 算法是一种流式图划分算法, 其初衷是以牺牲一定的划分质量为代价, 从而大大减少划分图数据的时间.
(2) 总体来说, 除了 Streaming 算法, 与其他算法相比, 本文提出的 ED-IDGP 算法拥有更低的或者可比较的划分时间.