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