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: (i) Weak recovery: can we estimate the communities with non-trivial overlap with the true communities? (ii) 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 4 communities and large average degree, we show that this threshold coincides with the Kesten-Stigum bound.

Joint work with Elchanan Mossel and Youngtak Sohn.

You can learn more about Professor Allan Sly here: https://web.math.princeton.edu/~asly/