关键词: 分布式图着色, Pregel模型, Spark, GraphX

Abstract: The graph coloring problem is one of the most famous and classical research questions in the field of computer science and mathematics. With the increasing of data scale, the performance of graph coloring algorithms is limited. And existing distributed graph coloring algorithms are mostly based on shared-memory message passing model. However, the development of Pregel model that has a share-nothing architecture has enhanced the data processing capability, and it has been the key technology for large-scale graph-data processing. But there is no related work to improve the existing distributed graph coloring algorithms to adapt share-nothing Pregel model and make an algorithm research and experimental comparison. In order to improve the performance of graph coloring algorithms, inspired by the classical graph coloring algorithm MIS (maximal-independent-set), this paper devises a distributed graph coloring algorithm MIS-Pregel based on the Pregel model. Then, this paper proposes two strategies to optimize the time for coloring and total number of colors, the first optimization strategy is based on the JP algorithm, and the second optimization strategy is based on the LDF algorithm. This paper implements the basic algorithm MIS-Pregel and two optimized algorithms (JP-Pregel and LDF-Pregel) based on above optimization strategies on Spark GraphX. Finally, extensive experiments show that the proposed basic algorithm has high efficiency of coloring and the performance of the optimization algorithms is improved by 26.4% and 30.9% than the basic algorithm over both synthetic and real datasets.

Key words: distributed graph coloring, Pregel model, Spark, GraphX