A Consistent Adjacency Spectral Embedding for Stochastic Blockmodel Graphs
From MaRDI portal
Abstract: 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 mis-assigned. 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 to Laplacian spectral clustering through analysis of simulated data and a graph derived from Wikipedia documents.
Recommendations
- Consistent adjacency-spectral partitioning for the stochastic block model when the model parameters are unknown
- Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding
- Strong consistency, graph Laplacians, and the stochastic block model
- Consistency of spectral clustering in stochastic block models
- Strong Consistency of Spectral Clustering for Stochastic Block Models
- Estimation and prediction for stochastic blockmodels for graphs with latent block structure
- Adjacency matrix comparison for stochastic block models
- Stochastic Blockmodels for Directed Graphs
- Latent structure blockmodels for Bayesian spectral graph clustering
- Randomized Spectral Clustering in Large-Scale Stochastic Block Models
Cites work
- A nonparametric view of network models and Newman–Girvan and other modularities
- A survey of statistical network models
- Algorithms for graph partitioning on the planted partition model
- Eigenvalue Inequalities for Matrix Product
- Estimation and Prediction for Stochastic Blockstructures
- Estimation and prediction for stochastic blockmodels for graphs with latent block structure
- Latent Space Approaches to Social Network Analysis
- Matrix Analysis
- Modeling graphs using dot product representations
- Random Dot Product Graph Models for Social Networks
- Stochastic blockmodels with a growing number of classes
- The Rotation of Eigenvectors by a Perturbation. III
Cited in
(70)- Lost in the shuffle: testing power in the presence of errorful network vertex labels
- Multiple network embedding for anomaly detection in time series of graphs
- A limit theorem for scaled eigenvectors of random dot product graphs
- Lead-lag detection and network clustering for multivariate time series with an application to the us equity market
- Large-scale estimation of random graph models with local dependence
- Network cross-validation for determining the number of communities in network data
- Universally consistent vertex classification for latent positions graphs
- Exact recovery discrimination in planted bisection model
- Identifying peer influence in therapeutic communities adjusting for latent homophily
- Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding
- Evidential prototype-based clustering based on transfer learning
- Euclidean Mirrors and Dynamics in Network Time Series
- Latent structure blockmodels for Bayesian spectral graph clustering
- Novel network trimming for robust vertex nomination in contaminated networks
- Synergistic graph fusion via encoder embedding
- Estimating network-mediated causal effects via principal components network regression
- Consistency of spectral clustering in stochastic block models
- Consistent adjacency-spectral partitioning for the stochastic block model when the model parameters are unknown
- Representation learning for dynamic graphs: a survey
- Entrywise eigenvector analysis of random matrices with low expected rank
- Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral estimator
- Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
- Bootstrapping networks with latent space structure
- The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics
- Impact of regularization on spectral clustering
- Random line graphs and edge-attributed network inference
- Bayesian estimation of the latent dimension and communities in stochastic blockmodels
- A sparse completely positive relaxation of the modularity maximization for community detection
- Testing for Equivalence of Network Distribution Using Subgraph Counts
- Nonparametric identification and estimation of stochastic block models from many small networks
- Detecting small clusters in the stochastic block model
- Entrywise limit theorems for eigenvectors of signal-plus-noise matrix models with weak signals
- Adjacency matrix comparison for stochastic block models
- A Bootstrap-based Method for Testing Similarity of Matched Networks
- ACRONYM: Augmented Degree Corrected, Community Reticulated Organized Network Yielding Model
- Statistical inference on random dot product graphs: a survey
- Network representation using graph root distributions
- Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees
- On the estimation of latent distances using graph distances
- On estimation and inference in latent structure random graphs
- Multilayer random dot product graphs: estimation and online change point detection
- scientific article; zbMATH DE number 7415122 (Why is no real title available?)
- Hypothesis testing for equality of latent positions in random graphs
- Vertex nomination schemes for membership prediction
- Conformal Prediction for Network-Assisted Regression
- On Bayesian new edge prediction and anomaly detection in computer networks
- Spectral graph clustering via the expectation-solution algorithm
- Empirical Bayes estimation for the stochastic blockmodel
- scientific article; zbMATH DE number 7370586 (Why is no real title available?)
- Consistent community detection approach in the nonparametric weighted stochastic blockmodel with unspecified number of communities
- Role of normalization in spectral clustering for stochastic blockmodels
- Scalable Estimation and Two-Sample Testing for Large Networks via Subsampling
- flexBART: Flexible Bayesian Regression Trees with Categorical Predictors
- scientific article; zbMATH DE number 7626709 (Why is no real title available?)
- scientific article; zbMATH DE number 7625156 (Why is no real title available?)
- Optimal Bayesian estimation for random dot product graphs
- Euclidean Representation of Low-Rank Matrices and Its Geometric Properties
- Limit theorems for eigenvectors of the normalized Laplacian for random graphs
- Vertex nomination via seeded graph matching
- On consistent vertex nomination schemes
- Simultaneous Dimensionality and Complexity Model Selection for Spectral Graph Clustering
- Efficient Estimation for Random Dot Product Graphs via a One-Step Procedure
- Extended stochastic block models with application to criminal networks
- scientific article; zbMATH DE number 7415085 (Why is no real title available?)
- Robust Recommendation via Social Network Enhanced Matrix Completion
- scientific article; zbMATH DE number 7307464 (Why is no real title available?)
- Higher-order entrywise eigenvectors analysis of low-rank random matrices: bias correction, Edgeworth expansion and bootstrap
- Vertex nomination: the canonical sampling and the extended spectral nomination schemes
- Evidential Clustering Based on Transfer Learning
- Valid two-sample graph testing via optimal transport procrustes and multiscale graph correlation with applications in connectomics
This page was built for publication: A Consistent Adjacency Spectral Embedding for Stochastic Blockmodel Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4648556)
