Fetching the paper…
Reading the bibliography…
The planted bisection model is a random graph model in which the nodes are divided into two equal-sized communities and then edges are added randomly in a way that depends on the community membership.
A lower bound for the critical probability in a certain percolation process
Theodore E. Harris · 1960
Earlier work this paper cites.
On the strength of connectedness of a random graph
Paul Erdős and Alfréd Rényi · 1961
Earlier work this paper cites.
Reducibility among combinatorial problems
R. Karp · 1972
Earlier work this paper cites.
Stochastic blockmodels: First steps
P.W. Holland, K.B. Laskey, and S. Leinhardt · 1983
Earlier work this paper cites.
Limit distribution for the existence of hamiltonian cycles in a random graph
János Komlós and Endre Szemerédi · 1983
Earlier work this paper cites.
Eigenvalues and graph bisection: An average-case analysis
R.B. Boppana · 1987
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.
The solution of some random NP-hard problems in polynomial expected time
M.E. Dyer and A.M. Frieze · 1989
Earlier work this paper cites.
The Metropolis algorithm for graph bisection
M. Jerrum and G.B. Sorkin · 1998
Earlier work this paper cites.
The expected norm of random matrices
Yoav Seginer · 2000
Cited alongside, same era.
Hill-climbing finds random planted bisections
T. Carson and R. Impagliazzo · 2001
Cited alongside, same era.
Algorithms for graph partitioning on the planted partition model
A. Condon and R.M. Karp · 2001
Cited alongside, same era.
Spectral partitioning of random graphs
F. McSherry · 2001
Cited alongside, same era.
Spectral norm of random matrices
Van H. Vu · 2007
Cited alongside, same era.
A nonparametric view of network models and Newman-Girvan and other modularities
P.J. Bickel and A. Chen · 2009
Cited alongside, same era.
Graph partitioning via adaptive spectral techniques
Graph spectra and the detectability of community structure in networks
Raj Rao Nadakuditi and Mark EJ Newman · 2012
Later among the works it cites.
Pseudo-likelihood methods for community detection in large sparse networks
Arash A. Amini, Aiyou Chen, Peter J. Bickel, and Elizaveta Levina · 2013
Later among the works it cites.
Constant factor approximation for balanced cut in the pie model
Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan · 2014
Closest in time.
Community detection thresholds and the weak ramanujan property
Laurent Massoulié · 2014
Closest in time.
Belief propagation, robust reconstruction, and optimal recovery of block models (extended abstract)
E. Mossel, J. Neeman, and A. Sly · 2014
Closest in time.
Stochastic block models and reconstruction
E. Mossel, J. Neeman, and A. Sly · 2014
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
A. Coja-Oghlan · 2010
Cited alongside, same era.
Clustering with spectral norm and the k-means algorithm
Amit Kumar and Ravindran Kannan · 2010
Cited alongside, same era.
Approximation algorithms for semi-random partitioning problems
Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan · 2012
Cited alongside, same era.
Exact recovery in the stochastic block model
E. Abbe, A. S. Bandeira, and G. Hall
Cited in the paper.
Closest in time.
A proof of the block model threshold conjecture
Elchanan Mossel, Joe Neeman, and Allan Sly · 2014
Closest in time.
Community detection via random and adaptive sampling
Se-Young Yun and Alexandre Proutiere · 2014
Closest in time.