{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T19:22:49Z","timestamp":1773688969617,"version":"3.50.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2017,8,14]],"date-time":"2017-08-14T00:00:00Z","timestamp":1502668800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2018,6]]},"DOI":"10.1007\/s00493-016-3238-8","type":"journal-article","created":{"date-parts":[[2017,8,14]],"date-time":"2017-08-14T09:57:16Z","timestamp":1502704636000},"page":"665-708","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":89,"title":["A Proof of the Block Model Threshold Conjecture"],"prefix":"10.1007","volume":"38","author":[{"given":"Elchanan","family":"Mossel","sequence":"first","affiliation":[]},{"given":"Joe","family":"Neeman","sequence":"additional","affiliation":[]},{"given":"Allan","family":"Sly","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,8,14]]},"reference":[{"key":"3238_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-65371-1","volume-title":"Branching processes","author":"K. B. Athreya","year":"1972","unstructured":"K. B. Athreya and P. E. Ney: Branching processes, Springer-Verlag, New York, 1972. Die Grundlehren der mathematischen Wissenschaften, Band 196."},{"key":"3238_CR2","doi-asserted-by":"publisher","first-page":"21068","DOI":"10.1073\/pnas.0907096106","volume":"106","author":"P. J. Bickel","year":"2009","unstructured":"P. J. Bickel and A. Chen: A nonparametric view of network models and Newman-Girvan and other modularities, Proceedings of the National Academy of Sciences 106 (2009), 21068\u201321073.","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"3238_CR3","first-page":"280","volume-title":"28th Annual Symposium on Foundations of Computer Science","author":"R. B. Boppana","year":"1987","unstructured":"R. B. Boppana: Eigenvalues and graph bisection: An average-case analysis, in: 28th Annual Symposium on Foundations of Computer Science, 280\u2013285. IEEE, 1987."},{"key":"3238_CR4","volume-title":"A new proof of Friedman\u2019s second eigenvalue theorem and its extension to random lifts","author":"C. Bordenave","year":"2015","unstructured":"C. Bordenave: A new proof of Friedman\u2019s second eigenvalue theorem and its extension to random lifts. arXiv preprint arXiv:1502.04482, 2015."},{"key":"3238_CR5","volume-title":"Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs","author":"C. Bordenave","year":"2015","unstructured":"C. Bordenave, M. Lelarge and L. Massouli: Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs. arXiv preprint arXiv:1501.06087, 2015."},{"key":"3238_CR6","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/BF02579448","volume":"7","author":"T. N. Bui","year":"1987","unstructured":"T. N. Bui, S. Chaudhuri, F. T. Leighton and M. Sipser: Graph bisection algorithms with good average case behavior, Combinatorica 7 (1987), 171\u2013191.","journal-title":"Combinatorica"},{"key":"3238_CR7","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1017\/S0963548309990514","volume":"19","author":"A. Coja-Oghlan","year":"2010","unstructured":"A. Coja-Oghlan: Graph partitioning via adaptive spectral techniques, Combinatorics, Probability and Computing 19 (2010), 227\u2013284.","journal-title":"Combinatorics, Probability and Computing"},{"key":"3238_CR8","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1002\/1098-2418(200103)18:2<116::AID-RSA1001>3.0.CO;2-2","volume":"18","author":"A. Condon","year":"2001","unstructured":"A. Condon and R. M. Karp: Algorithms for graph partitioning on the planted partition model, Random Structures and Algorithms 18 (2001), 116\u2013140.","journal-title":"Random Structures and Algorithms"},{"key":"3238_CR9","doi-asserted-by":"publisher","first-page":"066106","DOI":"10.1103\/PhysRevE.84.066106","volume":"84","author":"A. Decelle","year":"2011","unstructured":"A. Decelle, F. Krzakala, C. Moore and L. Zdeborov\u00e1: Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications, Physics Review E 84 (2011) 066106.","journal-title":"Physics Review E"},{"key":"3238_CR10","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1016\/0196-6774(89)90001-1","volume":"10","author":"M. E. Dyer","year":"1989","unstructured":"M. E. Dyer and A. M. Frieze: The solution of some random NP-hard problems in polynomial expected time, Journal of Algorithms 10 (1989), 451\u2013489.","journal-title":"Journal of Algorithms"},{"key":"3238_CR11","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1007\/s00220-012-1527-7","volume":"314","author":"L. Erd\u0151s","year":"2012","unstructured":"L. Erd\u0151s, A. Knowles, H.-T. Yau and J. Yin: Spectral statistics of Erd\u0151s-R\u00e9nyi graphs II: eigenvalue spacing and the extreme eigenvalues, Communications in Mathematical Physics 314 (2012), 587\u2013640.","journal-title":"Communications in Mathematical Physics"},{"key":"3238_CR12","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1002\/rsa.20089","volume":"27","author":"U. Feige","year":"2005","unstructured":"U. Feige and E. Ofek: Spectral techniques applied to sparse random graphs, Random Structures & Algorithms 27 (2005), 251\u2013275.","journal-title":"Random Structures & Algorithms"},{"key":"3238_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1080\/15427951.2005.10129097","volume":"2","author":"A. Flaxman","year":"2005","unstructured":"A. Flaxman, A. Frieze and T. Fenner: High degree vertices and eigenvalues in the preferential attachment graph, Internet Math. 2 (2005), 1\u201319.","journal-title":"Internet Math."},{"key":"3238_CR14","volume-title":"Community detection in sparse networks via grothendieck\u2019s inequality","author":"O. Gu\u00e9don","year":"2014","unstructured":"O. Gu\u00e9don and R. Vershynin: Community detection in sparse networks via grothendieck\u2019s inequality. arXiv preprint arXiv:1411.4686, 2014."},{"key":"3238_CR15","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0378-8733(83)90021-7","volume":"5","author":"P. W. Holland","year":"1983","unstructured":"P. W. Holland, K. B. Laskey and S. Leinhardt: Stochastic blockmodels: First steps, Social Networks 5 (1983), 109\u2013137.","journal-title":"Social Networks"},{"key":"3238_CR16","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/S0166-218X(97)00133-9","volume":"82","author":"M. Jerrum","year":"1998","unstructured":"M. Jerrum and G. B. Sorkin: The Metropolis algorithm for graph bisection, Discrete Applied Mathematics 82 (1998), 155\u2013175.","journal-title":"Discrete Applied Mathematics"},{"key":"3238_CR17","doi-asserted-by":"publisher","first-page":"1463","DOI":"10.1214\/aoms\/1177699139","volume":"37","author":"H. Kesten","year":"1966","unstructured":"H. Kesten and B. P. Stigum: Additional limit theorems for indecomposable multidimensional Galton-Watson processes, Ann. Math. Statist. 37 (1966), 1463\u20131481.","journal-title":"Ann. Math. Statist."},{"key":"3238_CR18","volume-title":"Spectral redemption: clustering sparse networks","author":"F. Krzakala","year":"2013","unstructured":"F. Krzakala, C. Moore, E. Mossel, J. Neeman, A. Sly, Zdeborova L and P. Zhang: Spectral redemption: clustering sparse networks. arXiv:1306.5550, 2013."},{"key":"3238_CR19","doi-asserted-by":"publisher","first-page":"695","DOI":"10.1145\/1367497.1367591","volume-title":"Proceeding of the 17th international conference on World Wide Web","author":"J. Leskovec","year":"2008","unstructured":"J. Leskovec, K. J. Lang, A. Dasgupta and M. W. Mahoney: Statistical properties of community structure in large social and information networks, in: Proceeding of the 17th international conference on World Wide Web, 695\u2013704. ACM, 2008."},{"key":"3238_CR20","first-page":"694","volume-title":"Proceedings of the 46th Annual ACM Symposium on Theory of Computing","author":"L. Massouli\u00e9","year":"2014","unstructured":"L. Massouli\u00e9: Community detection thresholds and the weak ramanujan property, in: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, 694\u2013703. ACM, 2014."},{"key":"3238_CR21","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1109\/SFCS.2001.959929","volume-title":"42nd IEEE Symposium on Foundations of Computer Science","author":"F. McSherry","year":"2001","unstructured":"F. McSherry: Spectral partitioning of random graphs, in: 42nd IEEE Symposium on Foundations of Computer Science, 529\u2013537. IEEE, 2001."},{"key":"3238_CR22","volume-title":"Probability Theory and Related Fields","author":"E. Mossel","year":"2014","unstructured":"E. Mossel, J. Neeman and A. Sly: Stochastic block models and reconstruction, Probability Theory and Related Fields, 2014, (to appear)."},{"key":"3238_CR23","doi-asserted-by":"publisher","first-page":"188701","DOI":"10.1103\/PhysRevLett.108.188701","volume":"108","author":"R. R. Nadakuditi","year":"2012","unstructured":"R. R. Nadakuditi and M. E. J Newman: Graph spectra and the detectability of community structure in networks, Physical Review Letters 108 (2012), 188701.","journal-title":"Physical Review Letters"},{"key":"3238_CR24","doi-asserted-by":"publisher","first-page":"1878","DOI":"10.1214\/11-AOS887","volume":"39","author":"K. Rohe","year":"2011","unstructured":"K. Rohe, S. Chatterjee and B. Yu: Spectral clustering and the high-dimensional stochastic blockmodel, The Annals of Statistics 39 (2011), 1878\u20131915.","journal-title":"The Annals of Statistics"},{"key":"3238_CR25","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1137\/S0040585X9797821X","volume":"45","author":"B. Roos","year":"2001","unstructured":"B. Roos: Binomial approximation to the poisson binomial distribution: The krawtchouk expansion, Theory of Probability and Its Applications 45 (2001), 258\u2013272.","journal-title":"Theory of Probability and Its Applications"},{"key":"3238_CR26","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/s003579900004","volume":"14","author":"T. A. B. Snijders","year":"1997","unstructured":"T. A. B. Snijders and K. Nowicki: Estimation and prediction for stochastic block-models for graphs with latent block structure, Journal of Classification 14 (1997), 75\u2013100.","journal-title":"Journal of Classification"},{"key":"3238_CR27","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1038\/35065725","volume":"410","author":"S. H. Strogatz","year":"2001","unstructured":"S. H. Strogatz: Exploring complex networks, Nature 410 (2001), 268\u2013276.","journal-title":"Nature"},{"key":"3238_CR28","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1142\/S0219199708002788","volume":"10","author":"T. Tao","year":"2008","unstructured":"T. Tao and V. Vu: Random matrices: the circular law, Communications in Contemporary Mathematics 10 (2008), 261\u2013307.","journal-title":"Communications in Contemporary Mathematics"},{"key":"3238_CR29","doi-asserted-by":"publisher","first-page":"1266","DOI":"10.1214\/11-AAP789","volume":"22","author":"P. M. Wood","year":"2012","unstructured":"P. M. Wood: Universality and the circular law for sparse random matrices, The Annals of Applied Probability 22 (2012), 1266\u20131300.","journal-title":"The Annals of Applied Probability"},{"key":"3238_CR30","volume-title":"Community detection via random and adaptive sampling","author":"S.-Y. Yun","year":"2014","unstructured":"S.-Y. Yun and A. Proutiere: Community detection via random and adaptive sampling, arXiv preprint arXiv:1402.3072, 2014."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-016-3238-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-016-3238-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-016-3238-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,2]],"date-time":"2019-10-02T11:10:51Z","timestamp":1570014651000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-016-3238-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,14]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,6]]}},"alternative-id":["3238"],"URL":"https:\/\/doi.org\/10.1007\/s00493-016-3238-8","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8,14]]}}}