Multi-resolution community detection in massive networks

Abstract

Aiming at improving the efficiency and accuracy of community detection in complex networks, we proposed a new algorithm, which is based on the idea that communities could be detected from subnetworks by comparing the internal and external cohesion of each subnetwork. In our method, similar nodes are firstly gathered into meta-communities, which are then decided to be retained or merged through a multilevel label propagation process, until all of them meet our community criterion. Our algorithm requires neither any priori information of communities nor optimization of any objective function. Experimental results on both synthetic and real-world networks show that, our algorithm performs quite well and runs extremely fast, compared with several other popular algorithms. By tuning a resolution parameter, we can also observe communities at different scales, so this could reveal the hierarchical structure of the network. To further explore the effectiveness of our method, we applied it to the E-Coli transcriptional regulatory network, and found that all the identified modules have strong structural and functional coherence.

21 pages, 9 figures

References in corpus (17)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• Power-law distributions in empirical data
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Maps of random walks on complex networks reveal community structure
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Comparing community structure identification
• Stochastic blockmodels and community structure in networks
• Structure and tie strengths in mobile communication networks
• Quantifying social group evolution
• An information-theoretic framework for resolving community structure in complex networks
• Surprise maximization reveals the community structure of complex networks
• A New Comparative Definition of Community and Corresponding Identifying Algorithm
• Fast and accurate determination of modularity and its effect size