Fetching the paper…
Reading the bibliography…
Resolving a conjecture of Abbe, Bandeira and Hall, the authors have recently shown that the semidefinite programming (SDP) relaxation of the maximum likelihood estimator achieves the sharp threshold for exactly recovering the community structure under the binary stochastic block model of two equal-sized clusters.
On random graphs, I
P. Erdös and A. Rényi · 1959
Earlier work this paper cites.
Information Theory
R. B. Ash · 1965
Earlier work this paper cites.
Stochastic blockmodels: First steps
P. W. Holland, K. B. Laskey, and S. Leinhardt · 1983
Earlier work this paper cites.
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
M. X. Goemans and D. P. Williamson · 1995
Earlier work this paper cites.
Improved approximation algorithms for MAX k k -CUT and MAX BISECTION
A. Frieze and M. Jerrum · 1997
Earlier work this paper cites.
The expected norm of random matrices
Y. Seginer · 2000
Earlier work this paper cites.
Algorithms for graph partitioning on the planted partition model
A. Condon and R. M. Karp · 2001
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.
Probability and Computing: Randomized Algorithms and Probabilistic Analysis
M. Mitzenmacher and E. Upfal · 2005
Earlier work this paper cites.
Nuclear norm minimization for the planted clique and biclique problems
B. P. Ames and S. A. Vavasis · 2011
Earlier work this paper cites.
Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
A. Decelle, F. Krzakala, C. Moore, and L. Zdeborova · 2011
Earlier work this paper cites.
Finding dense clusters via “Low Rank+ Sparse” decomposition
S. Oymak and B. Hassibi · 2011
Earlier work this paper cites.
Improved graph clustering
Y. Chen, S. Sanghavi, and H. Xu · 2012
Earlier work this paper cites.
Community detection in the labelled stochastic block model
S. Heimlicher, M. Lelarge, and L. Massoulié · 2012
Earlier work this paper cites.
Topics in random matrix theory
T. Tao · 2012
Cited alongside, same era.
Robust convex relaxation for the planted clique and densest k-subgraph problems
B. Ames · 2013
Cited alongside, same era.
Community detection thresholds and the weak ramanujan property
L. Massoulié · 2013
Cited alongside, same era.
A proof of the block model threshold conjecture
E. Mossel, J. Neeman, and A. Sly · 2013
Cited alongside, same era.
Decoding binary node labels from censored edge measurements: Phase transition and efficient recovery
E. Abbe, A. Bandeira, A. Bracher, and A. Singer · 2014
Cited alongside, same era.
Convex optimization for the planted k-disjoint-clique problem
Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms
E. Abbe and C. Sandon · 2015
Closest in time.
Multisection in the stochastic block model using semidefinite programming
N. Agarwal, A. S. Bandeira, K. Koiliaris, and A. Kolla · 2015
Closest in time.
Random Laplacian matrices and convex relaxations
A. Bandeira · 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 under the stochastic block model
B. Hajek, Y. Wu, and J. Xu · 2015
Closest in time.
Exact recovery threshold in the binary censored block model
B. Hajek, Y. Wu, and J. Xu · 2015
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
B. P. W. Ames and S. Vavasis · 2014
Cited alongside, same era.
On semidefinite relaxations for the block model
A. A. Amini and E. Levina · 2014
Cited alongside, same era.
Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
T. Cai and X. Li · 2014
Cited alongside, same era.
Clustering partially observed graphs via convex optimization
Y. Chen, A. Jalali, S. Sanghavi, and H. Xu · 2014
Cited alongside, same era.
Y. Chen and J. Xu · 2014
Cited alongside, same era.
Achieving exact cluster recovery threshold via semidefinite programming
B. Hajek, Y. Wu, and J. Xu · 2014
Cited alongside, same era.
Graph clustering with missing data: Convex algorithms and analysis
R. K. Vinayak, S. Oymak, and B. Hassibi · 2014
Cited alongside, same era.
Closest in time.
Reconstruction in the labeled stochastic block model
M. Lelarge, L. Massoulié, and J. Xu · 2015
Closest in time.
Semidefinite programs on sparse random graphs
A. Montanari and S. Sen · 2015
Closest in time.
Consistency thresholds for the planted bisection model
E. Mossel, J. Neeman, and A. Sly · 2015
Closest in time.
Reconstruction and estimation in the planted partition model
E. Mossel, J. Neeman, and A. Sly · 2015
Closest in time.
A semidefinite program for unbalanced multisection in the stochastic block model
W. Perry and A. Wein · 2015
Closest in time.
Spectral detection in the censored block model
A. Saade, F. Krzakala, M. Lelarge, and L. Zdeborova · 2015
Closest in time.
Exact recovery in the stochastic block model
E. Abbe, A. S. Bandeira, and G. Hall · 2016
Closest in time.
Semidefinite programs for exact recovery of a hidden community
B. Hajek, Y. Wu, and J. Xu · 2016
Closest in time.