Fetching the paper…
Reading the bibliography…
We consider the problem of reconstructing sparse symmetric block models with two blocks and connection probabilities $a/n$ and $b/n$ for inter- and intra-block edge probabilities, respectively.
Kesten, H.H. andStigum, B. P.B. P. (1966). Additional limit theorems for indecomposable multidimensional Galton–Watson processes. Ann. Math. Statist. 37 1463–1481
1966
Earlier work this paper cites.
Holland, Paul W.P. W., Laskey, Kathryn BlackmondK. B. andLeinhardt, SamuelS. (1983). Stochastic blockmodels: First steps. Social Networks 5 109–137
1983
Earlier work this paper cites.
Boppana, R. B.R. B. (1987). Eigenvalues and graph bisection: An average-case analysis. In 28th Annual Symposium on Foundations of Computer Science 280–285. IEEE, Los Angeles, CA
1987
Earlier work this paper cites.
Bui, T. N.T. N., Chaudhuri, S.S., Leighton, F. T.F. T. andSipser, M.M. (1987). Graph bisection algorithms with good average case behavior. Combinatorica 7 171–191
1987
Earlier work this paper cites.
Dyer, M. E.M. E. andFrieze, A. M.A. M. (1989). The solution of some random NP-hard problems in polynomial expected time. J. Algorithms 10 451–489
1989
Earlier work this paper cites.
Bleher, P. M.P. M., Ruiz, J.J. andZagrebnov, V. A.V. A. (1995). On the purity of the limiting Gibbs state for the Ising model on the Bethe lattice. J. Stat. Phys. 79 473–482
1995
Earlier work this paper cites.
Blum, AvrimA. andSpencer, JoelJ. (1995). Coloring random and semi-random k k -colorable graphs. J. Algorithms 19 204–234
1995
Earlier work this paper cites.
Alon, NogaN. andKahale, NabilN. (1997). A spectral technique for coloring random 3 3 -colorable graphs. SIAM J. Comput. 26 1733–1748
1997
Earlier work this paper cites.
Snijders, Tom A. B.T. A. B. andNowicki, KrzysztofK. (1997). Estimation and prediction for stochastic blockmodels for graphs with latent block structure. J. Classification 14 75–100
1997
Earlier work this paper cites.
Jerrum, MarkM. andSorkin, Gregory B.G. B. (1998). The Metropolis algorithm for graph bisection. Discrete Appl. Math. 82 155–175
1998
Earlier work this paper cites.
Evans, WilliamW., Kenyon, ClaireC., Peres, YuvalY. andSchulman, Leonard J.L. J. (2000). Broadcasting on trees and the Ising model. Ann. Appl. Probab. 10 410–433
2000
Cited alongside, same era.
Condon, AnneA. andKarp, Richard M.R. M. (2001). Algorithms for graph partitioning on the planted partition model. Random Structures Algorithms 18 116–140
2001
Cited alongside, same era.
McSherry, FrankF. (2001). Spectral partitioning of random graphs. In 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001) 529–537. IEEE Computer Soc., Los Alamitos, CA
2001
Cited alongside, same era.
Strogatz, S. H.S. H. (2001). Exploring complex networks. Nature 410 268–276
2001
Cited alongside, same era.
Janson, SvanteS. andMossel, ElchananE. (2004). Robust reconstruction on trees is determined by the second eigenvalue. Ann. Probab. 32 2630–2649
Decelle, A.A., Krzakala, F.F., Moore, C.C. andZdeborová, L.L. (2011). Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Physics Review E 84 066106
2011
Later among the works it cites.
Sly, AllanA. (2011). Reconstruction for the Potts model. Ann. Probab. 39 1365–1406
2011
Later among the works it cites.
Montanari, AndreaA., Mossel, ElchananE. andSly, AllanA. (2012). The weak limit of Ising models on locally tree-like graphs. Probab. Theory Related Fields 152 31–51
2012
Later among the works it cites.
Krzakala, FlorentF., Moore, CristopherC., Mossel, ElchananE., Neeman, JoeJ., Sly, AllanA., Zdeborová, LenkaL. andZhang, PanP. (2013). Spectral redemption in clustering sparse networks. Proc. Natl. Acad. Sci. USA 110 20935–20940
2013
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
2004
Cited alongside, same era.
Borgs, C.C., Chayes, J.J., Mossel, E.E. andRoch, S.S. (2006). The Kesten–Stigum reconstruction bound is tight for roughly symmetric binary channels. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06) 518–530
2006
Cited alongside, same era.
Leskovec, J.J., Lang, K. J.K. J., Dasgupta, A.A. andMahoney, M. W.M. W. (2008). Statistical properties of community structure in large social and information networks. In Proceeding of the 17th International Conference on World Wide Web 695–704. ACM, New York
2008
Cited alongside, same era.
Bickel, P. J.P. J. andChen, A.A. (2009). A nonparametric view of network models and Newman–Girvan and other modularities. Proc. Natl. Acad. Sci. USA 106 21068–21073
2009
Cited alongside, same era.
Coja-Oghlan, AminA. (2010). Graph partitioning via adaptive spectral techniques. Combin. Probab. Comput. 19 227–284
2010
Cited alongside, same era.
2014
Closest in time.
Mossel, E.E., Neeman, J.J. andSly, A.A. (2014). Belief propagation, robust reconstruction, and optimal recovery of block models (extended abstract), vol. 35. In JMLR Workshop and Conference Proceedings (COLT Proceedings) 1–35. Barcelona, Spain
2014
Closest in time.
2015
Closest in time.
Mossel, ElchananE., Neeman, JoeJ. andSly, AllanA. (2015). Reconstruction and estimation in the planted partition model. Probab. Theory Related Fields 162 431–461
2015
Closest in time.
Lyons, RussellR. andPeres, YuvalY. (2016). Probability on Trees and Networks. Cambridge Univ. Press, Cambridge. Available at \surl
2016
Closest in time.