基于Pregel模型的分布式图着色算法

• 作者: 冯志勇 杨雅君 王鑫 甘瀛
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 分布式图着色 Pregel模型 Spark GraphX
• 年，卷（期）: 2018,（6）
• 所属期刊栏目: 数据库技术
• 页码范围: 886-897
• 页数: 12页
• 分类号: TP391
• 字数: 10439字
• 语种: 中文
• DOI: 10.3778/j.issn.1673-9418.1709036

摘要

图着色问题一直是计算机科学和数学领域最著名和经典的研究问题之一.由于目前图数据规模的不断增加,单机图着色算法性能受到限制.现有的分布式图着色算法大多基于共享内存的消息传递模型,而无共享Pregel计算模型的提出与发展提高了大规模图数据的处理能力,其已成为现今大数据处理的主流框架之一,但尚缺少将现有的分布式图着色算法适配到Pregel模型进行算法研究与实验比较的工作.为了提高图着色算法的性能,受经典图着色算法MIS(maximal-independent-set)启发,设计了一种基于Pregel模型的分布式图着色算法MIS-Pregel.结合着色时间和所需颜色数等方面提出了两种不同的优化策略,第一种优化策略基于JP算法,第二种优化策略基于LDF算法.在实现了主流图数据处理模型Pregel的Spark GraphX框架下开发了上述MIS-Pregel算法和两种改进算法JP-Pregel和LDF-Pregel.在合成数据集和真实数据集上进行了实验,大量实验结果表明所提分布式图着色算法能够高效地完成图着色任务,且JP-Pregel算法和LDF-Pregel算法的着色时间比MIS-Pregel算法分别平均缩短了26.4%和30.9%.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	冯志勇		146	1072	17.0	24.0
3	王鑫	天津大学计算机科学与技术学院	56	364	10.0	16.0
9	甘瀛	天津大学计算机科学与技术学院	2	3	1.0	1.0
13	杨雅君	天津大学计算机科学与技术学院	3	8	2.0	2.0