Asymptotic Mutual Information for the Two-Groups Stochastic Block Model
作者： Yash Deshpande , Emmanuel Abbe , Andrea Montanari
DOI:
关键词: Stochastic block model 、 Variation of information 、 Mutual information 、 Mathematics 、 Statistical model 、 Interaction information 、 Discrete mathematics 、 Upper and lower bounds 、 Pointwise mutual information 、 Vertex (geometry) 、 Combinatorics
摘要: We develop an information-theoretic view of the stochastic block model, a popular statistical model for large-scale structure complex networks. A graph $G$ from such is generated by first assigning vertex labels at random finite alphabet, and then connecting vertices with edge probabilities depending on endpoints. In case symmetric two-group we establish explicit `single-letter' characterization per-vertex mutual information between graph. The expression intimately related to estimation-theoretic quantities, --in particular-- reveals phase transition critical point community detection. Below asymptotically same as if edges were independent. Correspondingly, no algorithm can estimate partition better than guessing. Conversely, above threshold, strictly smaller independent-edges upper bound. this regime there exists procedure that estimates
arxiv.org
harvard.edu参考文章(55)
Laurent Massoulié, Marc Lelarge, Jiaming Xu, Edge Label Inference in Generalized Stochastic Block Models: from Spectral Theory to Impossibility Results arXiv: Statistics Theory. ,(2014)
Ofer Zeitouni, Greg W. Anderson, Alice Guionnet, An Introduction to Random Matrices ,(2009)
Van Vu, A simple SVD algorithm for finding hidden partitions arXiv: Combinatorics. ,(2014)
Alexandre Proutière, Se-Young Yun, Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms. arXiv: Social and Information Networks. ,(2014)
Afonso S. Bandeira, Emmanuel Abbe, Georgina Hall, Exact Recovery in the Stochastic Block Model arXiv: Social and Information Networks. ,(2014)
Afonso S. Bandeira, Random Laplacian matrices and convex relaxations arXiv: Probability. ,(2015)
F. McSherry, Spectral partitioning of random graphs international conference on cluster computing. pp. 529- 537 ,(2001) , 10.1109/SFCS.2001.959929
Laurent Massoulié, Marc Lelarge, Simon Heimlicher, Community Detection in the Labelled Stochastic Block Model arXiv: Social and Information Networks. ,(2012)
Andrea Montanari, Finding One Community in a Sparse Graph arXiv: Machine Learning. ,(2015) , 10.1007/S10955-015-1338-2
Tim Roughgarden, Amir Globerson, Cafer Yildirim, David A. Sontag, Tight Error Bounds for Structured Prediction arXiv: Learning. ,(2014)