Fetching the paper…
Reading the bibliography…
In a paper that initiated the modern study of the stochastic block model, Decelle et al., backed by Mossel et al., made the following conjecture: Denote by $k$ the number of balanced communities, $a/n$ the probability of connecting inside communities and $b/n$ across, and set $\mathrm{SNR}=(a-b)^2/(k(a+(k-1)b)$; for any $k \geq 2$, it is possible to detect communities efficiently whenever $\mathrm{SNR}>1$ (the KS threshold), whereas for $k\geq 4$, it is possible to detect communities information-theoretically for some $\mathrm{SNR}<1$.
K. Rohe, S. Chatterjee, and B. Yu, Spectral clustering and the high-dimensional stochastic blockmodel , The Annals of Statistics 39
1915
Earlier work this paper cites.
A. Rényi, Some remarks on the theory of trees , Magyar Tud. Akad. Mat. Kutat Int. Kzl 4
1959
Earlier work this paper cites.
P. Erdös and A Rényi, On the evolution of random graphs , Publication of the Mathematical Institute of the Hungarian Academy of Sciences, 1960, pp. 17–61
1960
Earlier work this paper cites.
H. C. White, S. A. Boorman, and R. L. Breiger, Social structure from multiple networks , American Journal of Sociology 81
1976
Earlier work this paper cites.
P. W. Holland, K. Laskey, and S. Leinhardt, Stochastic blockmodels: First steps , Social Networks 5
1983
Earlier work this paper cites.
S. E. Fienberg, M. M. Meyer, and S. S. Wasserman, Statistical analysis of multiple sociometric relations , Journal of The American Statistical Association (1985), 51–67
1985
Earlier work this paper cites.
T.N. Bui, S. Chaudhuri, F.T. Leighton, and M. Sipser, Graph bisection algorithms with good average case behavior , Combinatorica 7
1987
Earlier work this paper cites.
R.B. Boppana, Eigenvalues and graph bisection: An average-case analysis , In 28th Annual Symposium on Foundations of Computer Science (1987), 280–285
1987
Earlier work this paper cites.
Y. J. Wang and G. Y. Wong, Stochastic blockmodels for directed graphs , Journal of the American Statistical Association (1987), 8–19
1987
Earlier work this paper cites.
M.E. Dyer and A.M. Frieze, The solution of some random NP-hard problems in polynomial expected time , Journal of Algorithms 10
1989
Earlier work this paper cites.
K.-I. Hashimoto, Zeta functions of finite graphs and representations of p-adic groups , In Automorphic forms and geometry of arithmetic varieties. Adv. Stud. Pure Math. 15
1989
Earlier work this paper cites.
J. Shi and J. Malik, Normalized cuts and image segmentation , IEEE Transactions on Pattern Analysis and Machine Intelligence 22
1997
Earlier work this paper cites.
T. A. B. Snijders and K. Nowicki, Estimation and Prediction for Stochastic Blockmodels for Graphs with Latent Block Structure , Journal of Classification 14
1997
Earlier work this paper cites.
Mark Jerrum and Gregory B. Sorkin, The metropolis algorithm for graph bisection , Discrete Applied Mathematics 82
1998
Earlier work this paper cites.
A. Condon and R. M. Karp, Algorithms for graph partitioning on the planted partition model , Lecture Notes in Computer Science 1671
1999
Earlier work this paper cites.
Kevin P. Murphy, Yair Weiss, and Michael I. Jordan, Loopy belief propagation for approximate inference: An empirical study , Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence (San Francisco, CA, USA), UAI’99, Morgan Kaufmann Publishers Inc., 1999, pp. 467–475
1999
Earlier work this paper cites.
T. Carson and R. Impagliazzo, Hill-climbing finds random planted bisections , Proc. 12th Symposium on Discrete Algorithms (SODA 01), ACM press, 2001, 2001, pp. 903–909
2001
Earlier work this paper cites.
F. McSherry, Spectral partitioning of random graphs , Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium on, 2001, pp. 529–537
2001
Earlier work this paper cites.
G. Linden, B. Smith, and J. York, Amazon.com recommendations: Item-to-item collaborative filtering , IEEE Internet Computing 7
2003
Earlier work this paper cites.
E. Mossel and Y. Peres, Information flow on trees , Ann. Appl. Probab. 13
2003
Earlier work this paper cites.
Assaf Naor Dimitris Achlioptas, The two possible values of the chromatic number of a random graph , Annals of Mathematics 162
2005
Earlier work this paper cites.
J. Chen and B. Yuan, Detecting functional modules in the yeast proteinÐprotein interaction network , Bioinformatics 22
2006
Earlier work this paper cites.
M.D. Horton, H.M. Stark, and A.A. Terras, What are zeta functions of graphs and what are they good for? , Contemporary Mathematics, Quantum Graphs and Their Applications (2006), 415:173–190
2006
Earlier work this paper cites.
Béla Bollobás, Svante Janson, and Oliver Riordan, The phase transition in inhomogeneous random graphs , Random Struct. Algorithms 31
2007
Earlier work this paper cites.
M.S. Cline, M. Smoot, E. Cerami, A. Kuchinsky, N. Landys, C. Workman, R. Christmas, I. Avila-Campilo, M. Creech, B. Gross, K. Hanspers, R. Isserlin, R. Kelley, S. Killcoyne, S. Lotia, S. Maere, J. Morris, K. Ono, V. Pavlovic, A.R. Pico, A. Vailaya, P. Wang, A. Adler, B.R. Conklin, L. Hood, M. Kuiper, C. Sander, I. Schmulevich, B. Schwikowski, G. J. Warner, T. Ideker, and G.D. Bader, Integration of biological networks and gene expression data using cytoscape , Nature Protocols 2
2007
Earlier work this paper cites.
Peter J. Bickel and Aiyou Chen, A nonparametric view of network models and newman-girvan and other modularities , Proceedings of the National Academy of Sciences 106
2009
Earlier work this paper cites.
David L. Donoho, Arian Maleki, and Andrea Montanari, Message-passing algorithms for compressed sensing , Proceedings of the National Academy of Sciences 106
2009
Cited alongside, same era.
Allan Sly, Reconstruction for the potts model , Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing (New York, NY, USA), STOC ’09, ACM, 2009, pp. 581–590
2009
Cited alongside, same era.
A. Coja-Oghlan, Graph partitioning via adaptive spectral techniques , Comb. Probab. Comput. 19
2010
Cited alongside, same era.
S. Fortunato, Community detection in graphs , Physics Reports 486 (3-5)
2010
Cited alongside, same era.
A. Goldenberg, A. X. Zheng, S. E. Fienberg, and E. M. Airoldi, A survey of statistical network models , Foundations and Trends in Machine Learning 2
2010
Cited alongside, same era.
A. Saade, F. Krzakala, and L. Zdeborová, Spectral Clustering of Graphs with the Bethe Hessian , ArXiv e-prints (2014)
2014
Later among the works it cites.
2014
Later among the works it cites.
J. Xu, M. Lelarge, and L. Massoulie, Edge label inference in generalized stochastic block models: from spectral theory to impossibility results , Proceedings of COLT 2014 (2014)
2014
Later among the works it cites.
2014
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Brian Ball, Brian Karrer, and M. E. J. Newman, An efficient and principled method for detecting communities in networks , Phys. Rev. E 84
2011
Cited alongside, same era.
A. Decelle, F. Krzakala, C. Moore, and L. Zdeborová, Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications , Phys. Rev. E 84
2011
Cited alongside, same era.
B. Karrer and M. E. J. Newman, Stochastic blockmodels and community structure in networks , Phys. Rev. E 83
2011
Cited alongside, same era.
Y. Chen, S. Sanghavi, and H. Xu, Clustering Sparse Graphs , arXiv:1210.3335 (2012)
2012
Cited alongside, same era.
D. S. Choi, P. J. Wolfe, and E. M. Airoldi, Stochastic blockmodels with a growing number of classes , Biometrika (2012), 1–12
2012
Cited alongside, same era.
2012
Cited alongside, same era.
E. Abbe and A. Montanari, Conditional random fields, planted constraint satisfaction and entropy concentration , Proc. of RANDOM (Berkeley), August 2013, pp. 332–346
2013
Cited alongside, same era.
2014
Later among the works it cites.
2015
Closest in time.
E. Abbe and C. Sandon, Recovering communities in the general stochastic block model without knowing the parameters , Advances in Neural Information Processing Systems (NIPS) 28 (C. Cortes, N.D. Lawrence, D.D. Lee, M. Sugiyama, R. Garnett, and R. Garnett, eds.), Curran Associates, Inc., 2015, pp. 676–684
2015
Closest in time.
2015
Closest in time.
A. S. Bandeira, Random laplacian matrices and convex relaxations , arXiv:1504.03987 (2015)
2015
Closest in time.
Christian Borgs, Jennifer Chayes, and Adam Smith, Private graphon estimation for sparse graphs , Advances in Neural Information Processing Systems 28 (C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, eds.), Curran Associates, Inc., 2015, pp. 1369–1377
2015
Closest in time.
Charles Bordenave, Marc Lelarge, and Laurent Massoulie, Non-backtracking spectrum of random graphs: Community detection and non-regular ramanujan graphs , Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS) (Washington, DC, USA), FOCS ’15, IEEE Computer Society, 2015, pp. 1347–1357
2015
Closest in time.
I. Cabreros, E. Abbe, and A. Tsirigos, Detecting Community Structures in Hi-C Genomic Data , Conference on Information Science and Systems, Princeton University. ArXiv e-prints 1509.05121 (2015)
2015
Closest in time.
2015
Closest in time.
C. Gao, Z. Ma, A. Y. Zhang, and H. H. Zhou, Achieving Optimal Misclassification Proportion in Stochastic Block Model , ArXiv e-prints (2015)
2015
Closest in time.
B. Hajek, Y. Wu, and J. Xu, Recovering a Hidden Community Beyond the Spectral Limit in O ( | E | log ∗ | V | ) O(|E|\log^{*}|V|) Time , ArXiv e-prints (2015)
2015
Closest in time.
V. Jog and P.-L. Loh, Information-theoretic bounds for exact recovery in weighted stochastic block models using the Renyi divergence , ArXiv e-prints (2015)
2015
Closest in time.
Elchanan Mossel, Joe Neeman, and Allan Sly, Reconstruction and estimation in the planted partition model , Probability Theory and Related Fields 162
2015
Closest in time.
A. Montanari, Finding one community in a sparse graph , arXiv:1502.05680 (2015)
2015
Closest in time.
A. Moitra, W. Perry, and A. S. Wein, How Robust are Reconstruction Thresholds for Community Detection? , ArXiv e-prints (2015)
2015
Closest in time.
2015
Closest in time.
2015
Closest in time.
E. Abbe, A.S. Bandeira, and G. Hall, Exact recovery in the stochastic block model , Information Theory, IEEE Transactions on 62
2016
Closest in time.
J. Banks and C. Moore, Information-theoretic thresholds for community detection in sparse networks , ArXiv e-prints (2016)
2016
Closest in time.
Olivier Guédon and Roman Vershynin, Community detection in sparse networks via grothendieck’s inequality , Probability Theory and Related Fields 165
2016
Closest in time.
Andrea Montanari and Subhabrata Sen, Semidefinite programs on sparse random graphs and their application to community detection , Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (New York, NY, USA), STOC 2016, ACM, 2016, pp. 814–827
2016
Closest in time.