{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T17:05:12Z","timestamp":1774631112148,"version":"3.50.1"},"reference-count":168,"publisher":"Emerald","issue":"1-2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018,6,7]]},"abstract":"<jats:p>The stochastic block model (SBM) is a random graph model with different group of vertices connecting differently. It is widely employed as a canonical model to study clustering and community detection, and provides a fertile ground to study the information-theoretic and computational tradeoffs that arise in combinatorial statistics and more generally data science.<\/jats:p>\n                  <jats:p>This monograph surveys the recent developments that establish the fundamental limits for community detection in the SBM, both with respect to information-theoretic and computational tradeoffs, and for various recovery requirements such as exact, partial and weak recovery. The main results discussed are the phase transitions for exact recovery at the Chernoff-Hellinger threshold, the phase transition for weak recovery at the Kesten-Stigum threshold, the optimal SNR-mutual information tradeoff for partial recovery, and the gap between information-theoretic and computational thresholds.<\/jats:p>\n                  <jats:p>The monograph gives a principled derivation of the main algorithms developed in the quest of achieving the limits, in particular two-round algorithms via graph-splitting, semidefinite programming, (linearized) belief propagation, classical\/nonbacktracking spectral methods and graph powering. Extensions to other block models, such as geometric block models, and a few open problems are also discussed.<\/jats:p>","DOI":"10.1561\/0100000067","type":"journal-article","created":{"date-parts":[[2018,6,7]],"date-time":"2018-06-07T09:32:47Z","timestamp":1528363967000},"page":"1-162","source":"Crossref","is-referenced-by-count":41,"title":["Community Detection and Stochastic Block Models"],"prefix":"10.1561","volume":"14","author":[{"given":"Emmanuel","family":"Abbe","sequence":"first","affiliation":[{"name":"Princeton University Program in Applied and Computational Mathematics, and Department of Electrical Engineering, , Princeton, USA"}]}],"member":"140","published-online":{"date-parts":[[2018,6,7]]},"reference":[{"key":"2026032712272297700_ref001","article-title":"On semidefinite relaxations for the block model","author":"Amini","year":"2014","journal-title":"arXiv:1406.5647"},{"issue":"2","key":"2026032712272297700_ref002","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1017\/S0963548309990514","article-title":"Graph partitioning via adaptive spectral techniques","volume":"19","author":"Coja-Oghlan","year":"2010","journal-title":"Comb. Probab. Comput"},{"issue":"2","key":"2026032712272297700_ref003","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1561\/2200000005","article-title":"A survey of statistical network models","volume":"2","author":"Goldenberg","year":"2010","journal-title":"Foundations and Trends in Machine Learning"},{"key":"2026032712272297700_ref004","article-title":"Finding One Community in a Sparse Graph","author":"Montanari","year":"2015","journal-title":"arXiv:1502.05680"},{"key":"2026032712272297700_ref005","article-title":"Random Laplacian matrices and convex relaxations","author":"Bandeira","year":"2015","journal-title":"arXiv:1504.03987"},{"key":"2026032712272297700_ref006","article-title":"Spectral Detection in the Censored Block Model","author":"Saade","year":"2015","journal-title":"arXiv: 1502.00163"},{"key":"2026032712272297700_ref007","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/ALLERTON.2016.7852203","volume-title":"Graph compression: The effect of clusters","author":"Abbe","year":"2016"},{"key":"2026032712272297700_ref008","article-title":"Community detection and stochastic block models: recent developments","author":"Abbe","year":"2017","journal-title":"ArXiv:1703.10146"},{"key":"2026032712272297700_ref009","article-title":"Community Detection on Euclidean Random Graphs","author":"Abbe","year":"2017","journal-title":"ArXiv:1706.09942"},{"key":"2026032712272297700_ref010","article-title":"Exact Recovery in the Stochastic Block Model","author":"Abbe","year":"2014","journal-title":"ArXiv:1405.3267"},{"issue":"1","key":"2026032712272297700_ref011","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1109\/TNSE.2014.2368716","article-title":"Decoding Binary Node Labels from Censored Edge Measurements: Phase Transition and Efficient Recovery","volume":"1","author":"Abbe","year":"2014","journal-title":"Network Science and Engineering, IEEE Transactions on"},{"key":"2026032712272297700_ref012","doi-asserted-by":"publisher","first-page":"1251","DOI":"10.1109\/ISIT.2014.6875033","volume-title":"Linear inverse problems on Erd\u00f6s-R\u00e9nyi graphs: Information-theoretic limits and efficient recovery","author":"Abbe","year":"2014"},{"issue":"1","key":"2026032712272297700_ref013","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1109\/TIT.2015.2490670","article-title":"Exact Recovery in the Stochastic Block Model","volume":"62","author":"Abbe","year":"2016","journal-title":"Information Theory, IEEE Transactions on"},{"key":"2026032712272297700_ref014","volume-title":"Manuscript. Results partly presented at the Simons Institute and partly available in E. Boix PACM Thesis","author":"Abbe","year":"2017"},{"key":"2026032712272297700_ref015","article-title":"Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank","author":"Abbe","year":"2017","journal-title":"ArXiv:1709.09565"},{"key":"2026032712272297700_ref016","article-title":"Group Synchronization on Grids","author":"Abbe","year":"2017","journal-title":"ArXiv:1706.08561"},{"key":"2026032712272297700_ref017","article-title":"Detection in the stochastic block model with multiple clusters: proof of the achievability conjectures, acyclic BP, and the information-computation gap","author":"Abbe","year":"2015","journal-title":"ArXiv e-prints 1512.09080"},{"key":"2026032712272297700_ref018","first-page":"676","volume-title":"Advances in Neural Information Processing Systems (NIPS) 28","author":"Abbe","year":"2015"},{"key":"2026032712272297700_ref019","first-page":"1334","volume-title":"Advances in Neural Information Processing Systems 29","author":"Abbe","year":"2016"},{"issue":"7","key":"2026032712272297700_ref020","doi-asserted-by":"publisher","first-page":"1334","DOI":"10.1002\/cpa.21719","article-title":"Proof of the Achievability Conjectures for the General Stochastic Block Model","volume":"71","author":"Abbe","year":"2017","journal-title":"Communications on Pure and Applied Mathematics"},{"issue":"3","key":"2026032712272297700_ref021","doi-asserted-by":"crossref","first-page":"1335","DOI":"10.4007\/annals.2005.162.1335","article-title":"The Two Possible Values of the Chromatic Number of a Random Graph","volume":"162","author":"Achlioptas","year":"2005","journal-title":"Annals of Mathematics"},{"key":"2026032712272297700_ref022","article-title":"Multisection in the Stochastic Block Model using Semidefinite Programming","author":"Agarwal","year":"2015","journal-title":"ArXiv:1507.02323"},{"issue":"June","key":"2026032712272297700_ref023","first-page":"1981","article-title":"Mixed Membership Stochastic Block Models","volume":"9","author":"Airoldi","year":"2008","journal-title":"J. Mach. Learn. Res"},{"issue":"4","key":"2026032712272297700_ref024","doi-asserted-by":"crossref","first-page":"581","DOI":"10.1016\/0047-259X(81)90099-3","article-title":"Representations for partially exchangeable arrays of random variables","volume":"11","author":"Aldous","year":"1981","journal-title":"Journal of Multivariate Analysis"},{"issue":"6","key":"2026032712272297700_ref025","doi-asserted-by":"publisher","first-page":"1733","DOI":"10.1137\/S0097539794270248","article-title":"A Spectral Technique for Coloring Random 3-Colorable Graphs","volume":"26","author":"Alon","year":"1997","journal-title":"SIAM Journal on Computing"},{"key":"2026032712272297700_ref026","doi-asserted-by":"publisher","first-page":"1583","DOI":"10.1109\/ISIT.2017.8006796","volume-title":"Compressing data on graphs with clusters","author":"Asadi","year":"2017"},{"issue":"1","key":"2026032712272297700_ref027","doi-asserted-by":"publisher","first-page":"016107","DOI":"10.1103\/PhysRevE.83.016107","article-title":"Stochastic blockmodels and community structure in networks","volume":"83","author":"Karrer","year":"2011","journal-title":"Phys. Rev. E"},{"issue":"5","key":"2026032712272297700_ref028","doi-asserted-by":"publisher","first-page":"1643","DOI":"10.1214\/009117905000000233","article-title":"Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices","volume":"33","author":"Baik","year":"2005","journal-title":"Ann. Probab"},{"issue":"3","key":"2026032712272297700_ref029","doi-asserted-by":"publisher","first-page":"036103","DOI":"10.1103\/PhysRevE.84.036103","article-title":"An efficient and principled method for detecting communities in networks","volume":"84","author":"Ball","year":"2011","journal-title":"Phys. Rev. E"},{"key":"2026032712272297700_ref030","article-title":"Information-theoretic thresholds for community detection in sparse networks","author":"Banks","year":"2016","journal-title":"ArXiv:1601.02658"},{"key":"2026032712272297700_ref031","article-title":"Information-theoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization","author":"Banks","year":"2016","journal-title":"arXiv: 1607.05222 [math.ST]"},{"key":"2026032712272297700_ref032","article-title":"Information-theoretic thresholds for community detection in sparse networks","author":"Banks","year":"2016","journal-title":"Proc. of COLT"},{"issue":"2","key":"2026032712272297700_ref033","doi-asserted-by":"crossref","first-page":"764","DOI":"10.1109\/TIT.2010.2094817","article-title":"The dynamics of message passing on dense graphs, with applications to compressed sensing","volume":"57","author":"Bayati","year":"2011","journal-title":"Information Theory, IEEE Transactions on"},{"issue":"36","key":"2026032712272297700_ref034","doi-asserted-by":"crossref","first-page":"14563","DOI":"10.1073\/pnas.1307845110","article-title":"Optimal M-estimation in high-dimensional regression","volume":"110","author":"Bean","year":"2013","journal-title":"Proceedings of the National Academy of Sciences"},{"issue":"4","key":"2026032712272297700_ref035","doi-asserted-by":"publisher","first-page":"1780","DOI":"10.1214\/13-AOS1127","article-title":"Optimal detection of sparse principal components in high dimension","volume":"41","author":"Berthet","year":"2013","journal-title":"Ann. Statist"},{"key":"2026032712272297700_ref036","article-title":"Exact recovery in the Ising blockmodel","author":"Berthet","year":"2016","journal-title":"ArXiv:1612.03880"},{"key":"2026032712272297700_ref037","article-title":"Community Detection in Networks using Graph Distance","author":"Bhattacharyya","year":"2014","journal-title":"ArXiv:1401.3915"},{"issue":"50","key":"2026032712272297700_ref038","doi-asserted-by":"publisher","first-page":"21068","DOI":"10.1073\/pnas.0907096106","article-title":"A nonparametric view of network models and Newman-Girvan and other modularities","volume":"106","author":"Bickel","year":"2009","journal-title":"Proceedings of the National Academy of Sciences"},{"issue":"1","key":"2026032712272297700_ref039","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1007\/BF02179399","article-title":"On the purity of the limiting Gibbs state for the Ising model on the Bethe lattice","volume":"79","author":"Bleher","year":"1995","journal-title":"Journal of Statistical Physics"},{"issue":"1","key":"2026032712272297700_ref040","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1002\/rsa.v31:1","article-title":"The Phase Transition in Inhomogeneous Random Graphs","volume":"31","author":"Bollob\u00e1s","year":"2007","journal-title":"Random Struct. Algorithms"},{"key":"2026032712272297700_ref041","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1109\/SFCS.1987.22","article-title":"Eigenvalues and graph bisection: An averagecase analysis","author":"Boppana","year":"1987","journal-title":"In 28th Annual Symposium on Foundations of Computer Science"},{"key":"2026032712272297700_ref042","doi-asserted-by":"publisher","first-page":"1347","DOI":"10.1109\/FOCS. 2015.86","volume-title":"Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS). FOCS \u201915","author":"Bordenave","year":"2015"},{"key":"2026032712272297700_ref043","article-title":"Consistent nonparametric estimation for heavy-tailed sparse graphs","author":"Borgs","year":"2015","journal-title":"ArXiv:1508.06675"},{"key":"2026032712272297700_ref044","article-title":"An Lp theory of sparse graph convergence I: limits, sparse random graph models, and power law distributions","author":"Borgs","year":"2014","journal-title":"ArXiv:1401.2906"},{"key":"2026032712272297700_ref045","article-title":"Iterative Collaborative Filtering for Sparse Matrix Estimation","author":"Borgs","year":"2017","journal-title":"ArXiv:1712.00710"},{"issue":"6","key":"2026032712272297700_ref046","doi-asserted-by":"crossref","first-page":"1801","DOI":"10.1016\/j.aim.2008.07.008","article-title":"Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing","volume":"219","author":"Borgs","year":"2008","journal-title":"Advances in Mathematics"},{"key":"2026032712272297700_ref047","doi-asserted-by":"publisher","first-page":"518","DOI":"10.1109\/FOCS.2006.76","volume-title":"Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science. FOCS \u201906","author":"Borgs","year":"2006"},{"key":"2026032712272297700_ref048","first-page":"1369","volume-title":"Advances in Neural Information Processing Systems 28","author":"Borgs","year":"2015"},{"issue":"2","key":"2026032712272297700_ref049","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/BF02579448","article-title":"Graph bisection algorithms with good average case behavior","volume":"7","author":"Bui","year":"1987","journal-title":"Combinatorica"},{"key":"2026032712272297700_ref050","volume-title":"Conference on Information Science and Systems","author":"Cabreros","year":"2015"},{"key":"2026032712272297700_ref051","article-title":"Recovering asymmetric communities in the stochastic block model","author":"Caltagirone","year":"2016","journal-title":"Allerton"},{"issue":"18","key":"2026032712272297700_ref052","doi-asserted-by":"publisher","first-page":"2283","DOI":"10.1093\/bioinformatics\/btl370","article-title":"Detecting functional modules in the yeast protein-protein interaction network","volume":"22","author":"Chen","year":"2006","journal-title":"Bioinformatics"},{"key":"2026032712272297700_ref053","article-title":"Information Recovery from Pairwise Measurements","author":"Chen","year":"2014","journal-title":"In Proc. ISIT, Honolulu"},{"key":"2026032712272297700_ref054","article-title":"Near-Optimal Joint Object Matching via Convex Relaxation","author":"Chen","year":"2014","journal-title":"Available at arXiv:1402.1473"},{"key":"2026032712272297700_ref055","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1093\/biomet\/asr053","article-title":"Stochastic blockmodels with a growing number of classes","author":"Choi","year":"2012","journal-title":"Biometrika"},{"issue":"6","key":"2026032712272297700_ref056","doi-asserted-by":"publisher","first-page":"066111","DOI":"10.1103\/PhysRevE.70.066111","article-title":"Finding community structure in very large networks","volume":"70","author":"Clauset","year":"2004","journal-title":"Phys. Rev. E"},{"issue":"10","key":"2026032712272297700_ref057","doi-asserted-by":"publisher","first-page":"2366","DOI":"10.1038\/nprot.2007.324","article-title":"Integration of biological networks and gene expression data using Cytoscape","volume":"2","author":"Cline","year":"2007","journal-title":"Nature Protocols"},{"key":"2026032712272297700_ref058","article-title":"Information-theoretic thresholds from the cavity method","author":"Coja-Oghlan","year":"2016","journal-title":"ArXiv:1611.00814"},{"key":"2026032712272297700_ref059","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/978-3-540-48413-4_23","article-title":"Algorithms for Graph Partitioning on the Planted Partition Model","volume":"1671","author":"Condon","year":"1999","journal-title":"Lecture Notes in Computer Science"},{"key":"2026032712272297700_ref060","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1038\/nature03602","article-title":"Rigorous Location of Phase Transitions in Hard Optimization Problems","volume":"435","author":"Achlioptas","year":"2005","journal-title":"Nature"},{"key":"2026032712272297700_ref061","volume-title":"Relations on Probability Spaces and Arrays of Random Variables","author":"Hoover","year":"1979"},{"issue":"11","key":"2026032712272297700_ref062","doi-asserted-by":"publisher","first-page":"1370","DOI":"10.1109\/TKDE.2004.68","article-title":"Cluster analysis for gene expression data: a survey","volume":"16","author":"Jiang","year":"2004","journal-title":"Knowledge and Data Engineering, IEEE Transactions on"},{"issue":"6","key":"2026032712272297700_ref063","doi-asserted-by":"crossref","first-page":"066106","DOI":"10.1103\/PhysRevE.84.066106","article-title":"Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications","volume":"84","author":"Decelle","year":"2011","journal-title":"Phys. Rev. E"},{"key":"2026032712272297700_ref064","first-page":"2197","volume-title":"Information-theoretically optimal sparse PCA","author":"Deshpande","year":"2014"},{"key":"2026032712272297700_ref065","article-title":"Graph limits and exchangeable random graphs","author":"Diaconis","year":"2007","journal-title":"ArXiv:0712.2749"},{"issue":"45","key":"2026032712272297700_ref066","doi-asserted-by":"publisher","first-page":"18914","DOI":"10.1073\/pnas.0909892106","article-title":"Messagepassing algorithms for compressed sensing","volume":"106","author":"Donoho","year":"2009","journal-title":"Proceedings of the National Academy of Sciences"},{"issue":"17","key":"2026032712272297700_ref067","doi-asserted-by":"publisher","first-page":"413","DOI":"10.4086\/toc.2015.v011a017","article-title":"Conditional Random Fields, Planted Constraint Satisfaction, and Entropy Concentration","volume":"11","author":"Abbe","year":"2015","journal-title":"Theory of Computing"},{"key":"2026032712272297700_ref068","doi-asserted-by":"publisher","first-page":"670","DOI":"10.1109\/FOCS.2015.47","volume-title":"Community Detection in General Stochastic Block models: Fundamental Limits and Efficient Algorithms for Recovery","author":"Abbe","year":"2015"},{"key":"2026032712272297700_ref069","article-title":"Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms","author":"Abbe","year":"2015","journal-title":"arXiv:1503.00609"},{"key":"2026032712272297700_ref070","article-title":"Stochastic blockmodel approximation of a graphon: Theory and consistent estimation","author":"Airoldi","year":"2013","journal-title":"arXiv:1311.1731"},{"key":"2026032712272297700_ref071","volume-title":"Private communications, 2017","author":"Mossel","year":"2017"},{"key":"2026032712272297700_ref072","article-title":"Belief Propagation, Robust Reconstruction, and Optimal Recovery of Block Models","author":"Mossel","year":"2013","journal-title":"Arxiv:arXiv:1309.1380"},{"key":"2026032712272297700_ref073","article-title":"Consistency Thresholds for Binary Symmetric Block Models","author":"Mossel","year":"2014","journal-title":"Arxiv:arXiv:1407.1591. In proc. of STOC15"},{"key":"2026032712272297700_ref074","doi-asserted-by":"crossref","first-page":"817","DOI":"10.1214\/aoap\/1060202828","article-title":"Information flow on trees","volume":"13","author":"Mossel","year":"2003","journal-title":"Ann. Appl. Probab"},{"key":"2026032712272297700_ref075","article-title":"Regular Partitions of Graphs","author":"Szemer\u00e9di","year":"1976","journal-title":"Problemes combinatoires et theorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976)"},{"key":"2026032712272297700_ref076","first-page":"17","article-title":"On the Evolution of Random Graphs","author":"Erd\u0151s","year":"1960","journal-title":"Publication of the Mathematical Institute of the Hungarian Academy of Sciences"},{"issue":"4","key":"2026032712272297700_ref077","doi-asserted-by":"crossref","first-page":"639","DOI":"10.1006\/jcss.2001.1773","article-title":"Heuristics for semirandom graph problems","volume":"63","author":"Feige","year":"2001","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"2026032712272297700_ref078","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1002\/rsa.20089","article-title":"Spectral techniques applied to sparse random graphs","volume":"27","author":"Feige","year":"2005","journal-title":"Random Structures & Algorithms"},{"key":"2026032712272297700_ref079","article-title":"The Geometric Block Model","author":"Galhotra","year":"2017","journal-title":"ArXiv:1709.05510"},{"key":"2026032712272297700_ref080","article-title":"Achieving Optimal Misclassification Proportion in Stochastic Block Model","author":"Gao","year":"2015","journal-title":"ArXiv:1505.03772"},{"issue":"3","key":"2026032712272297700_ref081","doi-asserted-by":"publisher","first-page":"031005","DOI":"10.1103\/PhysRevX.6.031005","article-title":"Detectability Thresholds and Optimal Algorithms for Community Structure in Dynamic Networks","volume":"6","author":"Ghasemian","year":"2016","journal-title":"Physical Review X"},{"issue":"12","key":"2026032712272297700_ref082","doi-asserted-by":"publisher","first-page":"7821","DOI":"10.1073\/pnas.122653799","article-title":"Community structure in social and biological networks","volume":"99","author":"Girvan","year":"2002","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"2026032712272297700_ref083","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","article-title":"Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming","volume":"42","author":"Goemans","year":"1995","journal-title":"Journal of the Association for Computing Machinery"},{"key":"2026032712272297700_ref084","doi-asserted-by":"crossref","DOI":"10.1073\/pnas.1221839110","article-title":"Efficient discovery of overlapping communities in massive networks","author":"Gopalan","year":"2013","journal-title":"Proceedings of the National Academy of Sciences"},{"issue":"3","key":"2026032712272297700_ref085","doi-asserted-by":"publisher","first-page":"1025","DOI":"10.1007\/s00440-015-0659-z","article-title":"Community detection in sparse networks via Grothendieck\u2019s inequality","volume":"165","author":"Gu\u00e9don","year":"2016","journal-title":"Probability Theory and Related Fields"},{"key":"2026032712272297700_ref086","article-title":"A spectral method for community detection in moderately-sparse degree-corrected stochastic block models","author":"Gulikers","year":"2015","journal-title":"ArXiv:1506.08621"},{"key":"2026032712272297700_ref087","article-title":"An Impossibility Result for Reconstruction in a Degree-Corrected Planted-Partition Model","author":"Gulikers","year":"2015","journal-title":"ArXiv:1511.00546"},{"issue":"4","key":"2026032712272297700_ref088","doi-asserted-by":"crossref","first-page":"1261","DOI":"10.1109\/TIT.2005.844072","article-title":"Mutual information and minimum mean-square error in Gaussian channels","volume":"51","author":"Guo","year":"2005","journal-title":"Information Theory, IEEE Transactions on"},{"key":"2026032712272297700_ref089","article-title":"Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions","author":"Hajek","year":"2015","journal-title":"ArXiv:1502.07738"},{"key":"2026032712272297700_ref090","article-title":"Information Limits for Recovering a Hidden Community","author":"Hajek","year":"2015","journal-title":"ArXiv:1509.07859"},{"key":"2026032712272297700_ref091","article-title":"Recovering a Hidden Community Beyond the Spectral Limit in O(|E| log* |V|) Time","author":"Hajek","year":"2015","journal-title":"ArXiv:1510.02786"},{"key":"2026032712272297700_ref092","article-title":"Community Detection in the Labelled Stochastic Block Model","author":"Heimlicher","year":"2012","journal-title":"arXiv: 1209.2910"},{"issue":"2","key":"2026032712272297700_ref093","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0378-8733(83)90021-7","article-title":"Stochastic blockmodels: First steps","volume":"5","author":"Holland","year":"1983","journal-title":"Social Networks"},{"key":"2026032712272297700_ref094","article-title":"Bayesian estimation from few samples: community detection and related problems","author":"Hopkins","year":"2017","journal-title":"ArXiv:1710.00264"},{"key":"2026032712272297700_ref095","first-page":"85","article-title":"Eine informationstheoretische Ungleichung und ihre Anwendung auf den Beweis der Ergodizitat von Markoffschen Ketten","volume":"8","author":"Csisz\u00e1r","year":"1963","journal-title":"Magyar. Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl"},{"key":"2026032712272297700_ref096","first-page":"282","volume-title":"Conditional random fields: Probabilistic models for segmenting and labeling sequence data","author":"Lafferty","year":"2001"},{"key":"2026032712272297700_ref097","first-page":"888","article-title":"Normalized Cuts and Image Segmentation","volume":"22","author":"Shi","year":"1997","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"3B","key":"2026032712272297700_ref098","doi-asserted-by":"publisher","first-page":"2630","DOI":"10.1214\/009117904000000153","article-title":"Robust reconstruction on trees is determined by the second eigenvalue","volume":"32","author":"Janson","year":"2004","journal-title":"Ann. Probab"},{"key":"2026032712272297700_ref099","article-title":"Performance of a community detection algorithm based on semidefinite programming","author":"Javanmard","year":"2016","journal-title":"ArXiv:1603.09045"},{"key":"2026032712272297700_ref100","article-title":"De-biasing the lasso: Optimal sample size for Gaussian designs","author":"Javanmard","year":"2015","journal-title":"arXiv: 1508.02757"},{"issue":"1","key":"2026032712272297700_ref101","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1214\/14-AOS1265","article-title":"Fast community detection by SCORE","volume":"43","author":"Jin","year":"2015","journal-title":"Ann. Statist"},{"key":"2026032712272297700_ref102","article-title":"Information-theoretic bounds for exact recovery in weighted stochastic block models using the Renyi divergence","author":"Jog","year":"2015","journal-title":"ArXiv:1509.06418"},{"key":"2026032712272297700_ref103","article-title":"Impact of regularization on Spectral Clustering","author":"Joseph","year":"2013","journal-title":"ArXiv:1312.1733"},{"issue":"6","key":"2026032712272297700_ref104","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevE.91.062803","article-title":"Limitations in the spectral method for graph partitioning: Detectability threshold and localization of eigenvectors","volume":"91","author":"Kawamoto","year":"2015","journal-title":"Phys. Rev. E"},{"issue":"5","key":"2026032712272297700_ref105","doi-asserted-by":"publisher","first-page":"1211","DOI":"10.1214\/aoms\/1177699266","article-title":"A Limit Theorem for Multidimensional Galton-Watson Processes","volume":"37","author":"Kesten","year":"1966","journal-title":"Ann. Math. Statist"},{"key":"2026032712272297700_ref106","article-title":"Community Detection in Hypergraphs, Spiked Tensor Models, and Sum-of-Squares","author":"Kim","year":"2017","journal-title":"ArXiv:1705.02973"},{"issue":"1","key":"2026032712272297700_ref107","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1137\/050640904","article-title":"A Polylogarithmic Approximation of the Minimum Bisection","volume":"48","author":"Krauthgamer","year":"2006","journal-title":"SIAM Review"},{"issue":"52","key":"2026032712272297700_ref108","doi-asserted-by":"publisher","first-page":"20935","DOI":"10.1073\/pnas.1312486110","article-title":"Spectral redemption in clustering sparse networks","volume":"110","author":"Krzakala","year":"2013","journal-title":"Proceedings of the National Academy of Sciences"},{"issue":"11-16","key":"2026032712272297700_ref109","doi-asserted-by":"publisher","first-page":"1481","DOI":"10.1016\/S1389-1286(99)00040-7","article-title":"Trawling the Web for Emerging Cyber-communities","volume":"31","author":"Kumar","year":"1999","journal-title":"Comput. Netw"},{"key":"2026032712272297700_ref110","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1145\/1134271.1134277","volume-title":"The Political Blogosphere and the 2004 U.S. Election: Divided They Blog","author":"Adamic","year":"2005"},{"issue":"6","key":"2026032712272297700_ref111","doi-asserted-by":"crossref","first-page":"933","DOI":"10.1016\/j.jctb.2006.05.002","article-title":"Limits of dense graph sequences","volume":"96","author":"Lov\u00e1sz","year":"2006","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"2026032712272297700_ref112","article-title":"Sparse random graphs: regularization and concentration of the Laplacian","author":"Le","year":"2015","journal-title":"ArXiv:1502.03049"},{"key":"2026032712272297700_ref113","article-title":"Fundamental limits of symmetric low-rank matrix estimation","author":"Lelarge","year":"2016","journal-title":"arXiv: 1611.03888"},{"key":"2026032712272297700_ref114","article-title":"MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel","author":"Lesieur","year":"2015","journal-title":"ArXiv:1507.03857"},{"issue":"1","key":"2026032712272297700_ref115","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1109\/MIC.2003.1167344","article-title":"Amazon.Com Recommendations: Item-to-Item Collaborative Filtering","volume":"7","author":"Linden","year":"2003","journal-title":"IEEE Internet Computing"},{"key":"2026032712272297700_ref116","doi-asserted-by":"crossref","DOI":"10.1090\/coll\/060","volume-title":"Large Networks and Graph Limits. American Mathematical Society colloquium publications","author":"Lov\u00e1sz","year":"2012"},{"key":"2026032712272297700_ref117","doi-asserted-by":"crossref","first-page":"812","DOI":"10.1126\/science.1073287","article-title":"Analytic and Algorithmic Solution of Random Satisfiability Problems","volume":"297","author":"M\u00e9zard","year":"2003","journal-title":"Science"},{"key":"2026032712272297700_ref118","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001","volume-title":"Networks: an introduction","author":"Newman","year":"2010"},{"issue":"4","key":"2026032712272297700_ref119","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1016\/0196-6774(89)90001-1","article-title":"The solution of some random NP-hard problems in polynomial expected time","volume":"10","author":"Dyer","year":"1989","journal-title":"Journal of Algorithms"},{"key":"2026032712272297700_ref120","article-title":"Learning Communities in the Presence of Errors","author":"Makarychev","year":"2015","journal-title":"arXiv: 1511.03229 [cs.DS]"},{"issue":"5428","key":"2026032712272297700_ref121","doi-asserted-by":"publisher","first-page":"751","DOI":"10.1126\/science.285.5428.751","article-title":"Detecting Protein Function and Protein-Protein Interactions from Genome Sequences","volume":"285","author":"Marcotte","year":"1999","journal-title":"Science"},{"key":"2026032712272297700_ref122","first-page":"1","volume-title":"Community detection thresholds and the weak Ramanujan property","author":"Massouli\u00e9","year":"2014"},{"key":"2026032712272297700_ref123","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1109\/SFCS.2001.959929","volume-title":"Spectral partitioning of random graphs","author":"McSherry","year":"2001"},{"issue":"6","key":"2026032712272297700_ref124","doi-asserted-by":"publisher","first-page":"1317","DOI":"10.1007\/s10955-006-9162-3","article-title":"Reconstruction on Trees and Spin Glass Transition","volume":"124","author":"M\u00e9zard","year":"2006","journal-title":"English. Journal of Statistical Physics"},{"key":"2026032712272297700_ref125","first-page":"828","volume-title":"How robust are reconstruction thresholds for community detection?","author":"Moitra","year":"2016"},{"key":"2026032712272297700_ref126","doi-asserted-by":"publisher","first-page":"814","DOI":"10.1145\/2897518.2897548","volume-title":"Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing. STOC 2016","author":"Montanari","year":"2016"},{"key":"2026032712272297700_ref127","article-title":"The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness","author":"Moore","year":"2017","journal-title":"ArXiv:1702.00467"},{"key":"2026032712272297700_ref128","article-title":"A Proof Of The Block Model Threshold Conjecture","author":"Mossel","year":"2014","journal-title":"arXiv: 1311.4115"},{"key":"2026032712272297700_ref129","article-title":"Density Evolution in the Degree-correlated Stochastic Block Model","author":"Mossel","year":"2015","journal-title":"ArXiv:1509.03281"},{"issue":"3","key":"2026032712272297700_ref130","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/s00440-014-0576-6","article-title":"Reconstruction and estimation in the planted partition model","volume":"162","author":"Mossel","year":"2015","journal-title":"Probability Theory and Related Fields"},{"key":"2026032712272297700_ref131","first-page":"467","volume-title":"Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence. UAI\u201999","author":"Murphy","year":"1999"},{"issue":"18","key":"2026032712272297700_ref132","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.108.188701","article-title":"Graph Spectra and the Detectability of Community Structure in Networks","volume":"108","author":"Nadakuditi","year":"2012","journal-title":"Phys. Rev. Lett"},{"issue":"1","key":"2026032712272297700_ref133","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1038\/nphys2162","article-title":"Communities, modules and large-scale structure in networks","volume":"8","author":"Newman","year":"2011","journal-title":"Nature Physics"},{"key":"2026032712272297700_ref134","doi-asserted-by":"crossref","first-page":"2566","DOI":"10.1073\/pnas.012582999","article-title":"Random Graph Models of Social Networks","volume":"99","author":"Newman","journal-title":"Proc. Natl. Acad. Sci. USA"},{"issue":"8","key":"2026032712272297700_ref135","doi-asserted-by":"crossref","first-page":"088701","DOI":"10.1103\/PhysRevLett.115.088701","article-title":"Generalized communities in networks","volume":"115","author":"Newman","year":"2015","journal-title":"Phys. Rev. Lett"},{"key":"2026032712272297700_ref136","article-title":"Random perturbation of low rank matrices: Improving classical bounds","author":"O\u2019Rourke","year":"2013","journal-title":"arXiv: 1311.2657 [math.NA]"},{"issue":"41","key":"2026032712272297700_ref137","doi-asserted-by":"publisher","first-page":"14722","DOI":"10.1073\/pnas.1400374111","article-title":"Network histograms and universality of blockmodel approximation","volume":"111","author":"Olhede","year":"2014","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"2026032712272297700_ref138","article-title":"Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery","author":"Chin","year":"2015","journal-title":"arXiv:1501.05021"},{"key":"2026032712272297700_ref139","doi-asserted-by":"crossref","first-page":"814","DOI":"10.1038\/nature03607","article-title":"Uncovering the overlapping community structure of complex networks in nature and society","volume":"435","author":"Palla","year":"2005","journal-title":"Nature"},{"issue":"1","key":"2026032712272297700_ref140","first-page":"011033","article-title":"Model selection and hypothesis testing for large-scale network models with overlapping groups","volume":"5","author":"Peixoto","year":"2015","journal-title":"Phys. Rev. X"},{"key":"2026032712272297700_ref141","article-title":"A semidefinite program for unbalanced multisection in the stochastic block model","author":"Perry","year":"2015","journal-title":"arXiv: 1507.05605 [cs.DS]"},{"key":"2026032712272297700_ref142","article-title":"Statistical limits of spiked tensor models","author":"Perry","year":"2016","journal-title":"ArXiv:1612.07728"},{"key":"2026032712272297700_ref143","article-title":"Message-passing algorithms for synchronization problems over compact groups","author":"Perry","year":"2016","journal-title":"ArXiv:1610.04583"},{"key":"2026032712272297700_ref144","article-title":"Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization","author":"Perry","year":"2016","journal-title":"ArXiv:1609.05573"},{"issue":"7","key":"2026032712272297700_ref145","doi-asserted-by":"crossref","first-page":"078701","DOI":"10.1103\/PhysRevLett.101.078701","article-title":"(Un)detectable cluster structure in sparse networks","volume":"101","author":"Reichardt","year":"2008","journal-title":"Phys. Rev. Lett"},{"issue":"3-5","key":"2026032712272297700_ref146","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.physrep.2009.11.002","article-title":"Community detection in graphs","volume":"486","author":"Fortunato","year":"2010","journal-title":"Physics Reports"},{"key":"2026032712272297700_ref147","article-title":"Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms","author":"Yun","year":"2014","journal-title":"arXiv:1412.7335"},{"key":"2026032712272297700_ref148","volume-title":"Community-Based Recommendations: a Solution to the Cold Start Problem","author":"Sahebi","year":"2011"},{"issue":"July","key":"2026032712272297700_ref149","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","article-title":"A Mathematical Theory of Communication","volume":"27","author":"Shannon","year":"1948","journal-title":"The Bell System Technical Journal"},{"issue":"1","key":"2026032712272297700_ref150","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/s003579900004","article-title":"Estimation and Prediction for Stochastic Blockmodels for Graphs with Latent Block Structure","volume":"14","author":"Snijders","year":"1997","journal-title":"Journal of Classification"},{"issue":"19","key":"2026032712272297700_ref151","doi-asserted-by":"publisher","first-page":"10869","DOI":"10.1073\/pnas.191367098","volume":"98","author":"Sorlie","year":"2001","journal-title":"Gene expression patterns of breast carcinomas distinguish tumor subclasses with clinical implications"},{"issue":"6","key":"2026032712272297700_ref152","doi-asserted-by":"publisher","first-page":"1913","DOI":"10.1137\/080734029","article-title":"Graph Sparsification by Effective Resistances","volume":"40","author":"Spielman","year":"2011","journal-title":"SIAM Journal on Computing"},{"key":"2026032712272297700_ref153","first-page":"1","volume-title":"Codes, Systems, and Graphical Models. IMA Volume in Mathematics and Its Applications","author":"Richardson","year":"2001"},{"key":"2026032712272297700_ref154","article-title":"A simple SVD algorithm for finding hidden partitions","author":"Vu","year":"2014","journal-title":"Available at arXiv:1404.3918. To appear in CPC"},{"issue":"6","key":"2026032712272297700_ref155","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1007\/s00493-007-2190-z","article-title":"Spectral Norm of Random Matrices","volume":"27","author":"Vu","year":"2007","journal-title":"Combinatorica"},{"key":"2026032712272297700_ref156","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1214\/aoap\/1019487349","article-title":"Broadcasting on trees and the Ising model","volume":"10","author":"Evans","year":"2000","journal-title":"Ann. Appl. Probab"},{"key":"2026032712272297700_ref157","article-title":"Nonparametric graphon estimation","author":"Wolfe","year":"2013","journal-title":"ArXiv:1309.5936"},{"key":"2026032712272297700_ref158","article-title":"Clustering and Inference From Pairwise Comparisons","author":"Wu","year":"2015","journal-title":"ArXiv:1502.04631"},{"key":"2026032712272297700_ref159","doi-asserted-by":"publisher","first-page":"1070","DOI":"10.1109\/ACSSC.2015.7421303","volume-title":"Achieving exact cluster recovery threshold via semidefinite programming under the stochastic block model","author":"Wu","year":"2015"},{"key":"2026032712272297700_ref160","article-title":"Edge Label Inference in Generalized Stochastic Block Models: from Spectral Theory to Impossibility Results","author":"Xu","year":"2014","journal-title":"Proceedings of COLT 2014"},{"key":"2026032712272297700_ref161","article-title":"Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices","author":"Chen","year":"2014","journal-title":"arXiv:1402.1267"},{"key":"2026032712272297700_ref162","article-title":"Asymptotic Mutual Information for the Two-Groups Stochastic Block Model","author":"Deshpande","year":"2015","journal-title":"arXiv:1507.08685"},{"key":"2026032712272297700_ref163","article-title":"Finite size analysis of the detectability limit of the stochastic block model","author":"Young","year":"2016","journal-title":"arXiv:1701.00062"},{"key":"2026032712272297700_ref164","article-title":"Community Detection via Random and Adaptive Sampling","author":"Yun","year":"2014","journal-title":"ArXiv e-prints 1402.3072. In proc. COLT14"},{"key":"2026032712272297700_ref165","article-title":"Optimal Cluster Recovery in the Labeled Stochastic Block Model","author":"Yun","year":"2015","journal-title":"ArXiv:1510.05956"},{"issue":"1","key":"2026032712272297700_ref166","doi-asserted-by":"publisher","first-page":"012303","DOI":"10.1103\/PhysRevE.93.012303","article-title":"Community detection in networks with unequal groups","volume":"93","author":"Zhang","year":"2016","journal-title":"Phys. Rev. E"},{"issue":"5","key":"2026032712272297700_ref167","doi-asserted-by":"publisher","first-page":"052802","DOI":"10.1103\/PhysRevE.90.052802","article-title":"Phase transitions in semisupervised clustering of sparse networks","volume":"90","author":"Zhang","year":"2014","journal-title":"Phys. Rev. E"},{"key":"2026032712272297700_ref168","article-title":"Near-optimal bounds for phase synchronization","author":"Zhong","year":"2017","journal-title":"arXiv preprint arXiv:1703.06605"}],"container-title":["Foundations and Trends\u00ae in Communications and Information Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.emerald.com\/ftcit\/article-pdf\/14\/1-2\/1\/11024029\/0100000067en.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/www.emerald.com\/ftcit\/article-pdf\/14\/1-2\/1\/11024029\/0100000067en.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T16:27:45Z","timestamp":1774628865000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.emerald.com\/ftcit\/article\/14\/1-2\/1\/1326454\/Community-Detection-and-Stochastic-Block-Models"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,7]]},"references-count":168,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2018,6,7]]}},"URL":"https:\/\/doi.org\/10.1561\/0100000067","relation":{},"ISSN":["1567-2190","1567-2328"],"issn-type":[{"value":"1567-2190","type":"print"},{"value":"1567-2328","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,6,7]]}}}