面向分布式图计算的图划分技术综述  

Survey of Graph Partitioning Techniques for Distributed Graph Computing

作　　者：尚俊霖 张振宇[1] 屈稳稳 王晓玲[1] Shang Junlin;Zhang Zhenyu;Qu Wenwen;Wang Xiaoling(School of Computer Science and Technology,East China Normal University,Shanghai 200062)

机构地区：[1]华东师范大学计算机科学与技术学院,上海200062

出　　处：《计算机研究与发展》2025年第1期90-103,共14页Journal of Computer Research and Development

基　　金：国家重点研发计划项目(2021YFC3340702);国家自然科学基金重点项目(62136002);国家自然科学基金项目(61972155)。

摘　　要：图结构作为表达事物之间复杂关联的数据结构,被广泛使用在多种应用场景中.随着互联网应用的不断发展,数据规模的不断增加,分布式的图计算系统相较于传统单机系统从运算时间、资源调度等各个方面显现出优越的性能.近年来,基于大规模图数据的分布式图计算系统使用需求快速增加,图数据划分技术受到了学术界的广泛关注.通过对分布式图计算系统中的图划分技术的研究,首先介绍了面向分布式图计算的图划分的技术背景,给出当前分布式图计算系统中的图划分相关概念的定义以及相关计算模型的分类体系,报告了分布式图计算模型的发展现状.接着对不同的图划分策略中的具体技术进行介绍,通过在不同策略之间进行分析与比较,总结其在各类分布式图计算系统中的优势与不足.最后就分布式图计算系统中图划分技术的发展现状,讨论了其当前存在的挑战与未来的研究方向.The graph data structure,which is adept at encapsulating intricate relationships among entities,has been widely used in a vast array of application scenarios.With the incessant progression of Internet applications and the concomitant surge in data scales,distributed graph computing systems have demonstrated superior performance compared with traditional single-machine systems in various aspects,including computational efficiency and resource scheduling.In recent years,the increasing demand for distributed graph computing systems designed for handling large-scale graph data has brought graph partitioning technology to the forefront of academic research.Based on a comprehensive analysis of graph partitioning techniques for distributed graph computing,we explain the technological backdrop of graph partitioning in these systems.We provide definitions for key concepts related to graph partitioning in modern distributed graph computing systems and present a classification scheme for existing computational models,offering insights into the current status of distributed graph computing paradigms.Subsequent sections delve into the complexities of different graph partitioning methodologies,conducting a thorough analysis to determine their respective strengths and weaknesses within the context of various distributed graph computing frameworks.Finally,we discuss the current challenges and future research directions of graph partitioning technology in distributed graph computing systems.

关 键 词：图划分 图数据分析与管理 图计算 分布式图系统 超图划分 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]