Fetching the paper…
Reading the bibliography…
The stochastic block model (SBM) is a random graph model with different group of vertices connecting differently.
Daniel A. Spielman and Nikhil Srivastava, Graph sparsification by effective resistances , SIAM Journal on Computing 40
1926
Earlier work this paper cites.
C. E. Shannon, A mathematical theory of communication , The Bell System Technical Journal 27
1948
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.
I. Csiszár, Eine informationstheoretische Ungleichung und ihre Anwendung auf den Beweis der Ergodizitat von Markoffschen Ketten , Magyar. Tud. Akad. Mat. Kutató Int. Közl 8
1963
Earlier work this paper cites.
H. Kesten and B. P. Stigum, A limit theorem for multidimensional galton-watson processes , Ann. Math. Statist. 37
1966
Earlier work this paper cites.
E. Szemerédi, Regular partitions of graphs , Problemes combinatoires et theorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) (1976)
1976
Earlier work this paper cites.
D. Hoover, Relations on probability spaces and arrays of random variables , Preprint, Institute for Advanced Study, Princeton., 1979
1979
Earlier work this paper cites.
David J. Aldous, Representations for partially exchangeable arrays of random variables , Journal of Multivariate Analysis 11
1981
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.
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.
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.
P. M. Bleher, J. Ruiz, and V. A. Zagrebnov, On the purity of the limiting Gibbs state for the Ising model on the Bethe lattice , Journal of Statistical Physics 79
1995
Earlier work this paper cites.
M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming , Journal of the Association for Computing Machinery 42
1995
Earlier work this paper cites.
Noga Alon and Nabil Kahale, A spectral technique for coloring random 3-colorable graphs , SIAM Journal on Computing 26
1997
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.
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.
Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, and Andrew Tomkins, Trawling the web for emerging cyber-communities , Comput. Netw. 31
1999
Earlier work this paper cites.
E.M. Marcotte, M. Pellegrini, H.-L. Ng, D.W. Rice, T.O. Yeates, and D. Eisenberg, Detecting protein function and protein-protein interactions from genome sequences , Science 285
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.
W. Evans, C. Kenyon, Y. Peres, and L. J. Schulman, Broadcasting on trees and the Ising model , Ann. Appl. Probab. 10
2000
Earlier work this paper cites.
Uriel Feige and Joe Kilian, Heuristics for semirandom graph problems , Journal of Computer and System Sciences 63
2001
Earlier work this paper cites.
J. Lafferty, Conditional random fields: Probabilistic models for segmenting and labeling sequence data , Morgan Kaufmann, 2001, pp. 282–289
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.
T. Richardson and R. Urbanke, An introduction to the analysis of iterative coding systems , Codes, Systems, and Graphical Models, IMA Volume in Mathematics and Its Applications, Springer, 2001, pp. 1–37
2001
Earlier work this paper cites.
M. Girvan and M. E. J. Newman, Community structure in social and biological networks , Proceedings of the National Academy of Sciences 99
2002
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.
M. Mézard, G. Parisi, and R. Zecchina, Analytic and algorithmic solution of random satisfiability problems , Science 297
2003
Earlier work this paper cites.
Aaron Clauset, M. E. J. Newman, and Cristopher Moore, Finding community structure in very large networks , Phys. Rev. E 70
2004
Earlier work this paper cites.
Svante Janson and Elchanan Mossel, Robust reconstruction on trees is determined by the second eigenvalue , Ann. Probab. 32
2004
Earlier work this paper cites.
D. Jiang, C. Tang, and A. Zhang, Cluster analysis for gene expression data: a survey , Knowledge and Data Engineering, IEEE Transactions on 16
2004
Earlier work this paper cites.
L. Adamic and N. Glance, The political blogosphere and the 2004 U.S. election: Divided they blog , Proceedings of the 3rd International Workshop on Link Discovery (New York, NY, USA), LinkKDD ’05, 2005, pp. 36–43
2005
Earlier work this paper cites.
Dimitris Achlioptas and Assaf Naor, The two possible values of the chromatic number of a random graph , Annals of Mathematics 162
2005
Earlier work this paper cites.
D. Achlioptas, A. Naor, and Y. Peres, Rigorous Location of Phase Transitions in Hard Optimization Problems , Nature 435
2005
Earlier work this paper cites.
Jinho Baik, Gérard Ben Arous, and Sandrine Péché, Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices , Ann. Probab. 33
2005
Earlier work this paper cites.
Uriel Feige and Eran Ofek, Spectral techniques applied to sparse random graphs , Random Structures & Algorithms 27
2005
Earlier work this paper cites.
Dongning Guo, Shlomo Shamai, and Sergio Verdú, Mutual information and minimum mean-square error in Gaussian channels , Information Theory, IEEE Transactions on 51
2005
Earlier work this paper cites.
G. Palla, I. Derenyi, I. Farkas, and T. Vicsek, Uncovering the overlapping community structure of complex networks in nature and society , Nature 435
2005
Earlier work this paper cites.
Christian Borgs, Jennifer Chayes, Elchanan Mossel, and Sebastien Roch, The Kesten-Stigum reconstruction bound is tight for roughly symmetric binary channels , Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (Washington, DC, USA), FOCS ’06, IEEE Computer Society, 2006, pp. 518–530
2006
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.
Robert Krauthgamer and Uriel Feige, A polylogarithmic approximation of the minimum bisection , SIAM Review 48
2006
Earlier work this paper cites.
L. Lovász and B. Szegedy, Limits of dense graph sequences , Journal of Combinatorial Theory, Series B 96
2006
Earlier work this paper cites.
Marc Mézard and Andrea Montanari, Reconstruction on trees and spin glass transition , Journal of Statistical Physics 124
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.
P. Diaconis and S. Janson, Graph limits and exchangeable random graphs , ArXiv:0712.2749 (2007)
2007
Earlier work this paper cites.
Van H. Vu, Spectral norm of random matrices , Combinatorica 27
2007
Earlier work this paper cites.
C. Borgs, J.T. Chayes, L. Lovasz, V.T. Sos, and K. Vesztergombi, Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing , Advances in Mathematics 219
2008
Earlier work this paper cites.
Jörg Reichardt and Michele Leone, (Un)detectable cluster structure in sparse networks , Phys. Rev. Lett. 101
2008
Cited alongside, same era.
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
Cited alongside, same era.
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.
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.
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
Later among the works it cites.
2015
Later among the works it cites.
2015
Later among the works it cites.
2015
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
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.
M. Newman, Networks: an introduction , Oxford University Press, Oxford, 2010
2010
Cited alongside, same era.
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.
Mohsen Bayati and Andrea Montanari, The dynamics of message passing on dense graphs, with applications to compressed sensing , Information Theory, IEEE Transactions on 57
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.
M. E. J. Newman, Communities, modules and large-scale structure in networks , Nature Physics 8
2011
Cited alongside, same era.
2015
Later among the works it cites.
2015
Later among the works it cites.
Jiashun Jin, Fast community detection by score , Ann. Statist. 43
2015
Later among the works it cites.
2015
Later among the works it cites.
Tatsuro Kawamoto and Yoshiyuki Kabashima, Limitations in the spectral method for graph partitioning: Detectability threshold and localization of eigenvectors , Phys. Rev. E 91
2015
Later among the works it cites.
2015
Later among the works it cites.
2015
Later among the works it cites.
Elchanan Mossel, Joe Neeman, and Allan Sly, Reconstruction and estimation in the planted partition model , Probability Theory and Related Fields 162
2015
Later among the works it cites.
A. Montanari, Finding one community in a sparse graph , arXiv:1502.05680 (2015)
2015
Later among the works it cites.
2015
Later among the works it cites.
Mark EJ Newman and Tiago P Peixoto, Generalized communities in networks , Phys. Rev. Lett. 115
2015
Later among the works it cites.
Tiago P Peixoto, Model selection and hypothesis testing for large-scale network models with overlapping groups , Phys. Rev. X 5
2015
Later among the works it cites.
Y. Wu, J. Xu, and B. Hajek, Achieving exact cluster recovery threshold via semidefinite programming under the stochastic block model , 2015 49th Asilomar Conference on Signals, Systems and Computers, Nov 2015, pp. 1070–1074
2015
Later among the works it cites.
2015
Later among the works it cites.
E. Abbe, Graph compression: The effect of clusters , 2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton), Sept 2016, pp. 1–8
2016
Later among the works it cites.
E. Abbe, A.S. Bandeira, and G. Hall, Exact recovery in the stochastic block model , Information Theory, IEEE Transactions on 62
2016
Later among the works it cites.
Emmanuel Abbe and Colin Sandon, Achieving the KS threshold in the general stochastic block model with linearized acyclic belief propagation , Advances in Neural Information Processing Systems 29 (D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, eds.), Curran Associates, Inc., 2016, pp. 1334–1342
2016
Later among the works it cites.
2016
Later among the works it cites.
Jess Banks, Cristopher Moore, Joe Neeman, and Praneeth Netrapalli, Information-theoretic thresholds for community detection in sparse networks , Proc. of COLT (2016)
2016
Later among the works it cites.
2016
Later among the works it cites.
2016
Later among the works it cites.
Francesco Caltagirone, Marc Lelarge, and Léo Miolane, Recovering asymmetric communities in the stochastic block model , Allerton (2016)
2016
Later among the works it cites.
Olivier Guédon and Roman Vershynin, Community detection in sparse networks via Grothendieck’s inequality , Probability Theory and Related Fields 165
2016
Later among the works it cites.
A. Ghasemian, P. Zhang, A. Clauset, C. Moore, and L. Peel, Detectability Thresholds and Optimal Algorithms for Community Structure in Dynamic Networks , Physical Review X 6
2016
Later among the works it cites.
2016
Later among the works it cites.
Ankur Moitra, William Perry, and Alexander S Wein, How robust are reconstruction thresholds for community detection? , Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, ACM, 2016, pp. 828–841
2016
Later among the works it cites.
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
Later among the works it cites.
2016
Later among the works it cites.
2016
Later among the works it cites.
2016
Later among the works it cites.
Pan Zhang, Cristopher Moore, and M. E. J. Newman, Community detection in networks with unequal groups , Phys. Rev. E 93
2016
Later among the works it cites.
A. R. Asadi, E. Abbe, and S. Verdú, Compressing data on graphs with clusters , 2017 IEEE International Symposium on Information Theory (ISIT), June 2017, pp. 1583–1587
2017
Closest in time.
2017
Closest in time.
2017
Closest in time.
E. Abbe, E. Boix, and C. Sandon, Graph powering and spectral gap extraction , Manuscript. Results partly presented at the Simons Institute and partly available in E. Boix PACM Thesis, Princeton University (2017)
2017
Closest in time.
2017
Closest in time.
2017
Closest in time.
Emmanuel Abbe and Colin Sandon, Proof of the achievability conjectures for the general stochastic block model , Communications on Pure and Applied Mathematics 71
2017
Closest in time.
2017
Closest in time.
S. Galhotra, A. Mazumdar, S. Pal, and B. Saha, The Geometric Block Model , ArXiv:1709.05510 (2017)
2017
Closest in time.
2017
Closest in time.
2017
Closest in time.
2017
Closest in time.
E. Mossel, Private communications, 2017
2017
Closest in time.