基于MapReduce的图结构聚类算法
作者:
作者单位:

作者简介:

张伟鹏(1991-),男,广东汕头人,硕士生,主要研究领域为大规模图数据并行算法;刘宇鸿(1997-),男,学士,主要研究领域为社区搜索,时态图挖掘;李振军(1979-),男,博士,工程师,主要研究领域为数据挖掘,深度学习;毛睿(1975-),男,博士,教授,CCF高级会员,主要研究领域为数据挖掘,数据库,统计方法,机器学习,计算生物;李荣华(1985-),男,博士,讲师,主要研究领域为图数据挖掘,社交网络分析;乔少杰(1981-),男,博士,教授,CCF高级会员,主要研究领域为轨迹数据挖掘,机器学习.

通讯作者:

李振军,E-mail:15323940@qq.com

中图分类号:

TP311

基金项目:

国家自然科学基金(61402292,61772091);国家自然科学基金广东省联合基金(U1301252);教育部人文社会科学研究规划基金(15YJAZH058)


MapReduce-Based Graph Structural Clustering Algorithm
Author:
Affiliation:

Fund Project:

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)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    图结构聚类(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.

    参考文献
    相似文献
    引证文献
引用本文

张伟鹏,李振军,李荣华,刘宇鸿,毛睿,乔少杰.基于MapReduce的图结构聚类算法.软件学报,2018,29(3):627-641

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2017-08-03
  • 最后修改日期:2017-09-05
  • 录用日期:
  • 在线发布日期: 2017-12-05
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号