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 blockmodels for graphs with latent block structure
- Estimation and Prediction for Stochastic Blockstructures
- 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
(73)- Estimation and prediction for stochastic blockmodels for graphs with latent block structure
- Network cross-validation for determining the number of communities in network data
- Limit theorems for eigenvectors of the normalized Laplacian for random graphs
- On estimation and inference in latent structure random graphs
- 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
- Extended stochastic block models with application to criminal networks
- Evidential prototype-based clustering based on transfer learning
- Latent structure blockmodels for Bayesian spectral graph clustering
- Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral estimator
- Spectral graph clustering via the expectation-solution algorithm
- Entrywise eigenvector analysis of random matrices with low expected rank
- Bayesian estimation of the latent dimension and communities in stochastic blockmodels
- On Bayesian new edge prediction and anomaly detection in computer networks
- Vertex nomination: the canonical sampling and the extended spectral nomination schemes
- The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics
- Consistency of spectral clustering in stochastic block models
- Role of normalization in spectral clustering for stochastic blockmodels
- Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
- Empirical Bayes estimation for the stochastic blockmodel
- A limit theorem for scaled eigenvectors of random dot product graphs
- Impact of regularization on spectral clustering
- Universally consistent vertex classification for latent positions graphs
- Statistical inference on random dot product graphs: a survey
- A sparse completely positive relaxation of the modularity maximization for community detection
- Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding
- Representation learning for dynamic graphs: a survey
- Vertex nomination via seeded graph matching
- Determining the number of communities in degree-corrected stochastic block models
- scientific article; zbMATH DE number 7626709 (Why is no real title available?)
- scientific article; zbMATH DE number 7625156 (Why is no real title available?)
- Testing for Equivalence of Network Distribution Using Subgraph Counts
- Simultaneous Dimensionality and Complexity Model Selection for Spectral Graph Clustering
- Optimal Bayesian estimation for random dot product graphs
- scientific article; zbMATH DE number 7307464 (Why is no real title available?)
- Inference for multiple heterogeneous networks with a common invariant subspace
- A sharp blockwise tensor perturbation bound for orthogonal iteration
- Adjacency matrix comparison for stochastic block models
- Consistent adjacency-spectral partitioning for the stochastic block model when the model parameters are unknown
- On consistent vertex nomination schemes
- Robust Recommendation via Social Network Enhanced Matrix Completion
- Lead-lag detection and network clustering for multivariate time series with an application to the us equity market
- Efficient Estimation for Random Dot Product Graphs via a One-Step Procedure
- Euclidean Representation of Low-Rank Matrices and Its Geometric Properties
- Entrywise limit theorems for eigenvectors of signal-plus-noise matrix models with weak signals
- Evidential Clustering Based on Transfer Learning
- Valid two-sample graph testing via optimal transport procrustes and multiscale graph correlation with applications in connectomics
- Synergistic graph fusion via encoder embedding
- Nonparametric identification and estimation of stochastic block models from many small networks
- Hypothesis testing for equality of latent positions in random graphs
- Multilayer random dot product graphs: estimation and online change point detection
- Consistent community detection approach in the nonparametric weighted stochastic blockmodel with unspecified number of communities
- Scalable Estimation and Two-Sample Testing for Large Networks via Subsampling
- flexBART: Flexible Bayesian Regression Trees with Categorical Predictors
- Conformal Prediction for Network-Assisted Regression
- Higher-order entrywise eigenvectors analysis of low-rank random matrices: bias correction, Edgeworth expansion and bootstrap
- 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
- Exact recovery discrimination in planted bisection model
- Identifying peer influence in therapeutic communities adjusting for latent homophily
- Euclidean Mirrors and Dynamics in Network Time Series
- Novel network trimming for robust vertex nomination in contaminated networks
- Estimating network-mediated causal effects via principal components network regression
- Bootstrapping networks with latent space structure
- Random line graphs and edge-attributed network inference
- Detecting small clusters in the stochastic block model
- A Bootstrap-based Method for Testing Similarity of Matched Networks
- ACRONYM: Augmented Degree Corrected, Community Reticulated Organized Network Yielding Model
- An omnibus embedding of multiple random graphs and implications for multiscale network inference
- Co-clustering analysis of multi-layer directed networks: a spectral approach
- Large-scale estimation of random graph models with local dependence
- Vertex nomination schemes for membership prediction
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)
