Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel

Abstract

Spectral clustering is a fast and popular algorithm for finding clusters in networks. Recently, Chaudhuri et al. (2012) and Amini et al.(2012) proposed inspired variations on the algorithm that artificially inflate the node degrees for improved statistical performance. The current paper extends the previous statistical estimation results to the more canonical spectral clustering algorithm in a way that removes any assumption on the minimum degree and provides guidance on the choice of the tuning parameter. Moreover, our results show how the "star shape" in the eigenvectors--a common feature of empirical networks--can be explained by the Degree-Corrected Stochastic Blockmodel and the Extended Planted Partition model, two statistical models that allow for highly heterogeneous degrees. Throughout, the paper characterizes and justifies several of the variations of the spectral clustering algorithm in terms of these models.

References in corpus (2)

• Stochastic blockmodels and community structure in networks
• Fast community detection by SCORE

Cited by in corpus (53)

• Consistency of spectral clustering in stochastic block models
• Covariate-assisted spectral clustering
• Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration
• Role of normalization in spectral clustering for stochastic blockmodels
• Achieving Optimal Misclassification Proportion in Stochastic Block Model
• A Survey on Theoretical Advances of Community Detection in Networks
• Community detection in networks using graph embeddings
• Multilayer Network Science: from Cells to Societies
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting
• A nonparametric two-sample hypothesis testing problem for random dot product graphs
• Demarcating Geographic Regions using Community Detection in Commuting Networks with Significant Self-Loops
• Adapting Stochastic Block Models to Power-Law Degree Distributions
• Detection of Community Structures in Networks with Nodal Features based on Generative Probabilistic Approach
• Determining the Number of Communities in Degree-corrected Stochastic Block Models
• Impact of regularization on Spectral Clustering
• Improvements on SCORE, Especially for Weak Signals
• Network cross-validation by edge sampling
• Community detection by spectral methods in multi-layer networks
• Laplacian Eigenmaps from Sparse, Noisy Similarity Measurements
• A random effects stochastic block model for joint community detection in multiple networks with applications to neuroimaging
• Revisiting the Bethe-Hessian: Improved Community Detection in Sparse Heterogeneous Graphs
• Spectral Algorithms for Community Detection in Directed Networks
• Community Detection in Networks with Node Features
• A unified framework for spectral clustering in sparse graphs
• Pairwise Covariates-adjusted Block Model for Community Detection
• Spectral clustering on spherical coordinates under the degree-corrected stochastic blockmodel
• Detecting and Localizing Anomalous Cliques in Inhomogeneous Networks using Egonets
• Randomized spectral co-clustering for large-scale directed networks
• Detecting Latent Communities in Network Formation Models
• A useful criterion on studying consistent estimation in community detection
• Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing
• Generalized least squares can overcome the critical threshold in respondent-driven sampling
• Spectral clustering via adaptive layer aggregation for multi-layer networks
• Limit theorems for eigenvectors of the normalized Laplacian for random graphs
• Spectral Analysis of High-dimensional Time Series
• Statistical Evaluation of Spectral Methods for Anomaly Detection in Networks
• Adjusted chi-square test for degree-corrected block models
• Directed mixed membership stochastic blockmodel
• Simultaneous Dimensionality and Complexity Model Selection for Spectral Graph Clustering
• Maximum Likelihood Latent Space Embedding of Logistic Random Dot Product Graphs
• Discovering Political Topics in Facebook Discussion threads with Graph Contextualization
• BATS: A Spectral Biclustering Approach to Single Document Topic Modeling and Segmentation
• Incrementally Updated Spectral Embeddings
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian
• A generalized Lieb's theorem and its applications to spectrum estimates for a sum of random matrices
• Latent structure blockmodels for Bayesian spectral graph clustering
• A Time-Varying Network for Cryptocurrencies
• Entrywise convergence of iterative methods for eigenproblems
• Unified Statistical Theory of Spectral Graph Analysis
• Measuring the Robustness of Graph Properties
• Multi-view Banded Spectral Clustering with Application to ICD9 Clustering
• Estimating Mixed-Memberships Using the Symmetric Laplacian Inverse Matrix
• Consistent Spectral Clustering of Network Block Models under Local Differential Privacy