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

摘要：

图着色问题一直是计算机科学和数学领域最著名和经典的研究问题之一.由于目前图数据规模的不断增加,单机图着色算法性能受到限制.现有的分布式图着色算法大多基于共享内存的消息传递模型,而无共享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%.

关键词：分布式图着色、Pregel模型、Spark、GraphX

所属期刊栏目：12

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

资助基金：The National Natural Science Foundation of China under Grant Nos.61572353,61402323;the Natural Science Foundation of Tianjin under Grant No.17JCYBJC15400

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

页数：共12页

页码：886-897