MapReduce-Based Graph Structural Clustering Algorithm

作者：Zhang Wei Peng; Li Zhen Jun; Li Rong Hua; Liu Yu Hong; Mao Rui; Qiao Shao Jie

来源：Journal of Software, 2018, 29(3): 627-641.

DOI：10.13328/j.cnki.jos.005456

• Graph clustering algorithms
• Graph data
• Map-reduce
• Merging algorithms
• Parallel computing models
• Similarity computation
• Structural clustering
• Structural graph

Graph Clustering is a fundamental task for graph mining which has been widely used in social network analysis related applications. Graph structural clustering (SCAN) is a well-known density-based graph clustering algorithm. SCAN algorithm can not only find the clusters in a graph, but also be able to identify hub nodes and outliers. However, with the growing graph size, the traditional SCAN algorithm is very hard to handle massive graph data, as its time complexity is O(m1.5) (m is the number of edges in the graph). To overcome the scalability issue of SCAN algorithm, this paper proposes a MapReduce based graph structural clustering algorithm, called MRSCAN. Specifically, the paper develops a MapReduce based similarity computation, a core node computation, as well as two clustering merging algorithms. In addition, it conducts extensive experiments over serval real-world graph datasets, and results demonstrate the accuracy, effectiveness, and scalability of the presented algorithm.

• 出版日期2018