An Impossibility Result for Reconstruction in a Degree-Corrected Planted-Partition Model
share
We consider a Degree-Corrected Planted-Partition model: a random graph on n nodes with two asymptotically equal-sized clusters. The model parameters are two constants a,b > 0 and an i.i.d. sequence of weights (ϕ_u)_u=1^n, with finite second moment Φ^(2). Vertices u and v are joined by an edge with probability ϕ_u ϕ_v/na when they are in the same class and with probability ϕ_u ϕ_v/nb otherwise. We prove that it is information-theoretically impossible to estimate the spins in a way positively correlated with the true community structure when (a-b)^2 Φ^(2)≤ 2(a+b). A by-product of our proof is a precise coupling-result for local-neighbourhoods in Degree-Corrected Planted-Partition models, which could be of independent interest.
READ FULL TEXT