Seminar Series: Belief Propagation and Phase Transitions in the Stochastic Block Model

The stochastic block model is a popular model of social and biological networks.  It generalizes the Erdos-Renyi model by assigning each vertex to one of k groups, and having the probability of an edge depend on the groups to which its endpoints belong.  It allows both "assortative" communities where vertices are more likely to connect to others of the same, and "disassortative" and directed community structures, like those in food webs, where predators form a community because they feed on similar prey.  Given a graph, we would like to infer the most likely block model: both the group assignment of the nodes, and the parameters of the model.  Recently, we gave an efficient algorithm for this problem based on belief propagation.  In the sparse case, this algorithm appears to work (with some caveats) in nearly-linear time.  

I will give an accessible explanation of this algorithm, including its connections with the cavity method of statistical physics.  I will also discuss a phase transition in the detectability of communities, that we conjectured on the basis of the Kesten-Stigum bound, and that was recently proved by Mossel, Neeman, and Sly.  If time permits, I will discuss other phase transitions in this model, such as in semisupervised learning where we are given the correct group labels for a certain fraction of the vertices, and some recent work on spectral algorithms for sparse networks.

This is joint work with Aurelien Decelle, Florent Krzakala, Lenka Zdeborova, and Pan Zhang.