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

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

3.2 算法框架
图划分问题是一个具有有限解集的组合优化问题, 其优化目标是最小化边切割和分区负载平衡. 本文研究的
是动态增量图划分算法, 当图发生动态变化时, 利用动态处理器处理完动态更新后, 再利用局部优化算法进一步提
高划分质量. 本文提出了基于顶点组重分配的动态增量图划分算法 ED-IDGP 来解决实时并持续增长的大规模动
态图的划分问题, ED-IDGP 算法的框架图如图 7 所示. 首先在输入初始图 G 上利用已有的图划分算法得到一个初
始划分 P = {P 1 ,P 2 ,...,P k } . 图动态更新∆G 是由一系列单元更新组成, 即顶点的插入、边的插入、顶点的删除和边
的删除. 图更新∆G 以动态更新流的方式均匀分配给 k 个动态处理器. 动态处理器用于接收和处理每一个单元更
新. 对于顶点的插入或边的插入, 动态处理器会根据当前分区的信息确定其赋值, 并将其发送给目标分区. 对于顶
点的删除或边的删除, 动态处理器将查找当前分区的顶点或边. 如果不在当前分区中, 它将被发送到它所在的分区
中. 在动态处理器处理完每个单元更新后, 如果分区发生变化, 那么触发局部优化器, 使得分区边界区域从局部次
优顶点划分转变为局部最优顶点划分, 从而进一步提高图划分的质量.

图更新 ∆G 输入图 G

局部优化器 局部优化器 局部优化器

P 1 P 2 P k
···
顶点 顶点 顶点
边 边 边

动态处理器 动态处理器 动态处理器

动态更新流 动态更新流 动态更新流

图 7 ED-IDGP 算法框架图

3.2.1 动态处理器
本文分别为顶点插入、边插入、顶点删除和边删除这 4 种不同的图更新类型介绍动态处理策略.
● 顶点插入. 虽然已有的一些工作 (例如, LDG [18] , FENNEL [19] , Leopard [29] , 文献 [37] 等) 为顶点插入提供了划
分策略, 但是它们都假设插入新顶点的大部分连接边在那时是已知的, 即一些局部图信息是已知的. 然而, 在许多
真实的分布式图处理或者图计算任务中, 图是实时发生变化的, 某个时刻插入一个新顶点并不能获取到该顶点的
大部分邻居信息. 例如, 在分布式图数据库中, 顶点及其连接的边通常从多个客户端独立且并发的插入. 这就需要
图划分算法能够在拥有有限图知识的情况下, 满足动态图划分的需求, 而现有的方法是不适用或者无效的.
本文考虑顶点插入的两种情况, 其一是某个时刻新顶点插入时, 还没有关于该顶点的边信息, 那么为了考虑负