Strong Consistency of Spectral Clustering for Stochastic Block Models

DOI10.1109/TIT.2019.2934157MaRDI QIDQ5211603zbMATH OpenOpenAlexWikidataFDO

Authors Liangjun Su, Wuyi Wang, Yichong Zhang

Publication date 28 January 2020

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Asymptotic distribution theory in statistics (62E20) Detection theory in information and communication theory (94A13)

Abstract: In this paper we prove the strong consistency of several methods based on the spectral clustering techniques that are widely used to study the community detection problem in stochastic block models (SBMs). We show that under some weak conditions on the minimal degree, the number of communities, and the eigenvalues of the probability block matrix, the K-means algorithm applied to the eigenvectors of the graph Laplacian associated with its first few largest eigenvalues can classify all individuals into the true community uniformly correctly almost surely. Extensions to both regularized spectral clustering and degree-corrected SBMs are also considered. We illustrate the performance of different methods on simulated networks.

Cited in

(26)

• Fast Network Community Detection With Profile-Pseudo Likelihood Methods
• Exact recovery discrimination in planted bisection model
• Consistency of spectral clustering in stochastic block models
• Estimating mixed-memberships using the symmetric Laplacian inverse matrix
• Network-adjusted covariates for community detection
• Strong consistency guarantees for clustering high-dimensional bipartite graphs with the spectral method
• Detecting small clusters in the stochastic block model
• Consistent Estimation of the Number of Communities via Regularized Network Embedding
• A performance guarantee for spectral clustering
• Nonparametric two-sample hypothesis testing for low-rank random graphs of differing sizes
• Strong consistency, graph Laplacians, and the stochastic block model
• Panel data models with time-varying latent group structures
• Aggregate spectral clustering for community detection in multi-layer popularity adjusted block model
• Joint Spectral Clustering in Multilayer Degree-Corrected Stochastic Blockmodels
• Randomized Spectral Clustering in Large-Scale Stochastic Block Models
• scientific article; zbMATH DE number 7370586 (Why is no real title available?)
• Spectral clustering and the high-dimensional stochastic blockmodel
• Consistent community detection approach in the nonparametric weighted stochastic blockmodel with unspecified number of communities
• A Consistent Adjacency Spectral Embedding for Stochastic Blockmodel Graphs
• Perfect spectral clustering with discrete covariates
• Improvements on SCORE, especially for weak signals
• Understanding asymptotic consistency and its unique advantages in large sample statistical inference
• Bias-Adjusted Spectral Clustering in Multi-Layer Stochastic Block Models
• Limit results for estimation of connectivity matrix in multi-layer stochastic block models
• A PANEL CLUSTERING APPROACH TO ANALYZING BUBBLE BEHAVIOR
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting

This page was built for publication: Strong Consistency of Spectral Clustering for Stochastic Block Models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5211603)