%0 Journal Article %1 Decelle2011Inference %A Decelle, Aurelien %A Krzakala, Florent %A Moore, Cristopher %A Zdeborová, Lenka %D 2011 %I American Physical Society %J Physical Review Letters %K message-passing, stocastic-block-models critical-phenomena communities %N 6 %P 065701+ %R 10.1103/physrevlett.107.065701 %T Inference and Phase Transitions in the Detection of Modules in Sparse Networks %U http://dx.doi.org/10.1103/physrevlett.107.065701 %V 107 %X 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.

@article{Decelle2011Inference, 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.}}, added-at = {2019-06-10T14:53:09.000+0200}, author = {Decelle, Aurelien and Krzakala, Florent and Moore, Cristopher and Zdeborov\'{a}, Lenka}, biburl = {https://www.bibsonomy.org/bibtex/20f423c9dc395d3f498c35f708752c8ff/nonancourt}, citeulike-article-id = {9605915}, citeulike-linkout-0 = {http://dx.doi.org/10.1103/physrevlett.107.065701}, citeulike-linkout-1 = {http://link.aps.org/abstract/PRL/v107/i6/e065701}, citeulike-linkout-2 = {http://link.aps.org/pdf/PRL/v107/i6/e065701}, doi = {10.1103/physrevlett.107.065701}, interhash = {5af38246504449fe565c80d25d24d1a1}, intrahash = {0f423c9dc395d3f498c35f708752c8ff}, issn = {0031-9007}, journal = {Physical Review Letters}, keywords = {message-passing, stocastic-block-models critical-phenomena communities}, month = aug, number = 6, pages = {065701+}, posted-at = {2014-06-05 18:08:13}, priority = {2}, publisher = {American Physical Society}, timestamp = {2019-08-01T16:14:15.000+0200}, title = {{Inference and Phase Transitions in the Detection of Modules in Sparse Networks}}, url = {http://dx.doi.org/10.1103/physrevlett.107.065701}, volume = 107, year = 2011 }