The ACO Seminar (2024–2025)

The stochastic block model is a canonical model of communities in random graphs. It was introduced in the social sciences and statistics as a model of communities, and in theoretical computer science as an average case model for graph partitioning problems under the name of the “planted partition model.” 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?

I will discuss recent results with Allan Sly and Youngtak Sohn showing that for sparse stochastic block models, the two inference tasks are equivalent except possibly at a critical point.