2015/07/30 by Yash Deshpande, Emmanuel Abbé, Deshpande, Yash +3 · 2 citations
Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Information Theory (cs.IT) #Random Matrices and Applications #Statistical Mechanics (cond-mat.stat-mech) #Statistics Theory (math.ST) #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.1507.08685
openalex publication_date 2015/07/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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. 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.