Speaker: Youngtak Sohn (Brown)

Title: Stochastic Block Model with Many Communities

Abstract:

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 progress toward proving this conjecture. We then turn to the case where $q = q_n$ grows with $n$, a setting for which no prediction currently exists. We show that the KS threshold can be surpassed efficiently when $q_n \gg \sqrt{n}$, while low-degree algorithms fail to beat the KS threshold when $q_n \ll \sqrt{n}$. Based on joint work with Byron Chin, Elchanan Mossel, and Alex Wein.