Spectral Clustering with the Degree-Corrected Laplacian

Abstract: In network analysis, community detection aims to partition the nodes into meaningful groups based on their connections. To study this problem, random graph models such as the Stochastic Block Model (SBM) and the Degree-Corrected Stochastic Block Model (DCSBM) are widely used. A common approach for estimating communities is spectral clustering, a dimension reduction technique that maps the nodes to a lower-dimensional space while preserving the relevant information. Specifically, the eigenvectors of a particular matrix are used as a representation of each node. These methods are popular due to their simplicity and relative effectiveness. We generalize the matrices commonly used in spectral methods, and introduce the degree-corrected Laplacian, which accounts for the degree heterogeneity introduced by the DCSBM. We prove that the spectral clustering method induced by this matrix is consistent, and show that it enjoys the same asymptotic properties as its classical counterparts. Finally, we propose a spectral clustering algorithm based on the degree-corrected Laplacian and evaluate its performance through simulated and real-world network data.