Stochastic blocks models: Detection and recovery

The stochastic block model is a canonical model of communities in random graphs. Given a sparse stochastic block model, the two standard inference tasks are:

1. Weak recovery: Can we estimate the communities with non-trivial overlap with the true communities?
2. Detection/hypothesis testing: Can we distinguish if the sample was drawn from the block model or from a random graph with no community structure with probability tending to 1 as the graph size tends to infinity?

We show that the thresholds for these two phenomena coincide and that the two inference tasks are equivalent except possibly at a critical point. In the case of the symmetric models with up to four communities and large average degree, we show that this threshold coincides with the Kesten-Stigum bound.

This is joint work with Elchanan Mossel and Youngtak Sohn.