Universal Phase Transition in Community Detectability under a Stochastic Block Model

Abstract

We prove the existence of an asymptotic phase transition threshold on community detectability for the spectral modularity method [M. E. J. Newman, Phys. Rev. E 74, 036104 (2006) and Proc. National Academy of Sciences. 103, 8577 (2006)] under a stochastic block model. The phase transition on community detectability occurs as the inter-community edge connection probability $p$ grows. This phase transition separates a sub-critical regime of small $p$, where modularity-based community detection successfully identifies the communities, from a super-critical regime of large $p$ where successful community detection is impossible. We show that, as the community sizes become large, the asymptotic phase transition threshold $p^{\ast }$ is equal to $\sqrt{p_1\cdot p_2}$, where $p_i(i=1,2)$ is the within-community edge connection probability. Thus the phase transition threshold is universal in the sense that it does not depend on the ratio of community sizes. The universal phase transition phenomenon is validated by simulations for moderately sized communities. Using the derived expression for the phase transition threshold we propose an empirical method for estimating this threshold from real-world data.

9 pages, 7 figures, to appear in Physical Review E

References in corpus (15)

• Modularity and community structure in networks
• Community detection in graphs
• Finding community structure in networks using the eigenvectors of matrices
• Stochastic blockmodels and community structure in networks
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Spectral redemption: clustering sparse networks
• Phase transition in the detection of modules in sparse networks
• Abrupt transition in the structural formation of interconnected networks
• Graph spectra and the detectability of community structure in networks
• Consistency of community detection in networks under degree-corrected stochastic block models
• Multiresolution community detection for megascale networks by information-based replica correlations
• Eigenvalue Spectra of Modular Networks
• Detectability of communities in heterogeneous networks
• A paradox in community detection
• Comparative Study for Inference of Hidden Classes in Stochastic Block Models

Cited by in corpus (6)

• Phase Transitions in Spectral Community Detection
• Phase Transitions and a Model Order Selection Criterion for Spectral Graph Clustering
• Detectability of the spectral method for sparse graph partitioning
• Revisiting Spectral Graph Clustering with Generative Community Models
• Phase Transitions in Spectral Community Detection of Large Noisy Networks
• Detectability threshold in weighted modular networks