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

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

k=2 k=2
60 100
k=8 k=8
80
ECI (%) 40 LBI (%) 60
40

20 20
0
0 −20
0 0.25 0.50 0.75 1.00 0 0.25 0.50 0.75 1.00
γ γ
(a) 在 DBLP 上的边切割改进值 ECI (b) 在 DBLP 上的负载平衡改进值 LBI
100
80 k=4 k=4
k=16 80 k=16
60 60
ECI (%) 40 LBI (%) 40
20

0
20
−20
0 −40
0 0.25 0.50 0.75 1.00 0 0.25 0.50 0.75 1.00
γ γ
(c) 在 LiveJournal 上的边切割改进值 ECI (d) 在 LiveJournal 上的负载平衡改进值 LBI
图 8 ED-IDGP 算法中的参数 γ 对划分质量的影响

4.3 算法效果与性能的多维度评估
4.3.1 划分质量评估
在本实验中, 我们固定 40% 的动态变化, 其中 30% 是顶点或边的插入, 10% 是顶点或边的删除. 动态图划分
′
′ ′ EC(P ) 的目标, 我们在数据集
问题的目标是最小化边切割 EC(P ) 和最小化负载平衡 LB(P ) . 对于最小化边切割
Youtube 和数据集 Twitter 上评估了标准化边切割 NEC, 如图 9 所示. 在图 9(a) 和图 9(b) 中, 横坐标表示的是分区
的数量 k, 纵坐标表示的是标准化边切割 NEC. 从图 9 中可知: (1) 一般来说, 与现有的 CCP、IncKGGGP 和 Streaming
算法相比, 本文提出的动态增量图划分算法 ED-IDGP 具有更低的或者可比较的标准化边切割 NEC. (2) Streaming
算法有着最高的标准化边切割 NEC, 表现出了最差的划分质量, 这主要是因为 Streaming 算法提出了惩罚机制, 保
证了图划分结果的负载平衡, 从而忽略了减少边切割. (3) 在数据集 Twitter 上, 当分区数 k 为 16 时, 本文提出的
ED-IDGP 算法的标准化边切割 NEC 分别比 CCP、IncKGGGP 和 Streaming 低 24.87%、36.75% 和 49.91%. (4) 在
所有的数据集和分区数 k 上, ED-IDGP 算法的标准化边切割 NEC 平均比 CCP、IncKGGGP 和 Streaming 低 16.15%、
20.54% 和 49.53%.
′
同时, 对于最小化边切割 EC(P ) 的目标, 我们在数据集 DBLP 和数据集 LiveJournal 上也评估了边切割改进
值 ECI, 如图 10 所示. 在图 10(a) 和图 10(b) 中, 横坐标表示的是分区的数量 k, 纵坐标表示的是边切割改进值 ECI.
从图 10 中可知: (1) 与现有的 CCP、IncKGGGP 和 Streaming 算法相比, 本文提出的 ED-IDGP 算法具有更高的边
切割改进值 ECI. (2) 类似地, Streaming 算法在所有数据集和分区数 k 上拥有最低的边切割改进值 ECI. (3) 当分区
数 k 为 4 时, 在数据集 DBLP 上, ED-IDGP 算法的边切割改进值 ECI 分别比 CCP、IncKGGGP 和 Streaming 高