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

Asymptotic distribution theory in statistics (62E20) Classification and discrimination; cluster analysis (statistical aspects) (62H30) 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

(27)

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

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)