Mutual information for the sparse stochastic block model
In this talk, we consider the problem of recovering the community structure in the stochastic block model with two communities. We aim to describe the mutual information between the observed network and the actual community structure in the sparse regime, where the total number of nodes diverges while the average degree of a given node remains bounded. The main result will be a conjecture for the limit of this quantity, and a proof that this conjectured limit provides a lower bound for the asymptotic mutual information. In the case when links across communities are more likely than links within communities, the asymptotic mutual information is known to be given by a variational formula. We also show that our conjectured limit coincides with this formula in this case. This is based on joint work with Jean-Christophe Mourrat.