Main content start
Seminar

Stochastic blocks models: Detection and recovery

Speaker
Allan Sly (Princeton)
Date
Mon, Mar 17 2025, 4:00pm
Location
Sequoia 200
red knot logo

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.