Consistent adjacency-spectral partitioning for the stochastic block model when the model parameters are unknown

DOI10.1137/120875600zbMATH Open1314.05186arXiv1205.0309OpenAlexW2964179623MaRDI QIDQ5300544FDOQ5300544

Joshua T. Vogelstein, Minh Tang, Donniell E. Fishkind, Carey E. Priebe, Daniel L. Sussman

Publication date: 27 June 2013

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1205.0309

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

zbMATH Keywords

stochastic block modeladjacency matrixspectral partition

Mathematics Subject Classification ID

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)

Cited In (37)

• Consistent nonparametric estimation for heavy-tailed sparse graphs
• A limit theorem for scaled eigenvectors of random dot product graphs
• Universally consistent vertex classification for latent positions graphs
• A survey on theoretical advances of community detection in networks
• Co-clustering separately exchangeable network data
• 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
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral estimator
• The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics
• Recent advances on mechanisms of network generation: community, exchangeability, and scale-free properties
• Impact of regularization on spectral clustering
• Title not available (Why is that?)
• Profile likelihood biclustering
• Adjacency matrix comparison for stochastic block models
• Statistical inference on random dot product graphs: a survey
• On the efficacy of higher-order spectral clustering under weighted stochastic block models
• Spectral co-clustering in multi-layer directed networks
• Estimating parameters of a probabilistic heterogeneous block model via the EM algorithm
• Optimality of spectral clustering in the Gaussian mixture model
• Vertex nomination schemes for membership prediction
• Spectral graph clustering via the expectation-solution algorithm
• Optimal Bipartite Network Clustering
• Randomized Spectral Clustering in Large-Scale Stochastic Block Models
• Multi-level spectral graph partitioning method
• Corrected Bayesian Information Criterion for Stochastic Block Models
• Rate optimal Chernoff bound and application to community detection in the stochastic block models
• Network Cross-Validation for Determining the Number of Communities in Network Data
• Empirical Bayes estimation for the stochastic blockmodel
• Title not available (Why is that?)
• 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

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)