关键词: Spark, GraphX, 分布式计算, 图聚类, 社区结构

Abstract: Structural graph clustering is a fundamental algorithm in large graph analysis, which is of great value in many real-world applications, such as component detection, biological function discovery and graph visualization. At present, most of the distributed structural graph clustering algorithms are based on MapReduce framework in   Hadoop, however this framework requires a lot of disk I/O overhead and calculates the exact similarities between all adjacent vertices in the graph which increases the computation of the algorithm. To solve the above two problems, this paper proposes two pruning rules, the first to reduce the number of similarity calculation between adjacent vertices and the second to reduce the computation time by calculating the similarity between vertices imprecisely. Then this paper proposes a structural graph clustering algorithm based on GraphX in Spark, called GXDSGC, which saves a lot of disk I/O overhead during operation. Finally, extensive experiments on many real and synthetic datasets show the efficiency and effectiveness of the proposed GXDSGC algorithm. Notably, it performs more than 30 times faster than the compared MapReduce framework algorithm based on Hadoop, which improves the efficiency of the structural graph clustering in graph data analysis.

Key words: Spark, GraphX, distributed computing, graph clustering, community structures