TY - GEN

T1 - Asymptotic mutual information for the binary stochastic block model

AU - Deshpande, Yash

AU - Abbe, Emmanuel

AU - Montanari, Andrea

N1 - Funding Information:
Y.D. and A.M. were partially supported by NSF grants CCF-1319979 and DMS-11 06627 and the AFOSR grant FA9550-13-1-0036. E.A. was partially supported by NSF CAREER Award CCF-1552131. Part of this work was done while the authors were visiting Simons Institute for the Theory of Computing, UC Berkeley
Publisher Copyright:
© 2016 IEEE.
Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.

PY - 2016/8/10

Y1 - 2016/8/10

N2 - 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 G 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, when the graph average degree diverges. 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 of the vertex labels. 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.

AB - 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 G 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, when the graph average degree diverges. 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 of the vertex labels. 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.

UR - http://www.scopus.com/inward/record.url?scp=84985919237&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84985919237&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2016.7541286

DO - 10.1109/ISIT.2016.7541286

M3 - Conference contribution

AN - SCOPUS:84985919237

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 185

EP - 189

BT - Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2016 IEEE International Symposium on Information Theory, ISIT 2016

Y2 - 10 July 2016 through 15 July 2016

ER -