复杂网络大数据中重叠社区检测算法

被引：54

作者：

乔少杰 ^{[1
]}

韩楠 ^{[2
]}

张凯峰 ^{[3
]}

邹磊 ^{[4
]}

王宏志 ^{[5
]}

Louis Alberto GUTIERREZ ^{[6
]}

机构：

[1] 成都信息工程大学信息安全工程学院

[2] 成都信息工程大学管理学院

[3] 西南交通大学信息科学与技术学院

[4] 北京大学计算机科学技术研究所

[5] 哈尔滨工业大学计算机科学与技术学院

[6] Department of Computer Science, Rensselaer Polytechnic

来源：

软件学报 | 2017年 / 28卷 / 03期

关键词：

复杂网络; 大数据; 重叠社区检测; 模块度; 图计算;

D O I：

10.13328/j.cnki.jos.005155

中图分类号：

TP311.13 []; O157.5 [图论];

学科分类号：

1201 ;

摘要：

提出一种新的面向复杂网络大数据的重叠社区检测算法DOC(detecting overlapping communities over complex network big data),时间复杂度为O(nlog2(n)),算法基于模块度聚类和图计算思想,应用新的节点和边的更新方法,利用平衡二叉树对模块度增量建立索引,基于模块度最优的思想设计一种新的重叠社区检测算法.相对于传统的重叠节点检测算法,对每个节点分析的频率大为降低,可以在较低的算法运行时间下获得较高的识别准确率.复杂网络大数据集上的算法测试结果表明:DOC算法能够有效地检测出网络重叠社区,社区识别准确率较高,在大规模LFR基准数据集上其重叠社区检测标准化互信息指标NMI最高能达到0.97,重叠节点检测指标F-score的平均值在0.91以上,且复杂网络大数据下的运行时间明显优于传统算法.

引用

页码：631 / 647

页数：17

共 7 条

[1] 网络大数据:现状与展望
王元卓
靳小龙
程学旗
[J]. 计算机学报, 2013, 36 (06) : 1125 - 1138
[2] Overlapping community identification approach in online social networks[J] . Xuewu Zhang,Huangbin You,William Zhu,Shaojie Qiao,Jianwu Li,Louis Alberto Gutierrez,Zhuo Zhang,Xinnan Fan.Physica A: Statistical Mechanics and its Applicat . 2015
[3] Finding overlapping communities in networks by label propagation[J] . Steve Gregory.New Journal of Physics . 2010 (10)
[4] Detecting overlapping communities of weighted networks via a local algorithm
Chen, Duanbing
Shang, Mingsheng
Lv, Zehua
Fu, Yan
[J]. PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS, 2010, 389 (19) : 4177 - 4187
[5] Extending the definition of modularity to directed graphs with overlapping communities[J] . V Nicosia,G Mangioni,V Carchiolo,M Malgeri.Journal of Statistical Mechanics: Theory and Expe . 2009 (03)
[6] Detecting the overlapping and hierarchical community structure in complex networks[J] . Andrea Lancichinetti,Santo Fortunato,János Kertész.New Journal of Physics . 2009 (3)
[7] Fast unfolding of communities in large networks[J] . Vincent D Blondel,Jean-Loup Guillaume,Renaud Lambiotte,Etienne Lefebvre.Journal of Statistical Mechanics: Theory and Experiment . 2008 (10)

← 1 →