主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2018年第12期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
张伟鹏,李振军,李荣华,刘宇鸿,毛睿,乔少杰.基于MapReduce的图结构聚类算法.软件学报,2018,29(3):627-641
基于MapReduce的图结构聚类算法
MapReduce-Based Graph Structural Clustering Algorithm
投稿时间:2017-08-03  修订日期:2017-09-05
DOI:10.13328/j.cnki.jos.005456
中文关键词:  图数据  并行计算模型  MapReduce  图结构聚类
英文关键词:graph data  parallel computing model  MapReduce  structural graph clustering
基金项目:国家自然科学基金(61402292,61772091);国家自然科学基金广东省联合基金(U1301252);教育部人文社会科学研究规划基金(15YJAZH058)
作者单位E-mail
张伟鹏 深圳大学 计算机与软件学院, 广东 深圳 518060  
李振军 深圳大学 计算机与软件学院, 广东 深圳 518060 15323940@qq.com 
李荣华 深圳大学 计算机与软件学院, 广东 深圳 518060  
刘宇鸿 深圳大学 计算机与软件学院, 广东 深圳 518060  
毛睿 深圳大学 计算机与软件学院, 广东 深圳 518060  
乔少杰 成都信息工程大学 网络空间安全学院, 四川 成都 610225  
摘要点击次数: 986
全文下载次数: 923
中文摘要:
      图结构聚类(SCAN)是一种著名的基于密度的图聚类算法,该算法不仅能够找到图中的聚类结构,而且还能发现图中的Hub节点和离群节点.然而,随着图数据规模越来越大,传统的SCAN算法的复杂度为Om1.5)(m为图中边的条数),因此很难处理大规模的图数据.为了解决SCAN算法的可扩展性问题,提出一种基于MapReduce的海量图结构聚类算法MRSCAN,这是一种计算核心节点以及两种合并聚类的MapReduce算法.最后,在多个真实的大规模图数据集上进行实验测试,实验结果验证了算法的准确性、有效性以及可扩展性.
英文摘要:
      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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利