Inference and phase transitions in the detection of modules in sparse networks
- PMID: 21902340
- DOI: 10.1103/PhysRevLett.107.065701
Inference and phase transitions in the detection of modules in sparse networks
Abstract
We present an asymptotically exact analysis of the problem of detecting communities in sparse random networks generated by stochastic block models. Using the cavity method of statistical physics and its relationship to belief propagation, we unveil a phase transition from a regime where we can infer the correct group assignments of the nodes to one where these groups are undetectable. Our approach yields an optimal inference algorithm for detecting modules, including both assortative and disassortative functional modules, assessing their significance, and learning the parameters of the underlying block model. Our algorithm is scalable and applicable to real-world networks, as long as they are well described by the block model.
Similar articles
-
Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications.Phys Rev E Stat Nonlin Soft Matter Phys. 2011 Dec;84(6 Pt 2):066106. doi: 10.1103/PhysRevE.84.066106. Epub 2011 Dec 12. Phys Rev E Stat Nonlin Soft Matter Phys. 2011. PMID: 22304154
-
Phase transitions in semisupervised clustering of sparse networks.Phys Rev E Stat Nonlin Soft Matter Phys. 2014 Nov;90(5-1):052802. doi: 10.1103/PhysRevE.90.052802. Epub 2014 Nov 5. Phys Rev E Stat Nonlin Soft Matter Phys. 2014. PMID: 25493829
-
Typology of phase transitions in Bayesian inference problems.Phys Rev E. 2019 Apr;99(4-1):042109. doi: 10.1103/PhysRevE.99.042109. Phys Rev E. 2019. PMID: 31108676
-
Scalable detection of statistically significant communities and hierarchies, using message passing for modularity.Proc Natl Acad Sci U S A. 2014 Dec 23;111(51):18144-9. doi: 10.1073/pnas.1409770111. Epub 2014 Dec 8. Proc Natl Acad Sci U S A. 2014. PMID: 25489096 Free PMC article.
-
Nonparametric Bayesian inference of the microcanonical stochastic block model.Phys Rev E. 2017 Jan;95(1-1):012317. doi: 10.1103/PhysRevE.95.012317. Epub 2017 Jan 17. Phys Rev E. 2017. PMID: 28208453
Cited by
-
The many facets of community detection in complex networks.Appl Netw Sci. 2017;2(1):4. doi: 10.1007/s41109-017-0023-6. Epub 2017 Feb 15. Appl Netw Sci. 2017. PMID: 30533512 Free PMC article.
-
Generalised thresholding of hidden variable network models with scale-free property.Sci Rep. 2019 Aug 2;9(1):11273. doi: 10.1038/s41598-019-47628-0. Sci Rep. 2019. PMID: 31375716 Free PMC article.
-
Stochastic block models: A comparison of variants and inference methods.PLoS One. 2019 Apr 23;14(4):e0215296. doi: 10.1371/journal.pone.0215296. eCollection 2019. PLoS One. 2019. PMID: 31013290 Free PMC article.
-
How modular structure can simplify tasks on networks: parameterizing graph optimization by fast local community detection.Proc Math Phys Eng Sci. 2014 Oct 8;470(2170):20140224. doi: 10.1098/rspa.2014.0224. Proc Math Phys Eng Sci. 2014. PMID: 25294962 Free PMC article.
-
Critical analysis of (Quasi-)Surprise for community detection in complex networks.Sci Rep. 2018 Sep 27;8(1):14459. doi: 10.1038/s41598-018-32582-0. Sci Rep. 2018. PMID: 30262896 Free PMC article.
LinkOut - more resources
Full Text Sources
