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

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

group movement gain formula is proposed to measure the most beneficial vertex group and move it to the target partition for optimization.
This study evaluates the performance and efficiency of the ED-IDGP algorithm from different perspectives and metrics on real datasets.
Key words: graph partitioning; local optimization; dynamic incremental graph partitioning algorithm

近年来, 随着互联网信息技术的迅猛发展, 各行各业每时每刻都在产生着各种各样的数据. 图作为一种特殊的
数据结构不但可以存储数据个体本身, 还可以存储数据个体之间复杂的关联关系. 在现实世界中, 许多应用都可以
建模为图, 例如有最短路径查找、关系模式挖掘、Web 网页排序等传统的图应用, 还有如社会网络分析、交通网
络分析、基于机器学习和深度学习的知识图挖掘等新兴的图计算应用. 早期的图数据规模较小, 只需要在单个机
器中进行存储和处理. 但是现如今, 我们所面临的图数据通常规模庞大、结构复杂, 而且呈动态增长态势. 例如, 微
信的日活跃用户从 2015 年的 5.7 亿增长到 2020 年的 10.9 亿. Facebook 的全球日活跃用户从 2011 年的 5 亿增长
到 2021 年的 18.8 亿. 万维网的中国网页数量从 2017 年的 2 604 亿增长到 2019 年的 2 978 亿. Google 的知识图谱
数据库从 2012 年的 5 亿个数据对象增长到现如今的 570 亿个数据对象. 随着图数据规模的日益增长, 在一台机器
上无法存储和处理大规模图数据. 因此, 大规模图数据需要在分布式环境中执行, 为了满足这一需求, 许多分布式
[1]
[5]
[3]
[2]
图处理系统应运而生, 如 Pregel , Giraph , GraphLab , Powerlyra 和 [4] RGraph 等. 此外, 还有一些针对图存储和
[6]
[8]
图查询的分布式图数据库系统, 如 Neo4j , Horton 和 [7] GraphBase 等.
在分布式图数据库系统或者分布式图处理系统中, 其中一个关键问题是如何将一个大规模图数据划分到一个
集群中的不同机器上, 以为多个客户端提供低延迟的在线查询服务或者为图处理任务提供高性能的并行计算. 因
此, 图划分是大规模分布式图处理的首要工作, 对图应用的存储、查询、处理和挖掘起基础支撑作用. 在分布式系
统中, 图应用的执行时间取决于一个集群中运行最慢的机器, 这就需要集群中的不同机器的工作负载应尽可能相
等. 此外, 图处理任务需要沿着图的拓扑结构进行, 这使得一个机器中的某些顶点需要与其他机器中的邻居顶点通
过传递消息进行通信. 例如图查询中需要从某个顶点开始进行遍历. 但是由于网络带宽、价格以及延迟等因素, 集
群中不同机器之间进行通信的成本远远要比机器内部的通信成本高, 这就需要不同机器间的通信成本应尽可能
低. 而图划分作为图处理的预处理步骤, 它的质量对分布式图处理任务的性能有很大的影响. 因此, 为了提高图计
算的性能, 图划分的目标是最小化不同分区间的通信成本, 同时保证各个分区的负载平衡.
图是由顶点和边构成, 划分一个图的基本方式主要有顶点划分 (基于边割的图划分) 和边划分 (基于点割的图
划分), 如图 1 所示. 顶点划分是将图中的顶点划分到不同的分区中, 若一条边的两个端点被划分到两个不同的分
区, 那么该边被切割. 基于边割的图划分的目标是最小化不同分区之间边被切割的数量, 并且使每个分区中顶点的
数量尽可能相等. 而边划分是将图中的边划分到不同的分区中, 若一个顶点的不同邻边被划分到两个或者多个不
同的分区中, 那么该顶点被切割. 基于点割的图划分的目标是最小化不同分区之间点被切割的数量, 并且使每个分
区中边的数量尽可能相等. 已有的大量工作表明基于边割的图划分有着更好的局部性, 而基于点割的图划分对于
具有超度顶点的图会使得分区负载更加平衡 [4] . 本文关注的是基于边割的图划分问题.

(a) 顶点划分 (b) 边划分
图 1 顶点划分与边划分

图划分问题已经被证明是一个 NP 难问题 [9] . 研究者提出了大量的启发式图划分算法, 从全局方法 [10−12] 到多
级方法 [13−15] 再到局部方法 [16,17] . 但这些方法都是用来划分静态图的. 随着图数据的规模不断增长, 真实世界中的图
表现出动态性, 即伴随着顶点或边的插入或删除. 如何对动态图进行划分已成为目前图划分领域研究的热点问题.
现有的可以对动态图进行划分的方法主要分为利用已有的静态图划分算法从头开始划分动态图、流式图划分方
法 [18−22] 、动态图重划分方法 [23−26] 以及增量图划分方法 [27−30] , 其中增量图划分方法根据处理更新的规模分为单元