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

来源：计算机科学与探索杂志2018年第6期北京时间：

作者：甘瀛，王鑫，冯志勇，杨雅君

单位：1. 天津大学 计算机科学与技术学院，天津 3003542. 天津市认知计算与应用重点实验室，天津 3003543. 天津大学 软件学院，天津 300354

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