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

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2024,35(4):1819−1840 [doi: 10.13328/j.cnki.jos.006842] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

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

李 贺 1 , 刘延娜 1 , 杨舒琪 1 , 黄健斌 1 , 乔少杰 2

1
(西安电子科技大学 计算机科学与技术学院, 陕西 西安 710126)
2
(成都信息工程大学 软件工程学院, 四川 成都 610103)
通信作者: 李贺, E-mail: heli@xidian.edu.cn

摘 要: 图划分是分布式图计算中的一项基础工作, 其作用是将大规模图进行划分并分配到集群中的不同机器上.
图划分的质量对分布式图计算的性能有很大的影响, 其目标是降低负载平衡和最小化边割. 如今, 现实中的图数据
通常呈动态增长态势, 这就需要一种能够处理动态增量图的划分方法, 在图数据动态增长的过程中确保划分的质
量不受影响. 目前虽然有一些动态图划分算法被提出, 但它们不能同时专注于实时处理动态变化和获得高质量的划
分结果. 提出基于顶点组重分配的动态增量图划分算法 (ED-IDGP) 来解决大规模动态增量图的划分问题. 在 ED-IDGP
算法中, 设计实时处理 4 种不同单元更新类型的动态处理器, 并在每次处理完单元更新后通过在分区发生动态变
化的附近执行局部优化器进一步提高图划分的质量. 在 ED-IDGP 的局部优化器中, 利用基于改进标签传播算法的
顶点组搜索策略搜索顶点组, 并利用提出的顶点组移动增益公式衡量最有益的顶点组, 将该顶点组移动到目标分
区中做优化. 在真实数据集上从不同的角度和度量指标评估了 ED-IDGP 算法的性能和效率.
关键词: 图划分; 局部优化; 动态增量图划分算法
中图法分类号: TP311

中文引用格式: 李贺, 刘延娜, 杨舒琪, 黄健斌, 乔少杰. 基于顶点组重分配的动态增量图划分算法. 软件学报, 2024, 35(4):
1819–1840. http://www.jos.org.cn/1000-9825/6842.htm
英文引用格式: Li H, Liu YN, Yang SQ, Huang JB, Qiao SJ. Dynamic Incremental Graph Partitioning Algorithm Based on Vertex
Group Redistribution. Ruan Jian Xue Bao/Journal of Software, 2024, 35(4): 1819–1840 (in Chinese). http://www.jos.org.cn/1000-9825/
6842.htm

Dynamic Incremental Graph Partitioning Algorithm Based on Vertex Group Redistribution
1
1
1
1
LI He , LIU Yan-Na , YANG Shu-Qi , HUANG Jian-Bin , QIAO Shao-Jie 2
1
(School of Computer Science and Technology, Xidian University, Xi’an 710126, China)
2
(School of Software Engineering, Chengdu University of Information Technology, Chengdu 610103, China)
Abstract: Graph partitioning is a basic task for distributed graph computing. It is used to divide a large-scale graph into different parts
and allocate them to different machines in a cluster. The quality of graph partitioning has a great impact on the performance of distributed
graph computing, and graph partitioning aims to minimize edge cuts and load balance. Nowadays, the graph data usually grow
dynamically, which needs a partitioning method to process dynamic incremental graphs, so as to ensure the quality of graph partitioning.
Although some dynamic graph partitioning algorithms have been presented recently, they cannot process real-time dynamic changes and
obtain high-quality graph partitioning results simultaneously. In this study, a dynamic incremental graph partitioning algorithm based on
vertex group redistribution (ED-IDGP) is proposed to solve the problem of large-scale dynamic incremental graph partitioning. In ED-IDGP,
a dynamic processor is designed to process four different unit update types in real time, and the graph partitioning quality is further
improved by executing a local optimizer near the dynamic change in the partition after each unit update. In the local optimizer of ED-IDGP,
a vertex group search strategy based on the improved label propagation algorithm is used to search for the vertex group, and a vertex

* 基金项目: 国家自然科学基金 (61602354, 61876138)
收稿时间: 2022-04-23; 修改时间: 2022-08-29; 采用时间: 2022-11-30; jos 在线出版时间: 2023-07-28
CNKI 网络首发时间: 2023-07-31