The DOI matches its Crossref record; 55 of the 55 references it cites were found in a registry or an index.
Community Detection in General Stochastic Block models: Fundamental Limits and Efficient Algorithms for Recovery
Abstract
New phase transition phenomena have recently been discovered for the stochastic block model, for the special case of two non-overlapping symmetric communities. This gives raise in particular to new algorithmic challenges driven by the thresholds. This paper investigates whether a general phenomenon takes place for multiple communities, without imposing symmetry. In the general stochastic block model SBM(n,p,W), n vertices are split into k communities of relative size {pi}i∈[k], and vertices in community i and j connect independently with probability {Wij}i,j∈[k]. This paper investigates the partial and exact recovery of communities in the general SBM (in the constant and logarithmic degree regimes), and uses the generality of the results to tackle overlapping communities. The contributions of the paper are: (i) an explicit characterization of the recovery threshold in the general SBM in terms of a new f-divergence function D+, which generalizes the Hellinger and Chernoff divergences, and which provides an operational meaning to a divergence function analog to the KL-divergence in the channel coding theorem, (ii) the development of an algorithm that recovers the communities all the way down to the optimal threshold and runs in quasi-linear time, showing that exact recovery has no information-theoretic to computational gap for multiple communities, (iii) the development of an efficient algorithm that detects communities in the constant degree regime with an explicit accuracy bound that can be made arbitrarily close to 1 when a prescribed signal-to-noise ratio [defined in terms of the spectrum of diag(p)W] tends to infinity.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Inference of Population Structure Using Multilocus Genotype Data
Pritchard, J. K., Stephens, M., & Donnelly, P. (2000) · Genetics · doi:10.1093/genetics/155.2.945 · Cited by 33,908
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
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
Strogatz, S. H. (2001) · Nature · doi:10.1038/35065725 · Cited by 8,302
Newman, M. (2010) · doi:10.1093/acprof:oso/9780199206650.001.0001 · Cited by 6,595
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
Image Processing, Analysis and Machine Vision
Sonka, M., Hlavac, V., & Boyle, R. (1993) · Springer eBooks · doi:10.1007/978-1-4899-3216-7 · Cited by 3,717
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
Social Structure from Multiple Networks. I. Blockmodels of Roles and Positions
White, H. C., Boorman, S. A., & Breiger, R. L. (1976) · American Journal of Sociology · doi:10.1086/226141 · Cited by 2,097
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
Image processing, analysis and machine vision
Dijkstra, T. (1994) · Neurocomputing · doi:10.1016/0925-2312(94)90073-6 · Cited by 1,805
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
A General Class of Coefficients of Divergence of One Distribution from Another
Ali, S. M., & Silvey, S. D. (1966) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1966.tb00626.x · Cited by 1,205
Statistical properties of community structure in large social and information networks
Leskovec, J., Lang, K. J., Dasgupta, A., & Mahoney, M. W. (2008) · Proceedings of the 17th international conference on World Wide Web · doi:10.1145/1367497.1367591 · Cited by 860
Social Structure from Multiple Networks. II. Role Structures
Boorman, S. A., & White, H. C. (1976) · American Journal of Sociology · doi:10.1086/226228 · Cited by 788
SPECTRAL CLUSTERING AND THE HIGH-DIMENSIONAL STOCHASTIC BLOCKMODEL
Rohe, K., Chatterjee, S., & Yu, B. (2010) · Cited by 782
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 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
Stochastic blockmodels for directed graphs.
Wang, Y. J., & Wong, G. Y. (1987) · Journal of the American Statistical Association · doi:10.1080/01621459.1987.10478385 · Cited by 480
Exact Recovery in the Stochastic Block ModelPreprint
Hall, E. G. (2016) · Cited by 441
Detecting functional modules in the yeast protein–protein interaction network
Chen, J., & Yuan, B. (2006) · Bioinformatics · doi:10.1093/bioinformatics/btl370 · Cited by 440
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
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
Statistical Analysis of Multiple Sociometric Relations
Fienberg, S. E., Meyer, M. M., & Wasserman, S. S. (1985) · Journal of the American Statistical Association · doi:10.1080/01621459.1985.10477129 · Cited by 289
Rigorous location of phase transitions in hard optimization problems
Achlioptas, D., Naor, A., & Peres, Y. (2005) · Nature · doi:10.1038/nature03602 · Cited by 279
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
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
Markov Processes and the H-Theorem
Morimoto, T. (1963) · Journal of the Physical Society of Japan · doi:10.1143/jpsj.18.328 · Cited by 216
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
Chen, Y., & Xu, J. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1402.1267 · Cited by 184
Concentration of Measure Inequalities in Information Theory, Communications, and Coding
Raginsky, M., & Sason, I. (2013) · Foundations and Trends in Communications and Information Theory · doi:10.1561/0100000064 · Cited by 180
Consistent Shape Maps via Semidefinite Programming
Huang, Q., & Guibas, L. (2013) · Computer Graphics Forum · doi:10.1111/cgf.12184 · Cited by 170
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
Graph Partitioning via Adaptive Spectral Techniques
Coja‐Oghlan, A. (2009) · Combinatorics Probability Computing · doi:10.1017/s0963548309990514 · Cited by 159
Stochastic Block Models and ReconstructionPreprint
Mossel, E., Neeman, J., & Sly, A. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1202.1499 · Cited by 154
Consistent shape maps via semidefinite programming
Qi-xing Huang, A., & Guibas, L. J. (2013) · doi:10.5555/2600289.2600314 · Cited by 149
On semidefinite relaxations for the block model
Amini, A., & Levina, E. (2018) · The Annals of Statistics · doi:10.1214/17-aos1545 · Cited by 136
Chin, P. S., Rao, A. B., & Vu, V. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1501.05021 · Cited by 118
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 100
Self-citationA Simple SVD Algorithm for Finding Hidden Partitions
Vu, V. (2017) · Combinatorics Probability Computing · doi:10.1017/s0963548317000463 · Cited by 80
Finding overlapping communities in social networks: toward a rigorous approach
Arora, S., Ge, R., Sachdeva, S., & Schoenebeck, G. R. (2012) · ACM Conference on Electronic Commerce (EC) · doi:10.1145/2229012.2229020 · Cited by 77
Consistency Thresholds for Binary Symmetric Block Models.Preprint
Mossel, E., Neeman, J., & Sly, A. (2014) · Cited by 46
Max Cut for Random Graphs with a Planted Partition
BOLLOBÁS, B., & Scott, A. (2004) · Combinatorics Probability Computing · doi:10.1017/s0963548304006303 · Cited by 38
Discovery with Data: Leveraging Statistics with Computer Science to Transform Science and Society
Rudin, C. D., Dunson, D. B., Irizarry, R. A., Ji, H., Laber, E. B., Leek, J. T., McCormick, T. H., Rose, S., Schafer, C., van der Laan, M. J., et al. (2014) · Cited by 34
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
Verdú, S. (1986) · IEEE Transactions on Information Theory · doi:10.1109/tit.1986.1057126 · Cited by 14
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
Community Detection and Stochastic Block Models
Abbe, E. (2018) · now publishers, Inc. eBooks · doi:10.1561/9781680834772 · Cited by 544
Self-citationMetrics for Community Analysis: A Survey
Chakraborty, T., Dalmia, A., Mukherjee, A., & Ganguly, N. (2018) · ACM Computing Surveys · doi:10.1145/3091106 · Cited by 296
Gradient Coding Using the Stochastic Block Model
Charles, Z., & Papailiopoulos, D. (2018) · 2018 IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2018.8437887 · Cited by 23
Metadata
- Authors
- Abbe, E., & Sandon, C.
- Venue
- 2015 IEEE 56th Annual Symposium on Foundations of Computer Science
- Publisher
- IEEE
- Published
- 2015-10
- Pages
- 670-688
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W2219655028
- Cited by
- 254
- References
- 55
- FWCI
- 34.65
- Type
- conference paper
- 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.