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

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

(2) 批处理增量图划分算法 IncKGGGP 是已有的静态图划分算法 KGGGP [36] 的增量式版本, KGGGP 是一种贪
婪图生长方法. IncKGGGP 算法只处理动态变化部分, 没有做局部优化.
(3) 流式图划分算法 Streaming 提出了很多启发式用于将每一个新顶点分配到分区中, 在本实验中选用划分效
果最好的 LDG 启发式 [18] , 该算法是流式图划分算法中最具有代表性的其中一个.

表 2 数据集的统计信息

图 |V | (M) | E | 平均度 最大度
DBLP 0.32 1.05M 6.62 3.43k
RoadNet-PA 1.09 1.54M 2.83 9
Youtube 1.13 2.99M 5.27 28.7k
LiveJournal 4.00 34.7M 17.4 14.8k
Orkut 3.07 117M 76.3 33.3k
Twitter 41.6 1.20G 57.8 3.00M

为了客观地比较我们提出的 IDGP 和 ED-IDGP 与最先进的方法的效果和性能, 我们使用以下度量指标. 图划
分问题的目标之一是最小化不同分区之间边被切割的数量. 为了比较边切割的数量, 我们使用公式 (11) 定义的标
准化边切割大小 NEC 来衡量.
EC (P)
NEC = (11)
|E|
此外, 我们也使用公式 (12) 定义的 ECI 来衡量与初始图 G 的划分 P 相比边切割的改进值.
EC (P)− EC (P )
′
ECI = (12)
EC (P)
图划分问题的另一个目标是使每个分区中的顶点数尽可能相等, 但分区不是绝对平衡的. 为了比较分区负载
平衡, 我们使用公式 (13) 定义的 LBI 来衡量与初始图 G 的划分 P 相比负载平衡的改进值.
LB(P)− LB(P )
′
LBI = (13)
LB(P)
由于算法需要移动顶点来提高图划分的质量, 移动顶点需要一定的迁移成本. 为了比较迁移效率, 我们使用公
式 (14) 定义的顶点迁移率 VMR 来表示不同分区之间顶点移动的个数与总顶点数的比率, 这衡量了由于动态变化
∆G 而重分配 G 的成本.
migrated vertices
VMR = (14)
|V|
4.2 算法中的参数分析
本节分析 ED-IDGP 算法中在顶点组移动增益 vgm : gain s→t (VG) 中所使用的参数 γ 对不同分区之间边切割的
数量和分区负载平衡的影响. 我们选用数据集 DBLP 和数据集 LiveJournal 做评估和分析. 在每次实验中, 我们固
定 30% 的动态变化, 主要涉及顶点或边的插入. 为了展示多样化的实验结果, 在数据集 DBLP 上我们设置 k 为 2
和 k 为 8 这两种情况, 在数据集 LiveJournal 上我们设置 k 为 4 和 k 为 16 这两种情况. 图 8 分别给出了在数据集 DBLP
和数据集 LiveJournal 上的边切割改进值 ECI 和负载平衡改进值 LBI. 最小化不同分区之间边被切割的数量和使得
每个分区中的顶点数量尽可能相等是冲突的, 当参数 γ 的值为 0 时, 这意味着本文提出的 ED-IDGP 算法只关注最
小化分区负载不平衡, 而完全忽略了最小化边切割. 因此, 在这种情况下, 分区的负载几乎是相等的. 从图 8(b)
和图 8(d) 可看出, 所有的结果都表明负载平衡改进值 LBI 是最大的. 同时, 从图 8(a) 和图 8(c) 可看出, 相应的边切
割改进值 ECI 是最小的. 随着参数 γ 不断增大, 边切割所占的权重将不断增加, 即边切割改进值 ECI 将不断增大.
同时, 分区负载平衡所占的权重将不断减少, 即负载平衡改进值 LBI 将不断减小. 当参数 γ 的值为 1 时, 这意味 ED-IDGP
算法只关注边切割, 而完全忽略了分区负载平衡. 为了实现更低的边切割, 拥有更大移动增益的顶点组被允许从欠
负载的分区移动到超负载的分区中. 然而, 这也许会导致严重的分区负载不平衡. 同样, 为了在边切割和分区负载
平衡之间达到一个自适应的平衡, 在接下来的所有实验中, 我们将 γ 值设置为中间值 0.5.