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

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

分配顶点. 此外, 文献 [21] 在 LGD 的基础上考虑到集群中网络带宽以及节点计算能力的不同, 提出了一种异构感
知的流式图划分算法. 但是上述这些方法均为单元素的流式算法, 即每次划分一个顶点. 在无法得知后续流信息的
情况下, 为了平衡分区的负载, 一些顶点会违背贪心策略而被分配到负载较小的分区, 会导致划分质量的下降. 为
了解决这些缺陷, 一些基于流的优化划分方法被提出, 如 Loom [22] . 然而, 由于这些方法需要收集一段时间内的动
态变化或者操作整个图, 因此它们并不适合用于划分实时持续增长的动态图. 此外, 所有的流式图划分算法都没有
考虑图中顶点或边的删除.
针对图结构的动态性, 一些研究提出了动态图重划分算法. 动态图重划分算法的特点是假设图发生动态变化
已经导致分区发生了变化, 它更专注于在动态图的一个快照上通过动态调整不断优化分区. 例如文献 [23] 提出了
多级图的重划分算法, 在初始划分的基础上, 通过粗化、多级扩散和多级优化 3 个阶段来获取新的划分. 由于多级
的划分策略不适合于大规模图, 近期有许多轻量级的重划分算法被提出, 它们只需要少量的关于图的信息. 例如
[6]
XDGP [24] 在每次迭代中利用标签传播将单个顶点转移到邻居多的分区中. Hermes [25] 是应用在图数据库 Neo4j 上
的重划分算法. 然而, 它有可能会出现转移的震荡, 因此文献 [26] 提出了一种有效的两阶段方法以解决这个问题.
上述的这些方法都假设图划分的环境是同构的且无网络争用的, 也就是各分区之间的单位通信代价都一样. 因此
Planar [33] 提出了在异构环境中的图划分. 然而, 上述的这些重划分算法不能够实时地处理图的动态变化, 不满足实
时动态图的划分. 此外, 它们都是针对图结构的动态性而提出来的. 但是在分布式图处理系统中, 图计算大多都是
迭代进行的, 在每个超步中每个分区都有一部分顶点被激活而进行计算. 为了提升图计算的效率, 一些研究者提出
了针对计算动态的重划分算法, 如 CatchW [34] , LogGP [35] 等.
近年来, 针对图结构的动态性有些研究者提出了增量图划分算法, 这类算法适合于持续增长的动态图. 根据处
理动态变化的规模可以将增量图划分算法分为批处理增量图划分算法和单元素增量图划分算法. 顾名思义, 批处
理增量图划分算法是针对一批动态变化提出的划分策略. 早期, 文献 [27] 提出了基于线性规划的增量图划分方法,
但是由于计算复杂度过高, 它不能够处理大规模图. 最近, 文献 [28] 为已有的静态图划分算法提出了增量式版本
来解决动态图的划分问题, 由于它只是处理动态变化的那部分图数据, 因此划分效率比利用全局算法划分整个图
高, 如静态图划分算法 KGGGP [36] 的增量式版本 IncKGGGP. 但是这些方法是收集一段时间内的动态变化, 而不是
实时处理单个动态变化. 此外, 由于批处理增量图划分算法更专注于处理动态变化部分, 没有使用局部优化技术,
因此其划分质量不高. 而单元素增量划分算法是为每个单独的动态变化提供了划分策略. 例如文献 [37] 为顶点、
边的插入或删除分别提出了处理策略, 能够满足实时动态图的划分. 但是对于新的顶点, 它假设新顶点的大部分邻
居信息是可用的, 以将该顶点划分到邻居最多的分区中. 而这与一些真实世界中的图的动态性特点不相符. 例如在
社交网络中, 某个时刻会有新的用户注册, 但是短时间内缺乏邻居信息. 因此该方法具有一定的局限性. Leopard [29]
专门针对只读图计算任务设计的单元素增量图划分算法. IOGP [30] 提出了一种用于分布式图数据库的增量在线图
划分算法. 然而, IOGP 的设计目的是为图数据库上的联机事务处理操作 OLTP 实现高性能而设计的, 具有一定的局
限性.

2 基础知识

本文研究的是动态增量图划分算法来解决实时大规模动态图的划分问题, 下面介绍问题定义和问题分析.
2.1 问题定义
首先给出与图划分问题相关的一些基本概念, 并在此基础上定义本文所研究的动态增量图划分问题.
定义 1. 图 (graph). 给定一个图 G = (V, E), V 是图 G 中的顶点集合, E 是图 G 中的边集合. |V|是图 G 中的顶点
数量, |E|是图 G 中的边数量. 对于图 G 中的任意一个顶点 v, 用 N(v) 表示顶点 v 的邻居顶点的集合.
定义 2. 图划分 (graph partitioning). 基于边割的图划分的划分对象是图 G 中的顶点集合 V. 若图 G 被划分成 k
∪ k
个分区 P = {P 1 ,P 2 ,...,P k } , k 是一个远小于|V|和|E|的正整数, 满足 V = P i 且当 i 不等于 j 时 P i ∩ P j = ∅ , 其中 P i
i=1
是 P 的第 i 个分区, 那么称 P 是图 G 的一个顶点划分.
对于图 G 中的一个顶点子集 S⊆V, 用 E(S, V \S) 表示顶点子集 S 和 V 中的其他顶点之间连接边的集合, 并且