Stochastic Block Models and Reconstruction

Details Stochastic Block Models and Reconstruction Stochastic Block Models and Reconstruction

2012-02-07

arxiv.org/abs/1202.1499v3

Mathematics

Probability

Scientific paper

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).

Affiliated with

Also associated with

No associations

Rating

Stochastic Block Models and Reconstruction does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Stochastic Block Models and Reconstruction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Stochastic Block Models and Reconstruction will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-580182