ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2017, Vol. 54 ›› Issue (12): 2851-2857.doi: 10.7544/issn1000-1239.2017.20160690

• 基础理论 • 上一篇    下一篇

基于启发策略的动态平衡图划分算法

李琪1,钟将1,李雪2   

  1. 1(重庆大学计算机学院 重庆 400044); 2(昆士兰大学信息技术与电子工程学院 澳大利亚 布里斯班 4072) (liqi0713@foxmail.com)
  • 出版日期: 2017-12-01
  • 基金资助: 
    国家“八六三”高技术研究发展计划基金项目(2015AA015308);重庆市社会事业与民生保障科技创新专项(cstc2017shmsA0641)

DyBGP: A Dynamic-Balanced Algorithm for Graph Partitioning Based on Heuristic Strategies

Li Qi1, Zhong Jiang1, Li Xue2   

  1. 1(College of Computer Science, Chongqing University, Chongqing 400044); 2(School of Information Technology and Electrical Engineering, University of Queensland, Brisbane, Australia 4072)
  • Online: 2017-12-01

摘要: 随着计算技术的发展以及大数据时代的来临,分布式计算已成为研究的热点,其中大图迭代计算作为其研究的重点,降低划分后子图之间的通信边规模是改善计算性能的关键.传统算法很难在切割率最小化与负载均衡上同时满足.由于图划分属于NP组合优化问题,提出了一种动态平衡算法来解决图的平衡划分,确保在子图边界点划分最优的基础上引入扰动策略使其跳出局部最优扩大搜索空间,最后在真实世界图上验证算法的可行性,分别从平衡系数、切割边规模与传统算法进行了比较.在指定的扰动次数下,此算法比常见的算法hash,Chunk,Metis在割边率上分别降低了近40%,30%,5%.与Metis相比,平衡系数也更加地优化,实验结果证明了该算法的有效性.

关键词: 平衡图划分, 启发策略, 负载均衡, 分布式计算, 局部优化

Abstract: With the development of computing technology and the advent of the era of big data, the distributed computing has became a research hotspot. Iterative computation of big graph becomes the focus of the research. Reducing the communication data quantity between subgraph after effective partitioning, it is the key to improve the computational performance, because the existing algorithms are difficult to meet the requirements on both minimizing fraction of egdes cut and load balancing at the same time. In this paper, a dynamic-balanced algorithm for graph partitioning named DyBGP is proposed, and it is used to solve the problem of balanced partition. Based on ensuring the partitioning of subgraph boundary vertices optimal, the perturbation strategy to jump out of local optimum to expand the search space is used. Finally, our algorithm is verified the feasibility in the real-world graph, respectively from the balance coefficient and the scale of edges cut compared with the traditional algorithms, such as Hash, Chunk and Metis. In the number of edges cut, it is decreased about 40%, 30%, 5% with our algorithm under specifying perturbation times. In the balance coefficient, our algorithm is more optimized than Metis. The experimental results show that the algorithm is effective.

Key words: balanced graph partitioning, heuristic strategies, load balancing, distributed computing, local optimization

中图分类号: