Probabilitas Series: Allan Sly

The Probabilitas Seminar series focuses on high-dimensional problems that combine statistics, probability, information theory, computer science, and other related fields. The upcoming seminar takes place on Friday, March 8, from 10:30-11:30am EST. The talk will be hybrid, both in-person in Science Center 316 and on Zoom (please contact the department for Zoom information). This week's guest will be Allan Sly of the Princeton University Mathematics Department.

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