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

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

doi:10.3969/j.issn.1000-0801.2016.02.012

您当前的位置：

首页 >

文章列表页 >

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

research and development | 更新时间：2024-06-05

- LGP-SA：Graph partition algorithm based on simulated annealing in large-scale graph processing
- Telecommunication Science Vol. 32, Issue 2, Pages: 83-91(2016)
- 作者机构：
- 作者简介：
- 基金信息：
- DOI：10.3969/j.issn.1000-0801.2016.02.012
  CLC： TP391
- Published Online：2016-02，
  
  Published：15 February 2016
- 稿件说明：
移动端阅览
Jinfeng XU, Yihong DONG, Shiyi WANG, et al. LGP-SA：Graph partition algorithm based on simulated annealing in large-scale graph processing[J]. Telecommunication science, 2016, 32(2): 83-91.
DOI：

Jinfeng XU, Yihong DONG, Shiyi WANG, et al. LGP-SA：Graph partition algorithm based on simulated annealing in large-scale graph processing[J]. Telecommunication science, 2016, 32(2): 83-91. DOI： 10.3969/j.issn.1000-0801.2016.02.012.

摘要

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

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.

关键词

Keywords

references

许金凤，董一鸿，王诗铬等 . 大规模图数据划分算法综述 [J ] . 电信科学， 2014 ， 30 （ 7 ）： 100 - 106 .

XU J F ， DONG Y H ， WANG S Y et al . Summary of large-scale graph partitioning algorithms [J ] . Telecommunications Science ， 2014 ， 30 （ 7 ）： 100 - 106 .

CHING A . Giraph：Large-scale graph processing infrastructure on Hadoop [C ] // Hadoop Summit 2011 ， Santa Clara，CA，USA . [ S.l.：s.n. ] ， 2011 .

MALEWICZ G ， AUSTEN M H ， BIK A J C et al . Pregel：a system for large-scale graph processing [C ] // 2010 ACM SIGMOD International Conference on Management of data ， June 6 - 10 ， 2010 ， Indianapolis，Indiana，USA . New York ： ACM Press ， 2010 ： 135 - 146 .

周爽，鲍玉斌，王志刚等 . BHP：面向BSP模型的负载均衡Hash图数据划分 [J ] . 计算机科学与探索， 2014 ， 8 （ 1 ）： 40 - 50 .

ZHOU S ， BAO Y B ， WANG Z G ， et al . BHP：BSP model oriented Hash graph data partition with load balancing [J ] . Journal of Frontiers of Computer Science ＆ Technology ， 2014 ， 8 （ 1 ）： 40 - 50 .

KHAYYAT Z ， AWARA K ， ALONAZI A ， et al . Mizan：a system for dynamic load balancing in large-scale graph processing [C// The 8th ACM European Conference on Computer Systems ， April 15 - 17 ， 2013 ， Prague，Czech . New York ： IEEE Press ， 2013 ： 169 - 182 .

UGANDER J ， BACKSTROM L . Balanced label propagation for partitioning massive graphs [C ] // The 6th ACM International Conference on Web Search and Data Mining ， February 6 - 8 ， 2013 ， Rome，Italy . New York ： ACM Press ， 2013 ： 507 - 516 .

VAQUERO L ， CUADRADO F ， LOGOTHETIS D ， et al . xDGP：a dynamic graph processing system with adaptive partitioning [J ] . Eprint Arxiv ， 2013 （ 9 ）.

BAO N T ， SUZUMURA T . Towards highly scalable pregel-based graph processing platform with x10 [C ] // The 22nd International Conference on World Wide Web Companion ， May 13 - 17 ， 2013 ， Rio de Janeiro，Brazil . Geneva ： International World Wide Web Conferences Steering Committee ， 2013 ： 501 - 508 .

SALIHOGLU S ， WIDOM J . GPS：A graph processing system [C ] // The 25th International Conference on Scientific and Statistical Database Management ， July 29 - 31 ， 2013 ， Baltimore，Maryland，USA . New York ： ACM Press ， 2013 .

VALIANT L G . A bridging model for parallel computation [J ] . Communications of the ACM ， 1990 ， 33 （ 8 ）： 103 - 111 .

WHITE T . Hadoop：The Definitive Guide [M ] . Cambridge：O’Reilly Media，Inc. ， 2012 .

RUTENBAR R . Simulated annealing algorithms：an overview [J ] . IEEE Circnit and Devices Magazine ， 1989 ： 19 - 26 .

KUMAR V . Algorithm for constraint satisfaction problem：a survey [J ] . AI Magazine ， 1992 ， 13 （ 1 ）： 32 - 44 .

LOW Y ， GONZALEZ J ， KYROLA A ， et al . GraphLab：a new framework for parallel machine learning [C ] // The 26th Conference on Uncertainty in Artificial Intelligence （UAI’10）， JJul 8 - 11 ， 2010 ， Catalina Island，California，USA . [ S.l.：s.n. ] ， 2010 ： 340 - 349 .

LOW Y ， BICKSON D ， GONZALEZ J ， et al . Distributed GraphLab：a framework for machine learning and data mining in the cloud [J ] . Proceedings of the VLDB Endowment ， 2012 ， 5 （ 8 ）： 716 - 727 .

Views

680

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

⁰