The Cavity Method, Belief Propagation, and Phase Transitions in Community Detection

The stochastic block model is a popular model of social and biological networks. Each vertex belongs to one of k groups, and the probability of an edge depends on the groups to which its endpoints belong. It allows both ``assortative'' communities where vertices tend to connect to others in the same group, and ``disassortative'' and directed community structures, like those in food webs, where predators form a community because they feed on similar prey. Given a network, we would like to infer the most likely block model: both the group labels of the nodes, and the parameters of the model. I will describe an efficient algorithm for this problem based on belief propagation, or equivalently the cavity method of statistical physics. Physically, the model corresponds to a generalized Potts model with strong interactions on the links of the network, and weak interactions along the non-links. Our analysis also reveals phase transitions in the detectability of communities, including an undetectable phase where no algorithm can do better than chance. There is also a regime where the accuracy we can achieve jumps discontinuously as a function of the fraction of nodes we have prior information about, and a tricritical point where this discontinuity disappears. This is joint work with Aurelien Decelle, Florent Krzakala, Lenka Zdeborov\'a, and Pan Zhang.