Allan Sly
2:00 pm, Wednesday, 10th July
Abstract
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.
Joint work with Elchanan Mossel and Youngtak Sohn.
Combinatorics
Princeton University
Wednesday 10 July 2024, 2.00 pm
Room 4082 (Anita B. Lawrence Center)