Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel

By Tai Qin, Karl Rohe. Neural Information Processing Systems, 2013

327 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/dfd14f153f93f290a5fcc3230bbab08a42bc47e0

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Statistical and Nonlinear Physics

Citations in the corpus

Limit theorems for eigenvectors of the normalized Laplacian for random graphs (2016, background): “For previous consistency results of X̆ as an estimator for X̃ in various random graphs models, the reader is referred to [34, 35, 43] among others.”
Consistency of spectral clustering in stochastic block models (2013, background): “In several recent works, Chaudhuri et al. (2012); Qin & Rohe (2013) studied graph Laplacian based spectral clustering with regularization, where a small constant is added to all node degrees prior to the normalization.”