Consistent adjacency-spectral partitioning for the stochastic block model when the model parameters are unknown
From MaRDI portal
Publication:5300544
Asymptotic properties of parametric estimators (62F12) Random graphs (graph-theoretic aspects) (05C80) Eigenvalues, singular values, and eigenvectors (15A18) Robustness and adaptive procedures (parametric inference) (62F35) Combinatorial aspects of block designs (05B05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Abstract: For random graphs distributed according to a stochastic block model, we consider the inferential task of partioning vertices into blocks using spectral techniques. Spectral partioning using the normalized Laplacian and the adjacency matrix have both been shown to be consistent as the number of vertices tend to infinity. Importantly, both procedures require that the number of blocks and the rank of the communication probability matrix are known, even as the rest of the parameters may be unknown. In this article, we prove that the (suitably modified) adjacency-spectral partitioning procedure, requiring only an upper bound on the rank of the communication probability matrix, is consistent. Indeed, this result demonstrates a robustness to model mis-specification; an overestimate of the rank may impose a moderate performance penalty, but the procedure is still consistent. Furthermore, we extend this procedure to the setting where adjacencies may have multiple modalities and we allow for either directed or undirected graphs.
Recommendations
- A Consistent Adjacency Spectral Embedding for Stochastic Blockmodel Graphs
- Consistency of spectral clustering in stochastic block models
- Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding
- Spectral clustering and the high-dimensional stochastic blockmodel
- Graph partitioning via adaptive spectral techniques
Cited in
(42)- Consistent nonparametric estimation for heavy-tailed sparse graphs
- A limit theorem for scaled eigenvectors of random dot product graphs
- Network cross-validation for determining the number of communities in network data
- Universally consistent vertex classification for latent positions graphs
- On the limiting spectral distributions of stochastic block models
- Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding
- Optimal bipartite network clustering
- Corrected Bayesian information criterion for stochastic block models
- Co-clustering separately exchangeable network data
- A survey on theoretical advances of community detection in networks
- Review on statistical methods for gene network reconstruction using expression data
- Consistency of spectral clustering in stochastic block models
- Smoothing graphons for modelling exchangeable relational data
- 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
- The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics
- Impact of regularization on spectral clustering
- The expected adjacency and modularity matrices in the degree corrected stochastic block model
- Recent advances on mechanisms of network generation: community, exchangeability, and scale-free properties
- scientific article; zbMATH DE number 7370527 (Why is no real title available?)
- Profile likelihood biclustering
- Adjacency matrix comparison for stochastic block models
- Statistical inference on random dot product graphs: a survey
- Estimating parameters of a probabilistic heterogeneous block model via the EM algorithm
- On the efficacy of higher-order spectral clustering under weighted stochastic block models
- Limiting spectral distribution of stochastic block model
- Spectral co-clustering in multi-layer directed networks
- Vertex nomination schemes for membership prediction
- Optimality of spectral clustering in the Gaussian mixture model
- Spectral graph clustering via the expectation-solution algorithm
- Randomized Spectral Clustering in Large-Scale Stochastic Block Models
- Multi-level spectral graph partitioning method
- Empirical Bayes estimation for the stochastic blockmodel
- Rate optimal Chernoff bound and application to community detection in the stochastic block models
- scientific article; zbMATH DE number 7625156 (Why is no real title available?)
- A Consistent Adjacency Spectral Embedding for Stochastic Blockmodel Graphs
- Fast community detection by SCORE
- A goodness-of-fit test for stochastic block models
- Vertex nomination: the canonical sampling and the extended spectral nomination schemes
- Maximum Likelihood Estimation and Graph Matching in Errorfully Observed Networks
- Analysis of spectral clustering algorithms for community detection: the general bipartite setting
- Consistency of spectral hypergraph partitioning under planted partition model
This page was built for publication: Consistent adjacency-spectral partitioning for the stochastic block model when the model parameters are unknown
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5300544)
