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

来源：计算机研究与发展杂志2017年第12期北京时间：

作者：李琪,钟将,李雪,

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

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