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

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

1.0 ED-IDGP CCP IncKGGGP 1.0 ED-IDGP CCP IncKGGGP
Streaming Streaming
0.8 0.8

0.6 0.6
LBI LBI
0.4 0.4

0.2 0.2
0 0
2 4 8 16 2 4 8 16
k k
(a) 在 DBLP 上的负载平衡改进值 LBI (b) 在 LiveJournal 上的负载平衡改进值 LBI
图 11 不同的分区数量 k 所对应的负载平衡改进值 LBI

10
ED-IDGP CCP Streaming 1 000 ED-IDGP CCP Streaming
IncKGGGP IncKGGGP
划分时间 (s) 1 划分时间 (s) 100

10
0.1
1
2 4 8 16 2 4 8 16
k k
(a) 在 DBLP 上的划分时间 (b) 在 LiveJournal 上的划分时间
图 12 动态图划分时间效率评估

0.40 0.25
ED-IDGP ED-IDGP
CCP CCP
0.35
0.20
VMR 0.30 VMR

0.15
0.25

0.20 0.10
2 4 8 16 2 4 8 16
k k
(a) 在 Youtube 上的顶点迁移率 VMR (b) 在 Twitter 上的顶点迁移率 VMR
图 13 动态图划分迁移效率评估

对于迁移效率, 从图 13 中可知: 除了在数据集 Twitter 上当分区数 k 为 4 时, CCP 算法有着更低或者可比较的
顶点迁移率 VMR, 这主要是因为 CCP 算法是一种简单的增量图划分算法, 它在每次处理完单元更新后, 只在较少
情况下通过移动单个顶点做局部优化, 导致划分质量不高. 而本文提出的 ED-IDGP 算法在利用动态处理器处理完
每个单元更新后, 通过移动顶点组 VG 做局部优化, 以获得高质量的划分结果.