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

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

素增量图划分方法和批处理增量图划分方法. 当图数据实时发生动态变化时, 对于执行中的分布式图计算任务, 需
要一种方法实时地对发生动态变化的图数据做处理以确保任务准确进行, 同时还需要保证图划分的质量以提升分
布式图计算的性能. 表 1 给出了不同种类的动态图划分方法的特点, 从中可知利用已有的静态图划分方法从头开
始重划分动态图会导致高的划分时间和成本. 大部分流式图划分方法没有局部优化, 一般会导致划分质量的下降,
并且流式图划分方法不能处理顶点或边的删除. 动态图重划分方法在已有初始图的分区上, 假设图发生动态变化
已经导致分区发生变化, 通过移动顶点进一步做优化. 该方法没有专门的机制处理动态变化部分以满足正在执行
的分布式图计算任务, 因此不适合这种应用场景. 而增量图划分方法能够专注处理动态部分. 但其中的批处理增量
图划分方法不是针对实时性提出的, 并且划分质量不高. 基于以上分析, 本文研究的是单元素增量图划分方法, 它
能够实时地专注处理动态图数据以确保执行中的分布式图计算任务准确进行, 以及通过局部优化技术以轻量级的
性能开销能够获得高质量的划分结果, 这具有重大的理论和现实意义.

表 1 动态图划分方法特点对比

类型 专注处理动态部分 实时性 轻量级 局部优化
从头开始重划分整个图 × × × ×
流式图划分方法 √ √ √ ×
动态图重划分方法 × × √ √
批处理增量图划分方法 √ × √ ×
单元素增量图划分方法 √ √ √ √

本文第 1 节介绍图划分的相关方法和研究现状. 第 2 节介绍问题定义和问题分析. 第 3 节介绍本文提出的基
于顶点组重分配的动态增量图划分算法的详细内容, 包括算法动机、算法框架、算法设计以及时空复杂度分析.
第 4 节通过对比实验验证本文提出的算法的有效性. 最后总结全文.
1 相关工作

早期的研究者针对静态图提出了大量的图划分算法, 主要分为基本图划分算法、多级图划分算法、局部图划
分算法、分布式图划分算法和基于标签传播的图划分算法等. 基本图划分算法根据不同的算法特征可分为谱划分
算法 [10] 、几何划分算法 [11] 和分支定界算法 [12] 等. 基本的图划分算法由于复杂度过高只能划分小规模的图. 随着图
规模的持续增长, 基本图划分算法无法满足需求, 于是研究者提出了多级图划分算法. 其中最经典的方法是
Metis [13,14] , 使用了多级划分策略, 但在扩展性上有缺陷. 此外, 还有 KL [16] , FM [17] 等图划分算法被提出进行局部的
优化. 为了提高可扩展性, 一些研究者提出了分布式的图划分算法, 如 PT-Scotch [15] , JA-BE-JA [31] . 文献 [32] 发现了
目前静态图划分中存在的一些问题, 提出了多级标签传播算法 MLP.
以上这些方法都是基于静态图划分提出来的, 真实世界中的图是动态变化的并且是持续增长的. 近年来, 已有
大量的研究者提出了动态图划分算法, 它的目标是当图发生动态变化时维持分区的负载平衡, 同时最小化被切割
的边数. 动态图划分算法从不同的关注点和特点出发, 主要可以分为流式图划分算法、动态图重划分算法和增量
图划分算法. 其中流式图划分算法依次处理顶点流, 可以用来划分动态图. 动态图重划分算法的特点是没有单独的
划分策略来处理动态变化部分, 它专注于在动态图的一个快照上通过局部调整不断地优化分区. 而增量图划分算
法为动态变化部分提出了处理策略, 该算法的特点是更专注于处理和划分动态变化部分, 通过将动态变化部分的
划分与原图的划分融合, 从而获得整个动态图的划分.
流式图划分算法的设计之初针对的是常规大图划分, 它将整个图视为一个顶点流, 依次将每个顶点划分到分
区中. 由于该算法可以处理新出现的顶点, 所以可以用来划分动态图, 即某个时刻的动态图的划分结果可以被视为
流式划分中的一个中间状态. 文献 [18] 提出了一种基于 Hash 的简单但有效的划分方法. 此外, 文献 [18] 也提出了
一种基于邻居分布的流式划分算法 LGD. 在 LGD 的基础上, FENNEL [19] 将图划分问题描述为流环境中的模块度
最大化, 并放宽了分区负载的硬约束. AKIN [20] 用 Jaccard 系数来计算顶点之间的相似性, 而不是仅根据邻居数量来