EAST HALL: *
Cris Moore <http://www.santafe.edu/about/
Professor, Santa Fe Institute
author of The Nature of Computation, published by Oxford University Press
Title: Belief Propagation and Phase Transitions in the Stochastic Block Model
Abstract: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.
