The DOI matches its Crossref record; 24 of the 24 references it cites were found in a registry or an index.
A Consistent Adjacency Spectral Embedding for Stochastic Blockmodel Graphs
Open accessAbstract
We present a method to estimate block membership of nodes in a random graph generated by a stochastic blockmodel. We use an embedding procedure motivated by the random dot product graph model, a particular example of the latent position model. The embedding associates each node with a vector; these vectors are clustered via minimization of a square error criterion. We prove that this method is consistent for assigning nodes to blocks, as only a negligible number of nodes will be misassigned. We prove consistency of the method for directed and undirected graphs. The consistent block assignment makes possible consistent parameter estimation for a stochastic blockmodel. We extend the result in the setting where the number of blocks grows slowly with the number of nodes. Our method is also computationally feasible even for very large graphs. We compare our method with Laplacian spectral clustering through analysis of simulated data and a graph derived from Wikipedia documents.
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
Horn, R. A., & Johnson, C. R. (1985) · Cited by 22,203
Finding and evaluating community structure in networks
Newman, M. E. J., & Girvan, M. (2004) · Physical Review E · doi:10.1103/physreve.69.026113 · Cited by 13,931 · cited 1×
“Bickel and Chen (2009) showed that maximizing the Newman–Girvan modularity (Newman and Girvan 2004) or the likelihood modularity provides consistent estimation of block membership.”
BackgroundFortunato, S. (2010) · Physics Reports · doi:10.1016/j.physrep.2009.11.002 · Cited by 11,293 · cited 1×
“Meth-ods for finding clusters of nodes in graphs are many and varied, with origins in physics, engineering, and statistics; Fortunato (2010) and Fjallstrom (1998) provided comprehensive reviews of clustering techniques.”
BackgroundHorn, R. A., & Johnson, C. R. (1985) · Cambridge University Press eBooks · doi:10.1017/cbo9780511810817 · Cited by 10,280
Hubert, L., & Arabie, P. (1985) · Journal of Classification · doi:10.1007/bf01908075 · Cited by 8,219
The Approximation of One Matrix by Another of Lower Rank
Eckart, C., & Young, G. (1936) · Psychometrika · doi:10.1007/bf02288367 · Cited by 3,800
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
Latent Space Approaches to Social Network Analysis
Hoff, P. D., Raftery, A. E., & Handcock, M. S. (2002) · Journal of the American Statistical Association · doi:10.1198/016214502388618906 · Cited by 1,917
The Rotation of Eigenvectors by a Perturbation. III
Davis, C., & Kahan, W. M. (1970) · SIAM Journal on Numerical Analysis · doi:10.1137/0707001 · Cited by 1,175
Estimation and Prediction for Stochastic Blockstructures
Nowicki, K., & Snijders, T. A. B. (2001) · Journal of the American Statistical Association · doi:10.1198/016214501753208735 · Cited by 1,148
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
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
Model-Based Clustering for Social Networks
Handcock, M. S., Raftery, A. E., & Tantrum, J. M. (2007) · Journal of the Royal Statistical Society Series A: Statistics in Society · doi:10.1111/j.1467-985x.2007.00471.x · Cited by 779
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
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
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
Random Dot Product Graph Models for Social Networks
Young, S. J., & Scheinerman, E. R. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-77004-6_11 · Cited by 238
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
Eigenvalue Inequalities for Matrix Product
Zhang, F., & Zhang, Q. (2006) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2006.880787 · Cited by 100
Fast Neutron Energy Absorption in Gases, Walls, and Tissue
Aebersold, P. C., & Anslow, G. A. (1946) · Physical Review · doi:10.1103/physrev.69.1 · Cited by 37
Reichardt, J., & Bornholdt, S. (2009) · Wiley eBooks · doi:10.1002/9783527628001.ch6 · Cited by 7
Research works printed but not linked: 6
- Airoldi E. M., 2008, The Journal of Machine Learning Research, 9, 1981
- Fjallstrom P., 1998, Computer and Information Science, 3
- Marchette D., 2011, Proceedings of the 57th ISI World Statistics Congress
- Newman M., 2004, Physical Review, 69, 1
- 10.1137/040607605 · doi:10.1137/040607605
- 10.1007/s00180-009-0158-8 · doi:10.1007/s00180-009-0158-8
Cited by
The connectome of an insect brain
Winding, M., Pedigo, B. D., Barnes, C. L., Patsolic, H. G., Park, Y., Kazimiers, T., Fushiki, A., Andrade, I. V., Khandelwal, A., Valdes-Aleman, J., et al. (2023) · Science · doi:10.1126/science.add9330 · Cited by 435
“GMM on an ASE embedding was recently shown to be a consistent way of estimating the membership assignments for a statistical network model called the stochastic block model, motivating this approach (107, 112).”
MethodSelf-citationRandom Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
Lambiotte, R., Delvenne, J.-C., & Barahona, M. (2014) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2015.2391998 · Cited by 398
Representation learning for dynamic graphs: A survey
Kazemi, S. M., Goel, R., Jain, K., Kobyzev, I., Sethi, A., Forsyth, P., & Poupart, P. (2019) · arXiv · doi:10.48550/arxiv.1905.11485 · Cited by 338
“…to solving a generalized eigenvalue decomposition: where L is a graph Laplacian; and the matrix Y can be obtained by considering the Sussman et al. [211] suggested to use a slightly different embedding based on the eigenvalue decomposition of the adjacency matrix A = UΣU (cid:48) (this matrix is…”
MethodConsistency of spectral clustering in stochastic block models
Lei, J., & Rinaldo, A. (2015) · The Annals of Statistics · doi:10.1214/14-aos1274 · Cited by 330
Ahlmann-Eltze, C., Huber, W., & Anders, S. (2025) · Nature Methods · doi:10.1038/s41592-025-02772-6 · Cited by 238
Metadata
- Authors
- Sussman, D. L., Tang, M., Fishkind, D. E., & Priebe, C. E.
- Venue
- Journal of the American Statistical Association
- Publisher
- Informa UK Limited
- Published
- 2012-09
- Volume
- 107
- Issue
- 499
- Pages
- 1119-1128
- ISSN
- 0162-1459 (ISSN-L)
- 1537-274X
- OpenAlex
- W1987349051
- Cited by
- 254
- References
- 24
- FWCI
- 11.19
- 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.