LGP-SA:分布式环境下基于模拟退火的大规模图划分算法

LGP-SA:Graph partition algorithm based on simulated annealing in large-scale graph processing

针对大规模图数据的分布式计算,首先需要进行图划分。当前大规模图划分方法采用顶点转移策略来减少分区间的边割数以降低通信开销,但容易陷入局部最优,引入模拟退火的方法进行顶点转移后,极大地避免了局部最优的陷阱,也极大地防止了顶点无效转移,更好地降低了通信开销。对比实验显示,本算法划分大规模图的边割率有了极大的改进,并用PageRank算法验证了算法的有效性和可行性。

Distributed computing for large-scale graph data need to partition the graph firstly. The current methods of large-scale graph partitioning is to reduce the edge cut in order to lessen communication overhead by using vertex transfer strategies, but easily to fall into local optimum. Simulated annealing has a great probability to avoid the trap of local optimum and prevent vertices from invalid transfer which was introduced to transfer vertices. This method decreased communication overhead great/y. Comparative experiments show that the proposed algorithm has made a great improvement in reducing edge cut rates in large scale graph partition field. PageRank algorithm was also used to verify the effectiveness and feasibility of this method.