Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel

2013-09-16 · NeurIPS 2013 12 · Tai Qin, Karl Rohe

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.

📄 PDF Abstract BibTeX arXiv:1309.4111

Code (0)

등록된 구현이 없습니다.

Tasks

Clustering

Methods 이 논문이 사용한 방법론

Spectral Clustering Spectral clustering has attracted increasing attention due to the promising ability in dealing with nonlinearly separable datasets [15], [16]. In spectral clustering, the…

Consistency of regularized spectral clustering in degree-corrected mixed membership model

2020-11-23 · Huan Qing, Jingli Wang

Community detection in network analysis is an attractive research area recently. Here, under the degree-corrected mixed membership (DCMM) model, we propose an efficient approach called mixed regularized spectral clusteri…

Clustering Community Detection

An improved spectral clustering method for community detection under the degree-corrected stochastic blockmodel

2020-11-12 · Huan Qing, Jingli Wang

For community detection problem, spectral clustering is a widely used method for detecting clusters in networks. In this paper, we propose an improved spectral clustering (ISC) approach under the degree corrected stochas…

Clustering Community Detection Stochastic Block Model

Dual regularized Laplacian spectral clustering methods on community detection

2020-11-09 · Huan Qing, Jingli Wang

Spectral clustering methods are widely used for detecting clusters in networks for community detection, while a small change on the graph Laplacian matrix could bring a dramatic improvement. In this paper, we propose a d…

Clustering Community Detection Stochastic Block Model

Spectral clustering on spherical coordinates under the degree-corrected stochastic blockmodel

2020-11-09 · Francesco Sanna Passino, Nicholas A. Heard, Patrick Rubin-Delanchy

Spectral clustering is a popular method for community detection in network graphs: starting from a matrix representation of the graph, the nodes are clustered on a low dimensional projection obtained from a truncated spe…

Clustering Community Detection Model Selection

Spectral clustering under degree heterogeneity: a case for the random walk Laplacian

2021-05-03 · Alexander Modell, Patrick Rubin-Delanchy

This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. Under a generalised random dot product graph, the embedding p…

Clustering Stochastic Block Model