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

摘要：

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

关键词：图划分、Giraph、模拟退火、大规模图、BSP

所属期刊栏目：32

分类号：TP391(计算技术、计算机技术)

资助基金：浙江省自然科学基金资助项目LY16F020003;国家自然科学基金资助项目No.61572266 Zhejiang Provincial Natural Science Foundation of ChinaLY16F020003;The National Natural Science Foundation of China61572266

在线出版日期：2016-03-30（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：83-91