Format

Send to

Choose Destination
Phys Rev Lett. 2011 Aug 5;107(6):065701. Epub 2011 Aug 2.

Inference and phase transitions in the detection of modules in sparse networks.

Author information

1
Université Paris-Sud, LPTMS, UMR, Orsay, France.

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.

Supplemental Content

Full text links

Icon for American Physical Society
Loading ...
Support Center