基于MapReduce的图结构聚类算法

图结构聚类（SCAN）是一种著名的基于密度的图聚类算法。该算法不仅能够找到图中的聚类结构，而且还能发现图中的Hub节点和离群节点。然而，随着图数据规模越来越大，传统的SCAN算法的复杂度为O（m^1.5）（m为图中边的条数），因此很难处理大规模的图数据。为了解决SCAN算法的可扩展性问题，本文提出了一种新颖的基于MapReduce的海量图结构聚类算法MRSCAN。具体地，我们提出了一种计算核心节点，以及两种合并聚类的MapReduce算法。最后，在多个真实的大规模图数据集上进行实验测试，实验结果验证了算法的准确性、有效性，以及可扩展性。

MapReduce-Based Graph Structural Clustering Algorithm

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. The SCAN algorithm can not only find the clusters in a graph, but it also 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(m^1.5) (m is the number of edges in the graph). To overcome the scalability issue of the SCAN algorithm, we propose a MapReduce-based graph structural clustering algorithm, called MRSCAN. Specifically, we develop a MapReduce-based similarity computation, core node computation, as well as two clustering merging algorithms. Finally, we conduct extensive experiments over serval real-world graph datasets, and results demonstrate the accuracy, effectiveness, and scalability of our algorithm.