Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel

2013/09/16 by Tai Qin, Karl Rohe, Qin, Tai +1 · 7 citations
Computer Science · Physics and Astronomy · #Advanced Clustering Algorithms Research #Complex Network Analysis Techniques #FOS: Computer and information sciences #FOS: Mathematics #Face and Expression Recognition #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Statistics Theory (math.ST)

paper · pdf · doi:10.48550/arxiv.1309.4111

openalex publication_date 2013/09/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• Fast community detection by SCORE
• A Generalized Solution of the Orthogonal Procrustes Problem
• Convex optimization for the planted k-disjoint-clique problem

Cited by

• Optimal Graph Clustering without Edge Density Signals
• Differentially Private Spectral Graph Clustering: Balancing Privacy, Accuracy, and Efficiency
• Network Signflip Parallel Analysis for Selecting the Embedding Dimension
• Finding Core Balanced Modules in Statistically Validated Stock Networks
• A Bayesian approach to model uncertainty in single-cell genomic data
• Multiple Hypothesis Testing To Estimate The Number Of Communities in Stochastic Block Models
• Impact of regularization on Spectral Clustering

Related

• Impact of regularization on Spectral Clustering
• Fundamental Limits of Spectral Clustering in Stochastic Block Models
• Revisiting Degree-Corrected Spectral Clustering: a Condition-Free Spectral Analysis and Extension
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting
• Randomized Spectral Clustering in Large-Scale Stochastic Block Models