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.

Speaker

Allan Sly 

Research area

Combinatorics

Affilation

Princeton University

Date

Wednesday 10 July 2024, 2.00 pm

Location

Room 4082 (Anita B. Lawrence Center)