推荐星级：
- 1
- 2
- 3
- 4
- 5
复杂网络大数据中重叠社区检测算法
资料介绍
提出一种新的面向复杂网络大数据的重叠社区检测算法DOC(detecting overlapping communities over complex network big data),时间复杂度为O(nlog2(n)),算法基于模块度聚类和图计算思想,应用新的节点和边的更新方法,利用平衡二叉树对模块度增量建立索引,基于模块度最优的思想设计一种新的重叠社区检测算法.相对于传统的重叠节点检测算法,对每个节点分析的频率大为降低,可以在较低的算法运行时间下获得较高的识别准确率.复杂网络大数据集上的算法测试结果表明:DOC算法能够有效地检测出网络重叠社区,社区识别准确率较高,在大规模LFR基准数据集上其重叠社区检测标准化互信息指标NMI最高能达到0.97,重叠节点检测指标F-score的平均值在0.91以上,且复杂网络大数据下的运行时间明显优于传统算法.
部分文件列表
| 文件名 | 大小 |
| 复杂网络大数据中重叠社区检测算法.pdf | 1M |
部分页面预览
（完整内容请下载后查看）软件学报 ISSN 1000-9825, CODEN RUXUEW
Journal of Software,2017,28(3):631-647 [doi: 10.13328/j.cnki.jos.005155]
©中国科学院软件研究所版权所有.
E-mail:
Tel: +86-10-62562563
复杂网络大数据中重叠社区检测算法∗
1
2
3
4
5
乔少杰
,
韩
楠
,
张凯峰
,
邹
磊
,
王宏志
,
Louis Alberto GUTIERREZ6
1(成都信息工程大学 信息安全工程学院,四川 成都 610225)
2(成都信息工程大学 管理学院,四川 成都 610103)
3(西南交通大学 信息科学与技术学院,四川 成都 611756)
4(北京大学 计算机科学技术研究所,北京 100871)
5(哈尔滨工业大学 计算机科学与技术学院,黑龙江 哈尔滨 150006)
6(Department of Computer Science, Rensselaer Polytechnic Institute, New York, USA)
通讯作者: 韩楠, E-mail:
摘
要: 提出一种新的面向复杂网络大数据的重叠社区检测算法 DOC(detecting overlapping communities over
complex network big data),时间复杂度为 O(nlog2(n)),算法基于模块度聚类和图计算思想,应用新的节点和边的更新
方法,利用平衡二叉树对模块度增量建立索引,基于模块度最优的思想设计一种新的重叠社区检测算法.相对于传统
的重叠节点检测算法,对每个节点分析的频率大为降低,可以在较低的算法运行时间下获得较高的识别准确率.复杂
网络大数据集上的算法测试结果表明:DOC 算法能够有效地检测出网络重叠社区,社区识别准确率较高,在大规模
LFR 基准数据集上其重叠社区检测标准化互信息指标 NMI 最高能达到 0.97,重叠节点检测指标 F-score 的平均值在
0.91 以上,且复杂网络大数据下的运行时间明显优于传统算法.
关键词: 复杂网络;大数据;重叠社区检测;模块度;图计算
中图法分类号: TP311
中文引用格式: 乔少杰,韩楠,张凯峰,邹磊,王宏志,GUTIERREZ LA.复杂网络大数据中重叠社区检测算法.软件学报,2017,
28(3):631-
英文引用格式: Qiao SJ, Han N, Zhang KF, Zou L, Wang HZ, Gutierrez LA. Algorithm for detecting overlapping communities
from complex network big data. Ruan Jian Xue Bao/Journal of Software, 2017,28(3):631-
cn/1000-9825/5155.htm
Algorithm for Detecting Overlapping Communities from Complex Network Big Data
QIAO Shao-Jie1, HAN Nan2, ZHANG Kai-Feng3, ZOU Lei4, WANG Hong-Zhi5, Louis Alberto GUTIERREZ6
1(College of Information Security Engineering, Chengdu University of Information Technology, Chengdu 610225, China)
2(School of Management, Chengdu University of Information Technology, Chengdu 610103, China)
3(School of Information Science and Technology, Southwest Jiaotong University, Chengdu 611756, China)
4(Institute of Computer Science and Technology, Peking University, Beijing 100871, China)
5(Department of Computer Science and Technology, Harbin Institute of Technology, Harbin 150006, China)
6(Department of Computer Science, Rensselaer Polytechnic Institute, New York, USA)
∗ 基金项目: 国家自然科学基金(61100045, 61363037); 教育部人文社会科学研究规划基金(15YJAZH058); 教育部人文社会科
学研究青年基金(14YJCZH046); 成都市软科学项目(2015-RK00-00059-ZF); 四川省教育厅资助科研项目(14ZB0458)
Foundation item: National Natural Science Foundation of China (61100045, 61363037); Planning Foundation for Humanities and
Social Sciences of Ministry of Education of China (15YJAZH058); Youth Foundation for Humanities and Social Sciences of Ministry of
Education of China (14YJCZH046); Soft Science Foundation of Chengdu (2015-RK00-00059-ZF); Foundation of Educational
Commission of Sichuan Province (14ZB0458)
收稿时间: 2016-07-15; 修改时间: 2016-09-14; 采用时间: 2016-11-01; jos 在线出版时间: 2016-11-29
CNKI 网络优先出版: 2016-11-29 13:34:57, http://www.cnki.net/kcms/detail/11.2560.TP.20161129.1334.002.html
632
Journal of Software 软件学报 Vol.28, No.3, March 2017
Abstract: 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.
Key words: complex network; big data; overlapping community detection; modularity; graph computing
随着互联网、物联网技术的快速发展,事物之间的联系更加紧密,错综复杂的联系形成了多样、多变、规
模庞大的网络,例如人际交往形成的复杂社交网络、蛋白质交互网络、基于地理空间的交通网络、城市路线网
络等.上述网络因其结构复杂、网络进化、连接和节点的多样性、多重复杂性融合,被称为复杂网络[1].复杂网
络在规模与复杂度上的快速增长,演变成网络大数据[2].在现实网络中,社区重叠是复杂网络大数据中另一重要
特征,即,不同社区之间具有重叠的节点.重叠社区的检测对于网络结构分析、社区划分等具有重要研究价值和
科学意义.值得注意的是,国家重点基础研究发展计划(973)和重大科学研究计划将社交网络结构分析的基础研
究作为重要支持方向.
复杂网络大数据中,社区发现算法的研究涉及社会学、生物学、计算机等交叉学科,具有广阔的应用前景.
例如在生物学方面,社区检测可以从蛋白质、新陈代谢网络中提取信息,帮助了解生命的奥秘.本文的主要研究
动机包括:
1) 早期社区发现研究工作很少考虑重叠节点,建立在节点只属于某一社区的假设之上.然而,在网络大
数据中,社区之间重叠是其重要结构特征,考虑网络节点的重叠性可以极大地提高算法的准确性;
2) 传统的非重叠社区发现算法已经不能满足对现实网络分析的要求.现有的重叠社区检测算法时间复
杂性较高,应用于大规模复杂网络数据时,其劣势相当明显.当网络节点规模上万,节点连接关系更加
复杂的情况下,甚至无法对社区进行划分;
3) 现有重叠社区检测算法很难兼顾算法的准确性和实效性.
针对上述不足,本文的主要贡献包括:基于模块度思想和图论知识,应用新的网络模块度更新方法和社区合
并方法,采用平衡二叉树对其进行优化,其节点间模块度增量更新算法时间复杂度仅为 O(log2(n)),整体算法时
间复杂度为 O(nlog2(n)),其中,n 表示节点的个数;在非重叠网络社区检测算法得到的社区划分基础上,提出了一
种新的重叠社区检测算法,降低了每个节点识别的时间代价,算法的复杂度仅为 O(n);为该类问题提供一种新的
思路,即,将重叠节点的检测作为了一个分类问题进行研究;将所提算法与经典的社区识别算法 COPRA 算法
(clustering overlap propagation algorithm)[3]、SLPA 算法(speaker-listener label propagation algorithm)[4]和 CONGA
算法(cluster-overlap newman girvan algorithm)[5]进行了对比实验,从多角度验证所提方法的性能优势.
1
相关工作
复杂网络大数据中,社区发现算法是根据网络的拓扑结构以及节点属性的相似性,将网络进行模块划分的
方法,通常情况下,找到这类划分方法精确解是一个 NP 难问题.按照是否考虑重叠节点划分将社区发现算法分
为两类:未考虑重叠节点和考虑重叠节点社区发现算法,主要工作如下.
(1) 未考虑重叠节点的社区发现算法
基于模块度最优思想的凝聚类算法成为目前网络社区挖掘方法的主流,经典算法包括 Fast-Newman 算法[6]
和 CNM 算法[7]等.Fast-Newman 算法基于最大化模块度的贪婪思想,归并能够产生最大模块度增量的两个社区,
全部评论(0)