1202.1499 (Elchanan Mossel et al.)

Stochastic Block Models and Reconstruction    [PDF]

Elchanan Mossel, Joe Neeman, Allan Sly

Consider the following {\em stochastic block model} of a random graph
consisting of two clusters of size approximately n/2. The cross-class edge
probability is a/n and the within-class probability is b/n. Decelle et al.
conjectured a threshold for the algorithmic problem of reconstructing the
hidden labels in a way that is correlated with the true partition. Their
conjecture is that the threshold is (a - b)^2 = 2(a + b) which is exactly the
threshold for the corresponding reconstruction problem on trees.
We prove one side of this conjecture, i.e., that reconstruction is impossible
when (a - b)^2 is at most 2(a + b). Moreover, we show that the stochastic block
model is contiguous to an Erd\"os-Renyi model when (a - b)^2 < 2(a+b) and
orthogonal to it when (a - b)^2 > 2(a+b).

View original: http://arxiv.org/abs/1202.1499