Telecommunications Science ›› 2016, Vol. 32 ›› Issue (2): 83-91.doi: 10.3969/j.issn.1000-0801.2016.02.012

• research and development • Previous Articles     Next Articles

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

Jinfeng XU,Yihong DONG,Shiyi WANG,Xianmang HE,Huahui CHEN   

  1. College of Information Science and Engineering,Ningbo University,Ningbo 315211,China
  • Published:2017-02-03
  • Supported by:
    Zhejiang Provincial Natural Science Foundation of China;The National Natural Science Foundation of China

Abstract:

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 greatly. 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.

Key words: graph partition, Giraph, simulated annealing, large-scale graph, BSP

No Suggested Reading articles found!