Spectral clustering on spherical coordinates under the degree-corrected
stochastic blockmodel
stochastic blockmodel
File(s)2011.04558v2.pdf (943.49 KB)
Working paper
Author(s)
Sanna Passino, Francesco
Heard, Nicholas A
Rubin-Delanchy, Patrick
Type
Journal Article
Abstract
Spectral clustering is a popular method for community detection in networks
under the assumption of the standard stochastic blockmodel. Taking a matrix representation of the graph such as the adjacency matrix, the nodes are clustered on a low dimensional projection obtained from a truncated spectral decomposition of the matrix. Estimating the number of communities and the dimension of the reduced latent space well is crucial for good performance of spectral clustering algorithms. Real-world networks, such as computer networks studied in cyber-security applications, often present heterogeneous within-community degree distributions which are better addressed by the degree-corrected stochastic blockmodel. A novel, model-based method is proposed in this article for simultaneous and automated selection of the number of communities and latent dimension for spectral clustering under the degree-corrected stochastic blockmodel. The method is based on a transformation to spherical coordinates of the spectral embedding, and on a novel modelling assumption in the transformed space, which is then embedded into an existing model selection framework for estimating the number of communities and the latent dimension. Results show improved performance over competing methods on simulated and real-world computer network data.
under the assumption of the standard stochastic blockmodel. Taking a matrix representation of the graph such as the adjacency matrix, the nodes are clustered on a low dimensional projection obtained from a truncated spectral decomposition of the matrix. Estimating the number of communities and the dimension of the reduced latent space well is crucial for good performance of spectral clustering algorithms. Real-world networks, such as computer networks studied in cyber-security applications, often present heterogeneous within-community degree distributions which are better addressed by the degree-corrected stochastic blockmodel. A novel, model-based method is proposed in this article for simultaneous and automated selection of the number of communities and latent dimension for spectral clustering under the degree-corrected stochastic blockmodel. The method is based on a transformation to spherical coordinates of the spectral embedding, and on a novel modelling assumption in the transformed space, which is then embedded into an existing model selection framework for estimating the number of communities and the latent dimension. Results show improved performance over competing methods on simulated and real-world computer network data.
Date Issued
2022
Date Acceptance
2021-10-30
Citation
Technometrics, 2022, 64 (3), pp.346-357
ISSN
0040-1706
Publisher
American Statistical Association
Start Page
346
End Page
357
Journal / Book Title
Technometrics
Volume
64
Issue
3
Copyright Statement
© 2021 The Author(s)
Identifier
http://arxiv.org/abs/2011.04558v1
Subjects
cs.LG
stat.ML
stat.ML
Publication Status
Accepted
Date Publish Online
2022-01-10