Spectral redemption in clustering sparse networks
Open accessThe DOI matches its Crossref record; 33 of the 33 references it cites were found in a registry or an index.
Abstract
Significance: Spectral algorithms are widely applied to data clustering problems, including finding communities or partitions in graphs and networks. We propose a way of encoding sparse data using a “nonbacktracking” matrix, and show that the corresponding spectral algorithm performs optimally for some popular generative models, including the stochastic block model. This is in contrast with classical spectral algorithms, based on the adjacency matrix, random walk matrix, and graph Laplacian, which perform poorly in the sparse case, failing significantly above a recently discovered phase transition for the detectability of communities. Further support for the method is provided by experiments on real networks as well as by theoretical arguments and analogies from probability theory, statistical physics, and the theory of random matrices.
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
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 · cited 2×
“[28] Girvan, M.”
BackgroundA tutorial on spectral clustering
von Luxburg, U. (2007) · Statistics and Computing · doi:10.1007/s11222-007-9033-z · Cited by 10,349
Finding community structure in networks using the eigenvectors of matrices
Newman, M. E. J. (2006) · Physical Review E · doi:10.1103/physreve.74.036104 · Cited by 4,761
An Information Flow Model for Conflict and Fission in Small Groups
Zachary, W. W. (1977) · Journal of Anthropological Research · doi:10.1086/jar.33.4.3629752 · Cited by 4,704
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
Lusseau, D., Schneider, K., Boisseau, O. J., Haase, P., Slooten, E., & Dawson, S. M. (2003) · Behavioral Ecology and Sociobiology · doi:10.1007/s00265-003-0651-y · Cited by 2,277
Richardson, T., & Urbanke, R. (2008) · Cambridge University Press eBooks · doi:10.1017/cbo9780511791338 · Cited by 2,271
On the Distribution of the Roots of Certain Symmetric Matrices
Wigner, E. P. (1958) · The Annals of Mathematics · doi:10.2307/1970008 · Cited by 1,463
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
Self-citationSpectral 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
The phase transition in inhomogeneous random graphs
Bollobás, B., Janson, S., & Riordan, O. (2007) · Random Structures & Algorithms · doi:10.1002/rsa.20168 · Cited by 545
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
Inference and Phase Transitions in the Detection of Modules in Sparse Networks
Decelle, A., Krzakala, F., Moore, C., & Zdeborová, L. (2011) · Physical Review Letters · doi:10.1103/physrevlett.107.065701 · Cited by 392
Self-citationEfficient 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
PSEUDO-LIKELIHOOD METHODS FOR COMMUNITY DETECTION IN LARGE SPARSE NETWORKS
Amini, A., Chen, A., Bickel, P. J., & Levina, E. (2013) · Cited by 335
A proof of Alon’s second eigenvalue conjecture and related problems
Friedman, J. (2008) · Memoirs of the American Mathematical Society · doi:10.1090/memo/0910 · Cited by 328
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
Pseudo-likelihood methods for community detection in large sparse networks
Amini, A. A., Chen, A., Bickel, P. J., & Levina, E. (2013) · The Annals of Statistics · doi:10.1214/13-aos1138 · Cited by 259
Zeta Functions of Finite Graphs and Representations of $p$-Adic Groups
Hashimoto, K.-I. (2018) · Advanced Studies in Pure Mathematics · doi:10.2969/aspm/01510211 · Cited by 255
NON-BACKTRACKING RANDOM WALKS MIX FASTER
Alon, N., Benjamini, I., Lubetzky, E., & SODIN, S. (2007) · Communications in Contemporary Mathematics · doi:10.1142/s0219199707002551 · Cited by 213
The Largest Eigenvalue of Sparse Random Graphs
KRIVELEVICH, M., & SUDAKOV, B. (2003) · Combinatorics, Probability and Computing · doi:10.1017/s0963548302005424 · Cited by 207 · cited 2×
“[18] Krivelevich M and Sudakov B (2003).”
BackgroundGraph Partitioning via Adaptive Spectral Techniques
Coja‐Oghlan, A. (2009) · Combinatorics Probability Computing · doi:10.1017/s0963548309990514 · Cited by 186
Stochastic Block Models and ReconstructionPreprint
Mossel, E., Neeman, J., & Sly, A. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1202.1499 · Cited by 154
Self-citationMossel, E., & Peres, Y. (2003) · The Annals of Applied Probability · doi:10.1214/aoap/1060202828 · Cited by 146
Self-citationNon-backtracking random walks mix faster
Alon, N., Benjamini, I., Lubetzky, E., et al. (2006) · Cited by 108
The non-backtracking spectrum of the universal cover of a graph
Angel, O., Friedman, J., & Hoory, S. (2014) · Transactions of the American Mathematical Society · doi:10.1090/s0002-9947-2014-06255-7 · Cited by 88
Scalable Inference of Overlapping Communities
Gopalan, P., Gerrish, S., Freedman, M. J., Blei, D. M., & Mimno, D. (2012) · Cited by 83
Graph Characterization via Ihara Coefficients
Ren, P., Wilson, R. C., & Hancock, E. R. (2010) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2010.2091969 · Cited by 74
Comparative Study for Inference of Hidden Classes in Stochastic Block ModelsPreprint
Zhang, P., & Krząkała, F. (n.d.) · Cited by 30
Self-citationRandom matrices, nonbacktracking walks, and orthogonal polynomials
Sodin, S. (2007) · Journal of Mathematical Physics · doi:10.1063/1.2819599 · Cited by 26
Comparative study for inference of hidden classes in stochastic block models
Zhang, P., Krząkała, F., Reichardt, J., & Zdeborová, L. (2012) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/2012/12/p12021 · Cited by 26
Self-citation
Cited by
Machine learning and the physical sciences
Carleo, G., Cirac, I., Cranmer, K., Daudet, L., Schuld, M., Tishby, N., Vogt-Maranto, L., & Zdeborová, L. (2019) · Reviews of Modern Physics · doi:10.1103/revmodphys.91.045002 · Cited by 2,417
Self-citationCommunity detection in networks: a user guide
Fortunato, S., & Hric, D. (2016) · Physics Reports · doi:10.1016/j.physrep.2016.09.002 · Cited by 2,086
Higher-order organization of complex networks
Benson, A. R., Gleich, D. F., & Leskovec, J. (2016) · Science · doi:10.1126/science.aad9029 · Cited by 1,270
Influence maximization in complex networks through optimal percolation
Morone, F., & Makse, H. A. (2015) · Nature · doi:10.1038/nature14604 · Cited by 1,230
Vital nodes identification in complex networks
Lü, L., Chen, D., Ren, X.-L., Zhang, Q.-M., Zhang, Y.-C., & Zhou, T. (2016) · Physics Reports · doi:10.1016/j.physrep.2016.06.007 · Cited by 1,183
Metadata
- Authors
- Krzakala, F., Moore, C., Mossel, E., Neeman, J., Sly, A., Zdeborová, L., & Zhang, P.
- Venue
- Proceedings of the National Academy of Sciences
- Published
- 2013-11-25
- Volume
- 110
- Issue
- 52
- Pages
- 20935-20940
- ISSN
- 0027-8424 (ISSN-L)
- 1091-6490
- OpenAlex
- W2024514015
- Cited by
- 638
- References
- 33
- FWCI
- 33.72
- Type
- journal article
- Language
- en
- Open access
- green
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.