Narrow scope for resolution-limit-free community detection

Abstract

Detecting communities in large networks has drawn much attention over the years. While modularity remains one of the more popular methods of community detection, the so-called resolution limit remains a significant drawback. To overcome this issue, it was recently suggested that instead of comparing the network to a random null model, as is done in modularity, it should be compared to a constant factor. However, it is unclear what is meant exactly by "resolution-limit-free", that is, not suffering from the resolution limit. Furthermore, the question remains what other methods could be classified as resolution-limit-free. In this paper we suggest a rigorous definition and derive some basic properties of resolution-limit-free methods. More importantly, we are able to prove exactly which class of community detection methods are resolution-limit-free. Furthermore, we analyze which methods are not resolution-limit-free, suggesting there is only a limited scope for resolution-limit-free community detection methods. Finally, we provide such a natural formulation, and show it performs superbly.

References in corpus (14)

• Fast unfolding of communities in large networks
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Community structure in directed networks
• An information-theoretic framework for resolving community structure in complex networks
• Modularity and community detection in bipartite networks
• Community detection in networks with positive and negative links
• Geographical dispersal of mobile communication networks
• Analysis of the structure of complex networks at different resolution levels
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Limited resolution in complex network community detection with Potts model approach
• Partitioning and modularity of graphs with arbitrary degree distribution
• Note on the equivalence of the label propagation method of community detection and a Potts model approach