Algorithm for Detecting Overlapping Communities from Complex Network Big Data

作者：Qiao, Shao Jie; Han, Nan^*; Zhang, Kai Feng; Zou, Lei; Wang, Hong Zhi; Gutierrez, Louis Alberto

来源：Journal of Software, 2017, 28(3): 631-647.

DOI：10.13328/j.cnki.jos.005155

• Balanced binary tree
• Graph computing
• Modularity
• Normalized mutual information
• On-line social networks
• Overlapping communities
• Overlapping community detections
• Traditional approaches

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.

• 出版日期2017
• 单位北京大学; 西南交通大学