Stochastic block model with many communities

The stochastic block model (SBM), a random graph generalizing the Erdős–Rényi model, has long served as a framework for community detection. For SBMs with $n$ vertices and a fixed number of communities $q$, Decelle et al. (2011) predicted that efficient recovery is possible above the Kesten–Stigum (KS) threshold and impossible below it. We review recent advances in proving this conjecture. We then consider the case where $q=q_n$ diverges with $n$, where no prediction exists. We show that the KS threshold can be beaten efficiently when $q_n\gg \sqrt{n}$, whereas low-degree algorithms fail to beat the KS threshold when $q_n\ll \sqrt{n}$.

This is based on joint work with Byron Chin, Elchanan Mossel, and Alex Wein.