The DOI matches its Crossref record; 97 of the 97 references it cites were found in a registry or an index.
Community Detection and Stochastic Block Models
Abstract
The field of community detection has been expanding greatly since the 1980s, with a remarkable diversity of models and algorithms developed in different communities like machine learning, computer science, network science, social science, and statistical physics. Various fundamental questions remain nonetheless unsettled, such as: Are there really communities? Algorithms may output community structures, but are these meaningful or artefacts? Can we always extract the communities when they are present; fully, partially? And what is a good benchmark to measure the performance of algorithms, and how good are the current algorithms? This monograph describes recent developments aiming at answering these questions in the context of block models. Addressing the issues from an information-theoretic view-point, the author gives a comprehensive description of the historical and recent work that has led to key new concepts in the various recovery requirements for community detection. The monograph provides a compact introduction to community detection, which enables the reader to apply these techniques in applications such as understanding sociological behavior, protein to protein interactions; gene expressions; recommendation systems; medical prognosis; DNA 3D folding; image segmentation, natural language processing, product-customer segmentation, webpage sorting, and many more.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A Mathematical Theory of Communication
Shannon, C. E. (1948) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1948.tb01338.x · Cited by 88,486
Community structure in social and biological networks
Girvan, M., & Newman, M. E. J. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.122653799 · Cited by 15,502
Normalized cuts and image segmentation
Shi, J., & Malik, J. (2000) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.868688 · Cited by 15,502
Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data
Lafferty, J., McCallum, A., & Pereira, F. C. N. (2001) · ScholarlyCommons (University of Pennsylvania) · Cited by 12,935
Fortunato, S. (2010) · Physics Reports · doi:10.1016/j.physrep.2009.11.002 · Cited by 11,293
Sørlie, T., Perou, C. M., Tibshirani, R., Aas, T., Geisler, S., Johnsen, H., Hastie, T., Eisen, M. B., van de Rijn, M., Jeffrey, S. S., et al. (2001) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.191367098 · Cited by 10,938
A tutorial on spectral clustering
von Luxburg, U. (2007) · Statistics and Computing · doi:10.1007/s11222-007-9033-z · Cited by 10,349
On Spectral Clustering: Analysis and an algorithm
Ng, A. Y., Jordan, M. I., & Weiss, Y. (2001) · Cited by 8,159
Finding community structure in very large networks
Clauset, A., Newman, M. E. J., & Moore, C. (2004) · Physical Review E · doi:10.1103/physreve.70.066111 · Cited by 7,390
Newman, M. (2010) · doi:10.1093/acprof:oso/9780199206650.001.0001 · Cited by 6,595
The Evolution of Random Graphs
(1986) · CBMS Regional Conference Series in Mathematics · doi:10.1090/cbms/062/06 · Cited by 5,543
Amazon.com recommendations: item-to-item collaborative filtering
Linden, G., Smith, B., & York, J. (2003) · IEEE Internet Computing · doi:10.1109/mic.2003.1167344 · Cited by 5,403
Uncovering the overlapping community structure of complex networks in nature and society
Palla, G., Derényi, I., Farkas, I., & Vicsek, T. (2005) · Nature · doi:10.1038/nature03607 · Cited by 5,373
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587
Understanding Machine Learning: From Theory to Algorithms
Shalev-Shwartz, S., & Ben-David, S. (2014) · doi:10.1017/cbo9781107298019 · Cited by 3,115
(2015) · Cited by 2,857
Stochastic blockmodels: First steps
Holland, P. W., Laskey, K. B., & Leinhardt, S. (1983) · Social Networks · doi:10.1016/0378-8733(83)90021-7 · Cited by 2,755
The political blogosphere and the 2004 U.S. election: divided they blog
Adamic, L. A., & Glance, N. (2005) · Proceedings of the 3rd international workshop on Link discovery · doi:10.1145/1134271.1134277 · Cited by 2,619
Integration of biological networks and gene expression data using Cytoscape
Cline, M. S., Smoot, M., Cerami, E., Kuchinsky, A., Landys, N., Workman, C., Christmas, R., Avila-Campilo, I., Creech, M., Gross, B., et al. (2007) · Nature Protocols · doi:10.1038/nprot.2007.324 · Cited by 2,507
Message-passing algorithms for compressed sensing
Donoho, D. L., Maleki, A., & Montanari, A. (2009) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0909892106 · Cited by 2,416
Stochastic blockmodels and community structure in networks
Karrer, B., & Newman, M. E. J. (2011) · Physical Review E · doi:10.1103/physreve.83.016107 · Cited by 2,025
On the evolution of random graphs
Erdös, P., & Rényi, A. (2011) · The Structure and Dynamics of Networks · doi:10.1515/9781400841356.38 · Cited by 1,757
Detecting Protein Function and Protein-Protein Interactions from Genome Sequences
Marcotte, E. M., Pellegrini, M., Ng, H.-L., Rice, D. W., Yeates, T. O., & Eisenberg, D. (1999) · Science · doi:10.1126/science.285.5428.751 · Cited by 1,670
Random graph models of social networks
Newman, M. E. J., Watts, D. J., & Strogatz, S. H. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.012582999 · Cited by 1,326
Cluster analysis for gene expression data: a survey
Jiang, D., Tang, C., & Zhang, A. (2004) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2004.68 · Cited by 1,235
Mutual Information and Minimum Mean-Square Error in Gaussian Channels
Guo, D., Shamai, S., & Verdu, S. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.844072 · Cited by 1,201
Bipartite network projection and personal recommendation
Zhou, T., Ren, J., Medo, M., & Zhang, Y.-C. (2007) · Physical Review E · doi:10.1103/physreve.76.046115 · Cited by 1,088
Analytic and Algorithmic Solution of Random Satisfiability Problems
Mézard, M., Parisi, G., & Zecchina, R. (2002) · Science · doi:10.1126/science.1073287 · Cited by 1,071
Trawling the Web for emerging cyber-communities
Kumar, R., Raghavan, P., Rajagopalan, S., & Tomkins, A. (1999) · Computer Networks · doi:10.1016/s1389-1286(99)00040-7 · Cited by 1,000
Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
Baik, J., Ben Arous, G., & Péché, S. (2005) · The Annals of Probability · doi:10.1214/009117905000000233 · Cited by 967
A Survey of Statistical Network Models
Goldenberg, A., Zheng, A. X., Fienberg, S. E., & Airoldi, E. M. (2010) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000005 · Cited by 819
Communities, modules and large-scale structure in networks
Newman, M. E. J. (2012) · Nature Physics · doi:10.1038/nphys2162 · Cited by 787
Mixed membership stochastic blockmodels
Airoldi, E. M., Blei, D. M., Fienberg, S. E., & Xing, E. P. (2007) · arXiv (Cornell University) · doi:10.48550/arxiv.0705.4485 · Cited by 781
A nonparametric view of network models and Newman–Girvan and other modularities
Bickel, P. J., & Chen, A. (2009) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0907096106 · Cited by 765
Decelle, A., Krzakala, F., Moore, C., & Zdeborová, L. (2011) · Physical Review E · doi:10.1103/physreve.84.066106 · Cited by 747
Estimation and Prediction for Stochastic Blockmodels for Graphs with Latent Block Structure
Snijders, T. A. B., & Nowicki, K. (1997) · Journal of Classification · doi:10.1007/s003579900004 · Cited by 653
Spectral redemption in clustering sparse networks
Krzakala, F., Moore, C., Mossel, E., Neeman, J., Sly, A., Zdeborová, L., & Zhang, P. (2013) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1312486110 · Cited by 638
Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing
Borgs, C., Chayes, J. T., Lovász, L., Sós, V. T., & Vesztergombi, K. (2008) · Advances in Mathematics · doi:10.1016/j.aim.2008.07.008 · Cited by 590
Spectral partitioning of random graphs
McSherry, F. (2001) · Proceedings 42nd IEEE Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2001.959929 · Cited by 584
Exact Recovery in the Stochastic Block ModelPreprint
Hall, E. G. (2016) · Cited by 469
Representations for partially exchangeable arrays of random variables
Aldous, D. J. (1981) · Journal of Multivariate Analysis · doi:10.1016/0047-259x(81)90099-3 · Cited by 442
Detecting functional modules in the yeast protein–protein interaction network
Chen, J., & Yuan, B. (2006) · Bioinformatics · doi:10.1093/bioinformatics/btl370 · Cited by 440
Algorithms for graph partitioning on the planted partition model
Condon, A., & Karp, R. M. (2001) · Random Structures and Algorithms · doi:10.1002/1098-2418(200103)18:2<116::aid-rsa1001>3.0.co;2-2 · Cited by 429
Efficient and principled method for detecting communities in networks
Ball, B., Karrer, B., & Newman, M. E. J. (2011) · Physical Review E · doi:10.1103/physreve.84.036103 · Cited by 386
On clusterings-good, bad and spectral
Kannan, R., Vempala, S., & Veta, A. (2002) · Proceedings 41st Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892125 · Cited by 372
Graph bisection algorithms with good average case behavior
Bui, T. N., Chaudhuri, S., Leighton, F. T., & Sipser, M. (1987) · Combinatorica · doi:10.1007/bf02579448 · Cited by 323
Graph Spectra and the Detectability of Community Structure in Networks
Nadakuditi, R. R., & Newman, M. E. J. (2012) · Physical Review Letters · doi:10.1103/physrevlett.108.188701 · Cited by 316
Community detection thresholds and the weak Ramanujan property
Massoulié, L. (2014) · Proceedings of the forty-sixth annual ACM symposium on Theory of computing · doi:10.1145/2591796.2591857 · Cited by 316
A Limit Theorem for Multidimensional Galton-Watson Processes
Kesten, H., & Stigum, B. P. (1966) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177699266 · Cited by 310
Fast community detection by SCORE
Jin, J. (2015) · The Annals of Statistics · doi:10.1214/14-aos1265 · Cited by 302
Reconstruction and estimation in the planted partition model
Mossel, E., Neeman, J., & Sly, A. (2015) · Probability Theory and Related Fields · doi:10.1007/s00440-014-0576-6 · Cited by 301
Efficient discovery of overlapping communities in massive networks
Gopalan, P. K., & Blei, D. M. (2013) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1221839110 · Cited by 272
Broadcasting on trees and the Ising model
Evans, W., Kenyon, C., Peres, Y., & Schulman, L. J. (2000) · The Annals of Applied Probability · doi:10.1214/aoap/1019487349 · Cited by 270
Finding a large hidden clique in a random graph
Alon, N., Krivelevich, M., & Sudakov, B. (1998) · Random Structures and Algorithms · doi:10.1002/(sici)1098-2418(199810/12)13:3/4<457::aid-rsa14>3.0.co;2-w · Cited by 262
Abbe, E., & Sandon, C. (2015) · 2015 IEEE 56th Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2015.47 · Cited by 254
Self-citationOptimal detection of sparse principal components in high dimension
Berthet, Q., & Rigollet, P. (2013) · The Annals of Statistics · doi:10.1214/13-aos1127 · Cited by 247
Spectral techniques applied to sparse random graphs
Feige, U., & Ofek, E. (2005) · Random Structures & Algorithms · doi:10.1002/rsa.20089 · Cited by 221
Stochastic blockmodels with a growing number of classes
Choi, D. S., Wolfe, P. J., & Airoldi, E. M. (2012) · Biometrika · doi:10.1093/biomet/asr053 · Cited by 220
Spectral partitioning works: Planar graphs and finite element meshes
Spielman, D. A., & Teng, S.-H. (2007) · Linear Algebra and its Applications · doi:10.1016/j.laa.2006.07.020 · Cited by 209
A proof of alon's second eigenvalue conjecture
Friedman, J. (2003) · Proceedings of the thirty-fifth annual ACM symposium on Theory of computing · doi:10.1145/780542.780646 · Cited by 192
The solution of some random NP-hard problems in polynomial expected time
Dyer, M., & FRIEZE, A. M. (1989) · Journal of Algorithms · doi:10.1016/0196-6774(89)90001-1 · Cited by 189
The two possible values of the chromatic number of a random graph
Achlioptas, D., & Naor, A. (2005) · Annals of Mathematics · doi:10.4007/annals.2005.162.1335 · Cited by 188
Chen, Y., & Xu, J. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1402.1267 · Cited by 184
Network histograms and universality of blockmodel approximation
Olhede, S. C., & Wolfe, P. J. (2014) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1400374111 · Cited by 176
Semidefinite programs on sparse random graphs and their application to community detection
Andrea Montanari, A., & Sen, S. (2016) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2897518.2897548 · Cited by 169
Community detection in sparse networks via Grothendieck’s inequality
Guédon, O., & Vershynin, R. (2016) · Probability Theory and Related Fields · doi:10.1007/s00440-015-0659-z · Cited by 168
Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
Hajek, B., Wu, Y., & Xu, J. (2016) · IEEE Transactions on Information Theory · doi:10.1109/tit.2016.2546280 · Cited by 164
Graph Partitioning via Adaptive Spectral Techniques
Coja‐Oghlan, A. (2009) · Combinatorics Probability Computing · doi:10.1017/s0963548309990514 · Cited by 159
Mossel, E., & Peres, Y. (2003) · The Annals of Applied Probability · doi:10.1214/aoap/1060202828 · Cited by 146
Information-theoretically optimal sparse PCA
Deshpande, Y., & Andrea Montanari, A. (2014) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2014.6875223 · Cited by 140
Decoding Binary Node Labels from Censored Edge Measurements: Phase Transition and Efficient Recovery
Abbe, E. A., Bandeira, A. S., Bracher, A., & Singer, A. (2014) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2014.2368716 · Cited by 137
Self-citationOn semidefinite relaxations for the block model
Amini, A., & Levina, E. (2018) · The Annals of Statistics · doi:10.1214/17-aos1545 · Cited by 136
Model Selection and Hypothesis Testing for Large-Scale Network Models with Overlapping Groups
Peixoto, T. P. (2015) · Physical Review X · doi:10.1103/physrevx.5.011033 · Cited by 135
Spectral norm of random matrices
Vu, V. H. (2007) · COMBINATORICA · doi:10.1007/s00493-007-2190-z · Cited by 132
Detectability Thresholds and Optimal Algorithms for Community Structure in Dynamic Networks
Ghasemian, A., Zhang, P., Clauset, A. J., Moore, C., & Peel, L. (2016) · Physical Review X · doi:10.1103/physrevx.6.031005 · Cited by 123
Near-Optimal Joint Object Matching via Convex RelaxationPreprint
Chen, Y., Guibas, L. J., & Huang, Q. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1402.1473 · Cited by 121
Abbe, E., & Sandon, C. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1512.09080 · Cited by 119
Self-citationAchieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
Hajek, B., Wu, Y., & Xu, J. (2016) · IEEE Transactions on Information Theory · doi:10.1109/tit.2016.2594812 · Cited by 108
Random Laplacian Matrices and Convex Relaxations
Bandeira, A. S. (2016) · Foundations of Computational Mathematics · doi:10.1007/s10208-016-9341-9 · Cited by 101
Community-Based Recommendations: a Solution to the Cold Start Problem
Sahebi, S., & Cohen, W. W. (2011) · D-Scholarship@Pitt (University of Pittsburgh) · Cited by 97
Generalized Communities in Networks
Newman, M. E. J., & Peixoto, T. P. (2015) · Physical Review Letters · doi:10.1103/physrevlett.115.088701 · Cited by 82
(Un)detectable Cluster Structure in Sparse Networks
Reichardt, J., & Leone, M. (2008) · Physical Review Letters · doi:10.1103/physrevlett.101.078701 · Cited by 74
Achieving Optimal Misclassification Proportion in Stochastic Block ModelPreprint
Gao, C., Ma, Z., Zhang, A. Y., & Zhou, H. H. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1505.03772 · Cited by 74
Private Graphon Estimation for Sparse GraphsPreprint
Borgs, C., Chayes, J., & Smith, A. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1506.06162 · Cited by 68
Accurate Community Detection in the Stochastic Block Model via Spectral AlgorithmsPreprint
Yun, S.-Y., & Proutière, A. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1412.7335 · Cited by 56
Phase transitions in semisupervised clustering of sparse networks
Zhang, P., Moore, C., & Zdeborová, L. (2014) · Physical Review E · doi:10.1103/physreve.90.052802 · Cited by 55
A Polylogarithmic Approximation of the Minimum Bisection
Krauthgamer, R., & Feige, U. (2006) · SIAM Review · doi:10.1137/050640904 · Cited by 55
Community detection in networks with unequal groups
Zhang, P., Moore, C., & Newman, M. E. J. (2016) · Physical review. E · doi:10.1103/physreve.93.012303 · Cited by 49
Optimal Cluster Recovery in the Labeled Stochastic Block ModelPreprint
Yun, S.-Y., & Proutière, A. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1510.05956 · Cited by 47
Consistency Thresholds for Binary Symmetric Block Models.Preprint
Mossel, E., Neeman, J., & Sly, A. (2014) · Cited by 46
A semidefinite program for unbalanced multisection in the stochastic block model
Perry, A., & Wein, A. S. (2017) · International Conference on Sampling Theory and Applications · doi:10.1109/sampta.2017.8024399 · Cited by 45
Multisection in the Stochastic Block Model Using Semidefinite Programming
Agarwal, N., Bandeira, A. S., Koiliaris, K., & Kolla, A. (2017) · Applied and numerical harmonic analysis · doi:10.1007/978-3-319-69802-1_4 · Cited by 43
Community Detection in Networks using Graph DistancePreprint
Bhattacharyya, S., & Bickel, P. J. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1401.3915 · Cited by 34
Detecting community structures in Hi-C genomic data
Cabreros, I., Abbe, E. A., & Tsirigos, A. (2016) · Conference on Information Sciences and Systems · doi:10.1109/ciss.2016.7460568 · Cited by 32
Self-citationKawamoto, T., & Kabashima, Y. (2015) · Physical Review E · doi:10.1103/physreve.91.062803 · Cited by 29
Information recovery from pairwise measurements
Chen, Y., & Goldsmith, A. J. (2014) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2014.6875186 · Cited by 18
Linear inverse problems on Erdős-Rényi graphs: Information-theoretic limits and efficient recovery
Abbe, E. A., Bandeira, A. S., Bracher, A., & Singer, A. (2014) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2014.6875033 · Cited by 10
Self-citation
Cited by
A Generalization of Transformer Networks to Graphs
Dwivedi, V. P., & Bresson, X. (2020) · arXiv · doi:10.48550/arxiv.2012.09699 · Cited by 398
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
Chi, Y., Lu, Y. M., & Chen, Y. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2019.2937282 · Cited by 360
A Comprehensive Survey on Community Detection With Deep Learning
Su, X., Xue, S., Liu, F., Wu, J., Yang, J., Zhou, C., Hu, W., Paris, C., Nepal, S., Jin, D., et al. (2024) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2021.3137396 · Cited by 353
Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss
HaoChen, J. Z., Wei, C., Gaidon, A., & Ma, T. (2021) · arXiv · doi:10.48550/arxiv.2106.04156 · Cited by 53
Subspace Estimation from Unbalanced and Incomplete Data Matrices: 𝓁2, ∞ Statistical Guarantees
Cai, C., Li, G., Chi, Y., Poor, H. V., & Chen, Y. (2021) · The Annals of Statistics · doi:10.1214/20-aos1986 · Cited by 37
Metadata
- Authors
- Abbe, E.
- Venue
- now publishers, Inc. eBooks
- Publisher
- now Publishers Inc
- Published
- 2018
- OpenAlex
- W2559839022
- Cited by
- 544
- References
- 97
- FWCI
- 32.03
- Type
- book
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.