We develop an information-theoretic view of the stochastic block model, a popular statistical model for the large-scale structure of complex networks. A graph @math from such a model is generated by first assigning vertex labels at random from a finite alphabet, and then connecting vertices with edge probabilities depending on the labels of the endpoints. In the case of the symmetric two-group model, we establish an explicit single-letter' characterization of the per-vertex mutual information between the vertex labels and the graph. The explicit expression of the mutual information is intimately related to estimation-theoretic quantities, and --in particular-- reveals a phase transition at the critical point for community detection. Below the critical point the per-vertex mutual information is asymptotically the same as if edges were independent. Correspondingly, no algorithm can estimate the partition better than random guessing. Conversely, above the threshold, the per-vertex mutual information is strictly smaller than the independent-edges upper bound. In this regime there exists a procedure that estimates the vertex labels better than random guessing.
While this paper was in preparation, Lesieur, Krzakala and Zdborov 'a @cite_0 studied estimation of low-rank matrices observed through noisy memoryless channels. They conjectured that the resulting minimal estimation error is universal across a variety of channel models. Our proof (see Section below) establishes universality across two such models: the Gaussian and the binary output channels. We expect that similar techniques can be useful to prove universality for other models as well.
@cite_0
2605304986
We consider the high-dimensional inference problem where the signal is a low-rank matrix which is corrupted by an additive Gaussian noise. Given a probabilistic model for the low-rank matrix, we compute the limit in the large dimension setting for the mutual information between the signal and the observations, as well as the matrix minimum mean square error, while the rank of the signal remains constant. This allows to locate the information-theoretic threshold for this estimation problem, i.e. the critical value of the signal intensity below which it is impossible to recover the low-rank matrix.