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

许金凤; 董一鸿; 王诗懿; 何贤芒; 陈华辉

doi:10.3969/j.issn.1000-0801.2016.02.012

您当前的位置：

首页 >

文章列表页 >

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

研究与开发 | 更新时间：2024-06-05

- LGP-SA：分布式环境下基于模拟退火的大规模图划分算法
- LGP-SA：Graph partition algorithm based on simulated annealing in large-scale graph processing
- 电信科学 2016年32卷第2期页码：83-91
- 作者机构：
- 作者简介：
  
  [ "许金凤（1990-），女，宁波大学硕士生，主要研究方向为大数据、数据挖掘。" ]
  [ "董一鸿（1969-），男，博士，宁波大学教授，主要研究方向为大数据、数据挖掘和人工智能。" ]
  [ "王诗懿（1989-），女，宁波大学硕士生，主要研究方向为大数据、数据挖掘。" ]
  [ "何贤芒（1981-），男，宁波大学讲师，主要研究方向为大数据、数据挖掘、隐私保护。" ]
  [ "陈华辉（1964-），男，博士，宁波大学教授，主要研究方向为数据流与数据挖掘。" ]
- 基金信息：
  
  浙江省自然科学基金资助项目;The Natural Science Foundation of Zhejiang Province of China(LY16F020003);国家自然科学基金资助项目;The National Natural Science Foundation of China(61572266)
- DOI：10.3969/j.issn.1000-0801.2016.02.012
  中图分类号： TP391
- 网络出版日期：2016-02，
  
  纸质出版日期：2016-02-15
- 稿件说明：
移动端阅览
许金凤, 董一鸿, 王诗懿, 等. LGP-SA：分布式环境下基于模拟退火的大规模图划分算法[J]. 电信科学, 2016,32(2):83-91.

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.
许金凤, 董一鸿, 王诗懿, 等. LGP-SA：分布式环境下基于模拟退火的大规模图划分算法[J]. 电信科学, 2016,32(2):83-91. DOI： 10.3969/j.issn.1000-0801.2016.02.012.

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 .

浏览量

680

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据