Boundary-connection deletion strategy based method for community detection in complex networks

摘要

Community detection in complex networks is a difficult problem. Up to now, there is no very effective method to solve it. Recently, many community detection algorithms based on edge removal have been proposed. However, these edge removal methods often delete many key connections within communities and weaken (or destroy) the community structure of the network. This will make the network communities more difficult to be identified and reduce the accuracy and stability of the algorithm. This paper proposed a boundary connection deletion based community detection algorithm. Different from other algorithms, our algorithm focuses on identifying and removing the boundary connections between network modules. This can enhance the network community structure and get high quality network modules. With high performance, our algorithm can detect the optimal and hierarchical community structure in weighted networks simultaneously. In order to verify the effectiveness of our algorithm, the stability and robustness of our algorithm were firstly analyzed. Then a series of experiments had been done on the real-world and synthetic networks. The real-world networks include Zachary’s karate club network, dolphin social network, American college foot-ball network, PolBooks network, Les Misérables character network, and the coauthorship network of scientists; The synthetic networks include GN benchmark and LFR benckmark. Two indices NMI and Modularity Q were used to compare our algorithm with the recently proposed algorithms, including meta-LPAm+, Srinivas and Rajendran’s model, IDPM, CFCDs, EDCD, CNM, and CDASS. Experimental results show that our algorithm has better performance than these algorithms.