Monday, December 04, 2017 at 4:15pm to 5:15pm
Yash Deshpande (MIT)
Title: An information-theoretic analysis of the stochastic block model
The stochastic block model is a popular model for large networks with latent clustered structure. Over the last few years, there has been significant interest in the statistical, computational and robustness aspects of the stochastic block model. In particular, insights from statistical physics have been particularly instrumental in spurring this interest and providing sharp predictions via non-rigorous methods. In this talk, we will consider information-theoretic view of the simplest stochastic block model and rigorously establish much of the picture provided by statistical physics, in a certain ‘diverging degree’ limit. We will also show how information-theoretic quantities are intimately related with fundamental limits in estimation.
The analysis proceeds by a universality argument reducing the stochastic block models to (possibly more) familiar low-rank perturbations of GOE matrices. This is established through the classical Lindeberg swapping trick. Thanks to the Gaussian structure, the low-rank perturbed models are then amenable to a variety of analysis methods. We will take an algorithmic route using a particular ‘approximate message passing’ scheme to establish the final result.
Joint work with Emmanuel Abbe and Andrea Montanari.