| 摘要: |
| 图结构聚类（SCAN）是一种著名的基于密度的图聚类算法，该算法不仅能够找到图中的聚类结构，而且还能发现图中的Hub节点和离群节点.然而，随着图数据规模越来越大，传统的SCAN算法的复杂度为O（m1.5）（m为图中边的条数），因此很难处理大规模的图数据.为了解决SCAN算法的可扩展性问题，提出一种基于MapReduce的海量图结构聚类算法MRSCAN，这是一种计算核心节点以及两种合并聚类的MapReduce算法.最后，在多个真实的大规模图数据集上进行实验测试，实验结果验证了算法的准确性、有效性以及可扩展性. |
| 关键词: 图数据 并行计算模型 MapReduce 图结构聚类 |
| DOI：10.13328/j.cnki.jos.005456 |
| 分类号:TP311 |
| 基金项目:国家自然科学基金（61402292，61772091）；国家自然科学基金广东省联合基金（U1301252）；教育部人文社会科学研究规划基金（15YJAZH058） |
|
| MapReduce-Based Graph Structural Clustering Algorithm |
|
ZHANG Wei-Peng1, LI Zhen-Jun1, LI Rong-Hua1, LIU Yu-Hong1, MAO Rui1, QIAO Shao-Jie2
|
|
1.College of Computer Science & Software Engineering, Shenzhen University, Shenzhen 518060, China;2.School of Cybersecurity, Chengdu University of Information Technology, Chengdu 610225, China
|
| Abstract: |
| 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. |
| Key words: graph data parallel computing model MapReduce structural graph clustering |
