首页 | 本学科首页   官方微博 | 高级检索  
     

基于顶点组重分配的动态增量图划分算法
引用本文:李贺,刘延娜,杨舒琪,黄健斌,乔少杰.基于顶点组重分配的动态增量图划分算法[J].软件学报,2024,35(4):1819-1840.
作者姓名:李贺  刘延娜  杨舒琪  黄健斌  乔少杰
作者单位:西安电子科技大学 计算机科学与技术学院, 陕西 西安 710126;成都信息工程大学 软件工程学院, 四川 成都 610103
基金项目:国家自然科学基金(61602354, 61876138)
摘    要:图划分是分布式图计算中的一项基础工作, 其作用是将大规模图进行划分并分配到集群中的不同机器上. 图划分的质量对分布式图计算的性能有很大的影响, 其目标是降低负载平衡和最小化边割. 如今, 现实中的图数据通常呈动态增长态势, 这就需要一种能够处理动态增量图的划分方法, 在图数据动态增长的过程中确保划分的质量不受影响. 目前虽然有一些动态图划分算法被提出, 但它们不能同时专注于实时处理动态变化和获得高质量的划分结果. 提出基于顶点组重分配的动态增量图划分算法(ED-IDGP)来解决大规模动态增量图的划分问题. 在ED-IDGP算法中, 设计实时处理4种不同单元更新类型的动态处理器, 并在每次处理完单元更新后通过在分区发生动态变化的附近执行局部优化器进一步提高图划分的质量. 在ED-IDGP的局部优化器中, 利用基于改进标签传播算法的顶点组搜索策略搜索顶点组, 并利用提出的顶点组移动增益公式衡量最有益的顶点组, 将该顶点组移动到目标分区中做优化. 在真实数据集上从不同的角度和度量指标评估了ED-IDGP算法的性能和效率.

关 键 词:图划分  局部优化  动态增量图划分算法
收稿时间:2022/4/23 0:00:00
修稿时间:2022/8/29 0:00:00

Dynamic Incremental Graph Partitioning Algorithm Based on Vertex Group Redistribution
LI He,LIU Yan-N,YANG Shu-Qi,HUANG Jian-Bin,QIAO Shao-Jie.Dynamic Incremental Graph Partitioning Algorithm Based on Vertex Group Redistribution[J].Journal of Software,2024,35(4):1819-1840.
Authors:LI He  LIU Yan-N  YANG Shu-Qi  HUANG Jian-Bin  QIAO Shao-Jie
Affiliation:School of Computer Science and Technology, Xidian University, Xi''an 710126, China; 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 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.
Keywords:graph partitioning  local optimization  dynamic incremental graph partitioning algorithm
点击此处可从《软件学报》浏览原始摘要信息
点击此处可从《软件学报》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号