2015

How Robust are Reconstruction Thresholds for Community Detection?

Moitra, Ankur, Perry, William, Wein, Alexander S.

Understand

The stochastic block model is one of the oldest and most ubiquitous models for studying clustering and community detection.

In an exciting sequence of developments, motivated by deep but non-rigorous ideas from statistical physics, Decelle et al.
conjectured a sharp threshold for when community detection is possible in the sparse regime.
Mossel, Neeman and Sly and Massoulie proved the conjecture and gave matching algorithms and lower bounds.

Built on

A Limit Theorem for Multidimensional Galton-Watson Processes
H. Kesten and B. P. Stigum · 1966
Earlier work this paper cites.
Stochastic blockmodels: First steps
P. W. Holland, K. B. Laskey, and S. Leinhardt · 1983
Earlier work this paper cites.
Graph bisection algorithms with good average case behavior
T. N. Bui, S. Chaudhuri, F. T. Leighton, and M. Sipser · 1987
Earlier work this paper cites.
Eigenvalues and graph bisection: An average-case analysis
R. B. Boppana · 1987
Earlier work this paper cites.
Coloring random and semi-random k-colorable graphs
A. Blum and J. Spencer · 1995
Earlier work this paper cites.
The metropolis algorithm for graph bisection
M. Jerrum and G. B. Sorkin · 1998
Earlier work this paper cites.
Recursive reconstruction on periodic trees
E. Mossel · 1998
Earlier work this paper cites.
The probabilistic method
N. Alon and J. H. Spencer · 2000
Earlier work this paper cites.
Broadcasting on trees and the Ising model
W. Evans, C. Kenyon, Y. Peres, and L. J. Schulman · 2000
Earlier work this paper cites.
Finding and certifying a large hidden clique in a semirandom graph
U. Feige and R. Krauthgamer · 2000
Earlier work this paper cites.
Heuristics for semirandom graph problems
U. Feige and J. Kilian · 2001
Earlier work this paper cites.
Spectral partitioning of random graphs
F. McSherry · 2001
Earlier work this paper cites.

Similar

Survey: Information flow on trees
E. Mossel · 2004
Cited alongside, same era.
Reconstruction on Trees and Spin Glass Transition
M. Mézard and A. Montanari · 2005
Cited alongside, same era.
The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels
C. Borgs, J. Chayes, E. Mossel, and S. Roch · 2006
Cited alongside, same era.
Statistical properties of community structure in large social and information networks
J. Leskovec, K. J. Lang, A. Dasgupta, and M. W. Mahoney · 2008
Cited alongside, same era.
Correlation clustering with noisy input
C. Mathieu and W. Schudy · 2010
Cited alongside, same era.
Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
A. Decelle, F. Krzakala, C. Moore, and L. Zdeborová · 2011
Cited alongside, same era.
How to play unique games against a semi-random adversary: Study of semi-random models of unique games
A. Kolla, K. Makarychev, and Y. Makarychev · 2011
Cited alongside, same era.
Reconstruction for the Potts model
A. Sly · 2011
Cited alongside, same era.
Approximation algorithms for semi-random partitioning problems
K. Makarychev, Y. Makarychev, and A. Vijayaraghavan · 2012
Cited alongside, same era.
A Proof Of The Block Model Threshold Conjecture
Original
E. Mossel, J. Neeman, and A. Sly · 2013
Cited alongside, same era.
On semidefinite relaxations for the block model
Original
A. A. Amini and E. Levina · 2014
Cited alongside, same era.
Community detection thresholds and the weak Ramanujan property
L. Massoulié · 2014
Cited alongside, same era.

Then

Belief propagation, robust reconstruction and optimal recovery of block models
E. Mossel, J. Neeman, and A. Sly · 2014
Later among the works it cites.
Reconstruction and estimation in the planted partition model
E. Mossel, J. Neeman, and A. Sly · 2014
Later among the works it cites.
Exact recovery in the stochastic block model
E. Abbe, A. S. Bandeira, and G. Hall · 2015
Closest in time.
Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms
E. Abbe and C. Sandon · 2015
Closest in time.
Community detection in sparse networks via Grothendieck’s inequality
O. Guédon and R. Vershynin · 2015
Closest in time.
Achieving exact cluster recovery threshold via semidefinite programming
B. Hajek, Y. Wu, and J. Xu · 2015
Closest in time.
Phase Transitions in Semidefinite Relaxations
Original
A. Javanmard, A. Montanari, and F. Ricci-Tersenghi · 2015
Closest in time.
Correlation clustering with noisy partial information
K. Makarychev, Y. Makarychev, and A. Vijayaraghavan · 2015
Closest in time.
Learning communities in the presence of errors
Original
K. Makarychev, Y. Makarychev, and A. Vijayaraghavan · 2015
Closest in time.
Semidefinite Programs on Sparse Random Graphs
Original
A. Montanari and S. Sen · 2015
Closest in time.
A semidefinite program for unbalanced multisection in the stochastic block model
Original
W. Perry and A. S. Wein · 2015
Closest in time.

Beyond the bibliography

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

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…