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

发布时间：2018-06-25 15:49

本文选题：复杂网络 + 大数据　；参考：《软件学报》2017年03期

【摘要】：提出一种新的面向复杂网络大数据的重叠社区检测算法DOC(detecting overlapping communities over complex network big data),时间复杂度为O(nlog2(n)),算法基于模块度聚类和图计算思想,应用新的节点和边的更新方法,利用平衡二叉树对模块度增量建立索引,基于模块度最优的思想设计一种新的重叠社区检测算法.相对于传统的重叠节点检测算法,对每个节点分析的频率大为降低,可以在较低的算法运行时间下获得较高的识别准确率.复杂网络大数据集上的算法测试结果表明:DOC算法能够有效地检测出网络重叠社区,社区识别准确率较高,在大规模LFR基准数据集上其重叠社区检测标准化互信息指标NMI最高能达到0.97,重叠节点检测指标F-score的平均值在0.91以上,且复杂网络大数据下的运行时间明显优于传统算法.
[Abstract]:A new overlay community detection algorithm for complex networks, big data oriented, is proposed. The time complexity of DOC (detecting overlapping communities over complex network big data), is O (nlog2 (n), algorithm is based on the idea of modular clustering and graph computing), and a new updating method of nodes and edges is applied. A new overlapping community detection algorithm is designed based on the idea of modularity optimization by using the balanced binary tree to index the modular degree increment. Compared with the traditional overlapped node detection algorithm, the analysis frequency of each node is greatly reduced, and the recognition accuracy can be obtained under the lower running time of the algorithm. The test results on the big data set of complex networks show that the big data algorithm can effectively detect the overlapping communities of the network, and the accuracy of community recognition is high. On the large scale LFR benchmark data set, the maximum of overlapping community detection standardized mutual information index (NMI) can reach 0.97, and the average value of overlapping node detection index F-score is above 0.91, and the running time of complex network big data is obviously better than that of the traditional algorithm.
【作者单位】：成都信息工程大学信息安全工程学院;成都信息工程大学管理学院;西南交通大学信息科学与技术学院;北京大学计算机科学技术研究所;哈尔滨工业大学计算机科学与技术学院;Department
【基金】：国家自然科学基金(61100045,61363037) 教育部人文社会科学研究规划基金(15YJAZH058);教育部人文社会科学研究青年基金(14YJCZH046) 成都市软科学项目(2015-RK00-00059-ZF) 四川省教育厅资助科研项目(14ZB0458)~~
【分类号】：TP311.13;O157.5

【相似文献】