title: 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. Natl. Acad. Sci. (USA) 103, 8577 (2006)] under a stochastic block model. The phase transition on community detectability occurs as the intercommunity edge connection probability p grows. This phase transition separates a subcritical regime of small p, where modularity-based community detection successfully identifies the communities, from a supercritical 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* is equal to √[p1p2], where pi(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.
authors: Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, Michigan 48109, USA.
authors: Pin-Yu
authors: PY
authors: Chen
authors: Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, Michigan 48109, USA.
authors: Alfred O
authors: AO
authors: Hero
mesh_terms: D008962:Models, Theoretical; D044367:Phase Transition; D013269:Stochastic Processes