Abstract

Recently, it was shown that there is a phase transition in the community detection problem. This transition was first computed using the cavity method, and has been proved rigorously in the case of q= 2 groups. However, analytic calculations using the cavity method are challenging since they require us to understand probability distributions of messages. We study analogous transitions in the so-called" zero-temperature inference" model, where this distribution is supported only on the most likely messages. Furthermore, whenever several messages are equally likely, we break the tie by choosing among them with equal probability, corresponding to an infinitesimal random external field. While the resulting analysis overestimates the thresholds, it reproduces some of the qualitative features of the system. It predicts a first-order detectability transition whenever q> 2 (as opposed to q> 4 according to the finite …

Date

May 21, 2014

Authors

Greg Ver Steeg, Cristopher Moore, Aram Galstyan, Armen Allahverdyan

Journal

Europhysics Letters

Volume

106

Issue

4

Pages

48004

Publisher

IOP Publishing