Fetching the paper…

Reading the bibliography…

2013

Community detection thresholds and the weak Ramanujan property

Massoulie, Laurent

Original
PDF
Post on X

Understand

Decelle et al.\cite{Decelle11} conjectured the existence of a sharp threshold for community detection in sparse random graphs drawn from the stochastic block model.

Mossel et al.\cite{Mossel12} established the negative part of the conjecture, proving impossibility of meaningful detection below the threshold.
However the positive part of the conjecture remained elusive so far.
Here we solve the positive part of the conjecture.

Community detection thresholds and the weak Ramanujan property · Around

Built on

S. L. Paul W. Holland, Kathryn Blackmond Laskey, “Stochastic blockmodels: First steps,” Social Networks , vol. 5, no. 2, pp. 109–137, 1983
1983
Earlier work this paper cites.
D. Williams, Probability with martingales . Cambridge University Press, 1991
Original
1991
Earlier work this paper cites.
W. Evans, C. Kenyon, Y. Peres, and L. Schulman, “Broadcasting on trees and the ising model,” pp. 410–433, 2000
2000
Earlier work this paper cites.

Similar

U. Feige and E. Ofek, “Spectral techniques applied to sparse random graphs,” Random Struct. Algorithms , vol. 27, no. 2, pp. 251–275, Sept. 2005. [Online]. Available: http://dx.doi.org/10.1002/rsa.v27:2
2005
Cited alongside, same era.
J. Friedman, “A proof of alon’s second eigenvalue conjecture and related problem,” Mem. Amer. Math. Soc. , no. 910., 2008
2008
Cited alongside, same era.
A. Coja-oghlan, “Graph partitioning via adaptive spectral techniques,” Comb. Probab. Comput. , vol. 19, no. 2, pp. 227–284, 2010. [Online]. Available: http://dx.doi.org/10.1017/S0963548309990514
2010
Cited alongside, same era.

Then

A. Decelle, F. Krzakala, C. Moore, and L. Zdeborova, “Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications,” Physics Review E , vol. 84:066106, 2011
2011
Later among the works it cites.
E. Mossel, J. Neeman, and A. Sly, “Stochastic block models and reconstruction,” Feb. 2012, available at: http://arxiv.org/abs/1202.1499
Original
2012
Later among the works it cites.
S. Heimlicher, M. Lelarge, and L. Massoulié, “Community detection in the labelled stochastic block model,” Nov. 2012, avaiable at: http://arxiv.org/abs/1209.2910
Original
2012
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…