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

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

割, 当动态变化插入一条新边 (a, h) 时并且将它分配到该划分中, 使得边 (a, h) 也被切割, 从而边切割的数量从 2
变为 3, 边插入不可避免导致了一个局部次优顶点划分. 而实际上如果在分配完新边之后, 通过调整分区边界区域
的局部结构, 将顶点 a 和 b 组成的一个顶点组从分区 P 1 移动到分区 P 2 , 那么就会实现一个局部最优顶点划分, 如
图 3(b) 所示.

P 1 P 2 P 1 P 2
d a h g d a h

e c b k j e c b k

f f
(a) 插入边 (a, h) 导致局部次优顶点划分 (b) 动态更新后的局部最优顶点划分
图 3 边插入对划分质量的影响

● 顶点删除. 当删除一个顶点时, 会同时删除该顶点的连接边, 顶点的删除与顶点的插入同样有可能会导致分
区负载不平衡. 图 4 展示了一个顶点删除的例子. 当从现有的图中删除顶点 e 时, 如图 4(a) 所示, 会使得 P 1 分区中
的顶点数变为 2, 而 P 2 分区中的顶点数为 4, 这导致了分区负载的严重不平衡, 从而出现了一个局部次优顶点划
分. 如果将顶点 b 从 P 2 分区移动到 P 1 分区, 那么会使得 P 1 分区和 P 2 分区中的顶点数都为 3, 同时边切割的数量
也从 3 降为 2, 从而在删除顶点后通过局部结构的调整达到了一个局部最优顶点划分, 如图 4(b) 所示.

P 1 P 2
P 1 P 2

f a c f a c
×
e
g
×
g b d b d

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

● 边删除. 如果要删除边的两个端点处于同一分区中, 有可能会导致划分质量的下降. 后文图 5 展示了边删除
的一个例子. 从图 5(a) 可看出, 当将边 (a, d) 从现有的图中删除之后, 在分区边界区域导致出现了局部次优顶点划分.
图 5(b) 展示了该分区边界区域的局部最优顶点划分, 可以看到将顶点 a、b 和 e 作为一个顶点组整体移动后, 会导
致边切割的数量从原来的 3 降为 1, 从而获得了一个更好的划分结果.

3 基于顶点组重分配的动态增量图划分算法

3.1 算法动机
真实世界中的图大多都是不断变化并且持续增长的. 动态图划分方法需要实时处理每次传入的动态变化, 包
括插入顶点或边到分区中和从分区中删除顶点或边. 因此, 需要设计动态处理器专门处理图的动态变化, 得到由初
始图和动态变化的那部分图数据所构成的一个新的划分. 但是如果只使用动态处理器处理动态变化来解决动态图