主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2020年专刊出版计划 微信服务介绍 最新一期:2019年第12期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
乔少杰,韩楠,张凯峰,邹磊,王宏志,Louis Alberto GUTIERREZ.复杂网络大数据中重叠社区检测算法.软件学报,2017,28(3):631-647
复杂网络大数据中重叠社区检测算法
Algorithm for Detecting Overlapping Communities from Complex Network Big Data
投稿时间:2016-07-15  修订日期:2016-09-14
DOI:10.13328/j.cnki.jos.005155
中文关键词:  复杂网络  大数据  重叠社区检测  模块度  图计算
英文关键词:complex network  big data  overlapping community detection  modularity  graph computing
基金项目:国家自然科学基金(61100045,61363037);教育部人文社会科学研究规划基金(15YJAZH058);教育部人文社会科学研究青年基金(14YJCZH046);成都市软科学项目(2015-RK00-00059-ZF);四川省教育厅资助科研项目(14ZB0458)
作者单位E-mail
乔少杰 成都信息工程大学 信息安全工程学院, 四川 成都 610225  
韩楠 成都信息工程大学 管理学院, 四川 成都 610103 hannan722@163.com 
张凯峰 西南交通大学 信息科学与技术学院, 四川 成都 611756  
邹磊 北京大学 计算机科学技术研究所, 北京 100871  
王宏志 哈尔滨工业大学 计算机科学与技术学院, 黑龙江 哈尔滨 150006  
Louis Alberto GUTIERREZ Department of Computer Science, Rensselaer Polytechnic Institute, New York, USA  
摘要点击次数: 1179
全文下载次数: 882
中文摘要:
      提出一种新的面向复杂网络大数据的重叠社区检测算法DOC(detecting overlapping communities over complex network big data),时间复杂度为Onlog2n)),算法基于模块度聚类和图计算思想,应用新的节点和边的更新方法,利用平衡二叉树对模块度增量建立索引,基于模块度最优的思想设计一种新的重叠社区检测算法.相对于传统的重叠节点检测算法,对每个节点分析的频率大为降低,可以在较低的算法运行时间下获得较高的识别准确率.复杂网络大数据集上的算法测试结果表明:DOC算法能够有效地检测出网络重叠社区,社区识别准确率较高,在大规模LFR基准数据集上其重叠社区检测标准化互信息指标NMI最高能达到0.97,重叠节点检测指标F-score的平均值在0.91以上,且复杂网络大数据下的运行时间明显优于传统算法.
英文摘要:
      Currently, the number of Internet users, along with complex networks including online social networks and electronic commerce networks, is growing explosively. To effectively and efficiently detecting overlapping community structure from complex network, big data plays an essential role in point of interest recommendation and hotspot propagation. In this study, a new algorithm over complex networks is proposed to detecting overlapping communities with a time complexity of O(nlog2(n)). The algorithm applies a new method for updating node and edge modularity based on the techniques of modularity clustering and graph computing. Balanced binary tree is used to index the modularity increment, and an overlapping community detection approach is provided based on the idea of modularity optimization to reduce the frequency of node analysis compared to traditional approaches. Experiments are conducted on real complex network big data, and the results show that the DOC algorithm can effectively detect overlapping communities with high accuracy, the normalized mutual information (NMI) can reach to 0.97 in large-scale LFR benchmark datasets, and the overlapping community detecting standard F-score value is averagely higher than 0.91. In addition, the runtime efficiency beats traditional approaches in complex network big data.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

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