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

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

用|E(S, V \S)|表示顶点子集 S 和 V 中的其他顶点之间连接边的数量. 在分布式图处理和图计算中, 不同分区的顶点
之间需要传递消息, 而由于网络价格、网络带宽以及网络延迟等因素, 不同分区之间的消息传递成本较高, 因此需
要最小化不同分区之间边被切割的数量. 此外由于分布式图任务的整体性能由最慢的机器决定, 因此还需要保证
每个分区的负载尽可能相等, 即每个分区的顶点数几乎相同. EC(P) 表示在图 G 的一个顶点划分 P 下的边切割的
数量, 因此基于边割的图划分的问题定义如公式 (1) 所示.
1 ∑ k |V|
minEC (P) = |E (P i ,V\P i )| s.t. |P i | ⩽ (1+ε) (1)
2 i=1 k
ε = 1 表示
其中, ε 是满足 0 ⩽ ε ⩽ 1 的不平衡系数. 这里, ε = 0 表示每个分区具有相同顶点数量的最严格情况, 而
每个分区的顶点数量可能高达平均顶点数量的 2 倍.
定义 3. 负载平衡 (load balance, LB). 给定图 G 包含 k 个分区的一个划分 P = {P 1 ,P 2 ,...,P k } . LB(P) 表示在图
G 的一个顶点划分 P 下的负载平衡, 如公式 (2) 所示.

∑
k |V|
LB(P) = W (P i )− (2)
i=1 k
其中, W(P i ) 表示分区 P i 中的顶点数量.
定义 4. 边界顶点 (boundary vertex). 如果分区 P i 中的一个顶点 v 与 P 中的其他分区中的顶点存在边, 那么该
顶点 v 就是分区 P i 中的一个边界顶点.
定义 5. 动态图 (dynamic graph). 真实图应用中, 图 G = (V, E) 中存在顶点或边的插入或删除. 在一段时间内,
图 G 转变为图 G = (V ,E ) V = V ∪V I −V D , E = E ∪ E I − E D . 其中 V I 和 E I 分别表示图中新插入的顶点和边的
′
′
′
′
′
,
集合, V D 和 E D 分别表示图中被删除的顶点和边的集合. 将动态变化的那部分图数据标记为∆G, 即 ∆G = V I ∪V D ∪
E I ∪ E D .
定义 6. 动态增量图划分 (dynamic incremental graph partitioning). 对于初始图 G = (V, E), 当图发生动态变化变
′
′
′
为 G = (V ,E ) 时. 动态图划分问题是在原来 G 的初始划分 P 的基础上, 处理动态变化图数据∆G 以获得一个更新
′ ′ EC(P ) . 此外, 对于动
′
后的划分 P , 并且 P 需要在维持各个分区中的顶点数量尽可能相等的情况下最小化边切割
态图划分问题, 除了要保证划分质量外, 还需要最小化 P 和 P 之间的差异, 减少划分成本和时间开销.
′
2.2 问题分析
我们分别介绍顶点插入、边插入、顶点删除和边删除这 4 种不同类型的动态变化对图划分质量的影响.
● 顶点插入. 新顶点的插入有可能会导致分区负载不平衡, 从而影响图划分的质量. 图 2 展示了新顶点插入时
的一个例子. 从图 2(a) 可看出, 当新顶点 h 插入到 P 1 分区时, 会使得 P 1 分区中的顶点数从 4 变为 5, 而 P 2 分区中
的顶点数只有 3, 那么这会导致 P 1 分区和 P 2 分区的负载严重不平衡, 进而影响图划分的质量. 如果将顶点 d 从 P 1
分区移动到 P 2 分区, 那么这两个分区中的顶点数都为 4, 达到负载平衡, 如图 2(b) 所示. 此外, 此次通过移动顶点
d 进行局部结构调整也使得边切割的数量从 3 降为 2, 从而获得了一个局部最优顶点划分.

P1 P2 P1 P2
e d a
f e a
c
f d c
g h b h g b

(a) 插入顶点 h 导致分区负载不平衡 (b) 动态更新后的局部最优顶点划分
图 2 顶点插入对划分质量的影响

● 边插入. 如果插入新边的两个端点处于不同的分区中, 会导致边切割的数量增加 1, 从而导致划分质量的下
降. 图 3 展示了新边插入的一个例子. 图 3(a) 是由分区 P 1 和 P 2 组成的一个局部划分, 起初边 (b, h) 和 (b, k) 被切