Inference and Phase Transitions in the Detection of Modules in Sparse Networks

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.

Figure 1

Learning for $q=2$ groups with $n_a=1/2$, average degree $c=3$, and $ϵ=c_{\mathrm{out}}/c_{\mathrm{in}}=0.15$. If we initialize our algorithm in the ordered region, i.e., with ${ϵ}_0<0.37$, it infers the correct value of $ϵ$. Inset: The free energy as a function of $ϵ$. Note the minimum at $ϵ=0.15$ and the paramagnetic region for $ϵ>0.37$.

Figure 2

The best possible overlap between the inferred and true group assignments. Left: Community detection with $q=2$, $c=3$, and different values of $ϵ=c_{\mathrm{out}}/c_{\mathrm{in}}$. A continuous phase transition between a detectable and a nondetectable phase arises at the critical point ${ϵ}_s$ given by (4). Middle: The 4-group community detection benchmark of Ref. 9 with $c=16$, with the same phenomenology. The number of BP iterations needed for convergence is a constant with respect to $N$ and diverges at the critical point. The results agree well with MC simulations, except very close to the critical point where finite-size effects are stronger. Right: A planted coloring problem with $q=5$ and $c_{\mathrm{in}}=0$, $c=c_{\mathrm{out}}(1-1/q)$. Both the ordered fixed point (green $+$’s, obtained by initializing in the actual group assignment) and the paramagnetic one (blue $\times$’s, obtained by initializing the algorithm in a random configuration) exist between $c_d$ and $c_s$. The difference $\Delta f$ (red) between the paramagnetic and ordered free energies shows that modules are, in principle, detectable as soon as $c>c_c$ when $\Delta f>0$. In practice, it is exponentially hard to find the corresponding fixed point, and detection becomes feasible only after the phase transition point $c_s$ given by (4).