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

Abstract

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 spectral decomposition of the matrix. Estimating correctly the number of communities and the dimension of the reduced latent space is critical for good performance of spectral clustering algorithms. Furthermore, many real-world graphs, such as enterprise computer networks studied in cyber-security applications, often display heterogeneous within-community degree distributions. Such heterogeneous degree distributions are usually not well captured by standard spectral clustering algorithms. In this article, a novel spectral clustering algorithm is proposed for community detection under the degree-corrected stochastic blockmodel. The proposed method is based on a transformation of the spectral embedding to spherical coordinates, and a novel modelling assumption in the transformed space. The method allows for simultaneous and automated selection of the number of communities and the latent dimension for spectral embeddings of graphs with uneven node degrees. Results show improved performance over competing methods in representing computer networks.

References in corpus (12)

• Fast unfolding of communities in large networks
• Stochastic blockmodels and community structure in networks
• Hyperbolic Geometry of Complex Networks
• Consistency of spectral clustering in stochastic block models
• Fast community detection by SCORE
• Consistency of community detection in networks under degree-corrected stochastic block models
• Pseudo-likelihood methods for community detection in large sparse networks
• Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel
• Scalable Inference of Customer Similarities from Interactions Data using Dirichlet Processes
• Bayesian estimation of the latent dimension and communities in stochastic blockmodels
• The multilayer random dot product graph
• A statistical interpretation of spectral embedding: the generalised random dot product graph

Cited by in corpus (3)

• Latent structure blockmodels for Bayesian spectral graph clustering
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian
• Matrix factorisation and the interpretation of geodesic distance