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

doi:10.3969/j.issn.1000-0801.2016.02.012

摘要/Abstract

摘要：

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

关键词: 图划分, Giraph, 模拟退火, 大规模图, BSP

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

许金凤,董一鸿,王诗懿,何贤芒,陈华辉. LGP-SA：分布式环境下基于模拟退火的大规模图划分算法[J]. 电信科学, 2016, 32(2): 83-91.

Jinfeng XU,Yihong DONG,Shiyi WANG,Xianmang HE,Huahui CHEN. LGP-SA：Graph partition algorithm based on simulated annealing in large-scale graph processing[J]. Telecommunications Science, 2016, 32(2): 83-91.

图/表 16

图1

图2

图3

图4

图5

图6

表1

表2

表3

图7

图8

图9

图10

图11

图12

图13

参考文献 15

[1]	许金凤，董一鸿，王诗铬等. 大规模图数据划分算法综述[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.
[2]	CHING A . Giraph：Large-scale graph processing infrastructure on Hadoop[C]// Hadoop Summit 2011， Santa Clara，CA，USA. [S.l.：s.n.]， 2011.
[3]	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.
[4]	周爽，鲍玉斌，王志刚等. 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.
[5]	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.
[6]	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.
[7]	VAQUERO L ， CUADRADO F ， LOGOTHETIS D ， et al. xDGP：a dynamic graph processing system with adaptive partitioning[J]. Eprint Arxiv， 2013（9）.
[8]	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.
[9]	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.
[10]	VALIANT L G . A bridging model for parallel computation[J]. Communications of the ACM， 1990，33（8）： 103-111.
[11]	WHITE T . Hadoop：The Definitive Guide[M]. Cambridge：O’Reilly Media，Inc.， 2012.
[12]	RUTENBAR R . Simulated annealing algorithms：an overview[J]. IEEE Circnit and Devices Magazine， 1989： 19-26.
[13]	KUMAR V . Algorithm for constraint satisfaction problem：a survey[J]. AI Magazine， 1992，13（1）： 32-44.
[14]	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.
[15]	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.

图	顶点数/个	边数/个	来源	类别
Ego-Facebook	4 039	88 234	Facebook匿名社交圈	幂律图
Email-Enron	36 692	367 662	Enron电邮通信网络	幂律图
Ca-HepTh	9 877	51 971	协作网络	非幂律图
Loc-Brightkit	58 228	214 078	基于Brightkite位置的在线社交网络	非幂律图
Loc-Gowalla	196 591	950 327	基于Gowalla位置的在线社交网络	非幂律图
as-Skitter	1 696 415	11 095 298	网络拓扑图	非幂律图

图			温度
图	T=10	T=30	T=50	T=70	T=90
Ego-Facebook	0.234 8	0.181 4	0.184 9	0.180 3	0.184 5
Email-Enron	0.351 4	0.274 5	0.264 7	0.254 5	0.243 5
Ca-HepTh	0.251 5	0.187 8	0.186 4	0.173 4	0.165 4
Loc-Brightkit	0.214 5	0.172 4	0.171 8	0.164 2	0.157 5
Loc-Gowalla	0.364 1	0.145 4	0.124 8	0.148 7	0.134 5
as-Skitter	0.406 2	0.101 2	0.097 8	0.101 5	0.109 1

图			温度迭代步长
图	L=1	L=3	L=5	L=7	L=9
Ego-Facebook	0.211 2	0.174 9	0.163 5	0.160 3	0.164 5
Email-Enron	0.316 5	0.274 7	0.264 5	0.274 5	0.253 5
Ca-HepTh	0.221 5	0.176 4	0.184 5	0.173 4	0.164 8
Loc-Brightkit	0.214 5	0.161 8	0.157 8	0.164 2	0.163 5
Loc-Gowalla	0.234 1	0.144 8	0.148 8	0.148 7	0.134 5
as-Skitter	0.186 2	0.107 8	0.114 5	0.094 1	0.099 1