# Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel

arXiv: https://arxiv.org/abs/1309.4111 · HTML: https://mlsanity.com/paper/1309.4111/

## Key facts

- Cited by 45 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Sep 2013.

## Built on by (most cited first, 30 of 45)

- [Learning Parametrised Graph Shift Operators](https://mlsanity.com/paper/2101.10050/) (2021)
- [Leave-one-out Singular Subspace Perturbation Analysis for Spectral Clustering](https://mlsanity.com/paper/2205.14855/) (2022)
- [Community detection for weighted bipartite networks](https://mlsanity.com/paper/2109.10319/) (2021)
- [Spectral clustering under degree heterogeneity: a case for the random walk Laplacian](https://mlsanity.com/paper/2105.00987/) (2021)
- [Estimating Graph Dimension with Cross-validated Eigenvalues](https://mlsanity.com/paper/2108.03336/) (2021)
- [The Multivariate Community Hawkes Model for Dependent Relational Events in Continuous-time Networks](https://mlsanity.com/paper/2205.00639/) (2022)
- [A Spectral Analysis of Graph Neural Networks on Dense and Sparse Graphs](https://mlsanity.com/paper/2211.03231/) (2022)
- [Intensity Profile Projection: A Framework for Continuous-Time Representation Learning for Dynamic Networks](https://mlsanity.com/paper/2306.06155/) (2023)
- [Efficiently matching random inhomogeneous graphs via degree profiles](https://mlsanity.com/paper/2310.10441/) (2023)
- [A Simple and Powerful Framework for Stable Dynamic Network Embedding](https://mlsanity.com/paper/2311.09251/) (2023)
- [A Compressed Sensing Based Least Squares Approach to Semi-supervised Local Cluster Extraction](https://mlsanity.com/paper/2202.02904/) (2022)
- [Bipartite mixed membership distribution-free model. A novel model for community detection in overlapping bipartite weighted networks](https://mlsanity.com/paper/2211.00912/) (2022)
- [Differentially private exact recovery for stochastic block models](https://mlsanity.com/paper/2406.02644/) (2024)
- [Informative core identification in complex networks](https://mlsanity.com/paper/2101.06388/) (2021)
- [A useful criterion on studying consistent estimation in community detection](https://mlsanity.com/paper/2109.14950/) (2021)
- [Community detection by spectral methods in multi-layer networks](https://mlsanity.com/paper/2403.12540/) (2024)
- [Directed mixed membership stochastic blockmodel](https://mlsanity.com/paper/2101.02307/) (2021)
- [Semi-Supervised Clustering with Inaccurate Pairwise Annotations](https://mlsanity.com/paper/2104.02146/) (2021)
- [A class of network models recoverable by spectral clustering](https://mlsanity.com/paper/2104.10347/) (2021)
- [Directed degree corrected mixed membership model and estimating community memberships in directed networks](https://mlsanity.com/paper/2109.07826/) (2021)
- [Distribution-Free Model for Community Detection](https://mlsanity.com/paper/2111.07495/) (2021)
- [Efficient Identity and Position Graph Embedding via Spectral-Based Random Feature Aggregation](https://mlsanity.com/paper/2505.20992/) (2025)
- [Inference for Network Regression Models with Community Structure](https://mlsanity.com/paper/2106.04271/) (2021)
- [Ergodic Limits, Relaxations, and Geometric Properties of Random Walk Node Embeddings](https://mlsanity.com/paper/2109.04526/) (2021)
- [Consistency between ordering and clustering methods for graphs](https://mlsanity.com/paper/2208.12933/) (2022)
- [Of Spiky SVDs and Music Recommendation](https://mlsanity.com/paper/2307.01212/) (2023)
- [Latent class analysis by regularized spectral clustering](https://mlsanity.com/paper/2310.18727/) (2023)
- [Matrix Factorization Framework for Community Detection under the Degree-Corrected Block Model](https://mlsanity.com/paper/2601.06262/) (2026)
- [Latent structure blockmodels for Bayesian spectral graph clustering](https://mlsanity.com/paper/2107.01734/) (2021)
- [Distribution free optimality intervals for clustering](https://mlsanity.com/paper/2107.14442/) (2021)

## Abstract (arXiv)

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.