An impossibility result for reconstruction in the degree-corrected stochastic block model

We consider the Degree-Corrected Stochastic Block Model (DC-SBM): a random graph on n nodes, having i.i.d. weights (.u)nu=1 (possibly heavy-tailed), 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 .(2).Vertices u are connected by an edge with probability .u.vna when they are in the same class and with probability .u.vnb 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.(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 Massoulié (2016) to establish a law of large numbers for local-functionals and (2)that long-range interactions are weak in (power-law) DC-SBMs.