Detectability of communities in heterogeneous networks

Abstract

Communities are fundamental entities for the characterization of the structure of real networks. The standard approach to the identification of communities in networks is based on the optimization of a quality function known as "modularity". Although modularity has been at the center of an intense research activity and many methods for its maximization have been proposed, not much it is yet known about the necessary conditions that communities need to satisfy in order to be detectable with modularity maximization methods. Here, we develop a simple theory to establish these conditions, and we successfully apply it to various classes of network models. Our main result is that heterogeneity in the degree distribution helps modularity to correctly recover the community structure of a network and that, in the realistic case of scale-free networks with degree exponent $\gamma <2.5$, modularity is always able to detect the presence of communities.

6 pages, 5 figures, accepted for publication in Physical Review E

References in corpus (5)

• Modularity and community structure in networks
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Phase transition in the detection of modules in sparse networks
• Graph spectra and the detectability of community structure in networks

Cited by in corpus (24)

• Detecting communities using asymptotical Surprise
• Enhanced detectability of community structure in multilayer networks through layer aggregation
• Eigenvalue Spectra of Modular Networks
• Phase Transitions in Spectral Community Detection
• Community Detection in Quantum Complex Networks
• A paradox in community detection
• Super-resolution community detection for layer-aggregated multilayer networks
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• Universal Phase Transition in Community Detectability under a Stochastic Block Model
• Walk modularity and community structure in networks
• Detectability of the spectral method for sparse graph partitioning
• Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection
• Decoding communities in networks
• Detectability thresholds of general modular graphs
• Spectral partitioning in equitable graphs
• Uncovering Complex Overlapping Pattern of Communities in Large-scale Social Networks
• Comprehensive spectral approach for community structure analysis on complex networks
• Stochastic fluctuations and the detectability limit of network communities
• Revisiting Spectral Graph Clustering with Generative Community Models
• Router-level community structure of the Internet Autonomous Systems
• Phase Transitions in Spectral Community Detection of Large Noisy Networks
• Non-backtracking walks reveal compartments in sparse chromatin interaction networks
• Detectability threshold in weighted modular networks
• Error-Correcting Decoders for Communities in Networks