Journal of Software:2018.29(3):627-641

(深圳大学 计算机与软件学院, 广东 深圳 518060;成都信息工程大学 网络空间安全学院, 四川 成都 610225)
MapReduce-Based Graph Structural Clustering Algorithm
ZHANG Wei-Peng,LI Zhen-Jun,LI Rong-Hua,LIU Yu-Hong,MAO Rui,QIAO Shao-Jie
(College of Computer Science & Software Engineering, Shenzhen University, Shenzhen 518060, China;School of Cybersecurity, Chengdu University of Information Technology, Chengdu 610225, China)
Chart / table
Similar Articles
Article :Browse 2751   Download 1775
Received:August 03, 2017    Revised:September 05, 2017
> 中文摘要: 图结构聚类(SCAN)是一种著名的基于密度的图聚类算法,该算法不仅能够找到图中的聚类结构,而且还能发现图中的Hub节点和离群节点.然而,随着图数据规模越来越大,传统的SCAN算法的复杂度为Om1.5)(m为图中边的条数),因此很难处理大规模的图数据.为了解决SCAN算法的可扩展性问题,提出一种基于MapReduce的海量图结构聚类算法MRSCAN,这是一种计算核心节点以及两种合并聚类的MapReduce算法.最后,在多个真实的大规模图数据集上进行实验测试,实验结果验证了算法的准确性、有效性以及可扩展性.
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.
文章编号:     中图分类号:TP311    文献标志码:
基金项目:国家自然科学基金(61402292,61772091);国家自然科学基金广东省联合基金(U1301252);教育部人文社会科学研究规划基金(15YJAZH058) 国家自然科学基金(61402292,61772091);国家自然科学基金广东省联合基金(U1301252);教育部人文社会科学研究规划基金(15YJAZH058)
Foundation items:National Natural Science Foundation of China (61402292, 61772091);National Natural Science Foundation of China Guangdong Joint Fund Project (U1301252);Planning Foundation for Humanities and Social Sciences of Ministry of Education of China (15YJAZH058)
Reference text:


ZHANG Wei-Peng,LI Zhen-Jun,LI Rong-Hua,LIU Yu-Hong,MAO Rui,QIAO Shao-Jie.MapReduce-Based Graph Structural Clustering Algorithm.Journal of Software,2018,29(3):627-641