AN IMPOSSIBILITY RESULT FOR RECONSTRUCTION IN THE DEGREE-CORRECTED STOCHASTIC BLOCK MODEL

• 成果类型: Article
• 署名作者: Gulikers, Lennart; Lelarge, Marc; Massoulie, Laurent
• 署名单位: Institut Polytechnique de Paris; Ecole Polytechnique; Universite PSL; Ecole Normale Superieure (ENS)
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/18-AAP1381
• 发表日期: 2018
• 页码: 3002-3027
• 关键词: Random graphs; degree distributions; trees

摘要

We consider the Degree-Corrected Stochastic Block Model (DC-SBM): a random graph on n nodes, having i.i.d. weights (phi u)(u)(n)=i (possibly heavytailed), partitioned into q >= 2 asymptotically equal-sized clusters. The model parameters are two constants a, b > 0 and the finite second moment of the weights Phi((2)). Vertices u and v are connected by an edge with probability phi u phi v/na when they are in the same class and with probability phi u phi v/nb otherwise. We prove that it is information-theoretically impossible to estimate the clusters in a way positively correlated with the true community structure when (a - b)(2) (Phi)((2)) <= q (a + b). As by-products of our proof we obtain (1) a precise coupling result for local neighbourhoods in DC-SBMs, that we use in Gulikers, Lelarge and Massoulie (2016) to establish a law of large numbers for local-functionals and (2) that long-range interactions are weak in (power-law) DC-SBMs.