| Autor: |
Chen PY; Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, Michigan 48109, USA., Hero AO 3rd; Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, Michigan 48109, USA. |
| Jazyk: |
angličtina |
| Zdroj: |
Physical review. E, Statistical, nonlinear, and soft matter physics [Phys Rev E Stat Nonlin Soft Matter Phys] 2015 Mar; Vol. 91 (3), pp. 032804. Date of Electronic Publication: 2015 Mar 06. |
| DOI: |
10.1103/PhysRevE.91.032804 |
| Abstrakt: |
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. |
| Databáze: |
MEDLINE |
| Externí odkaz: |
|
