Multi-Community Spectral Clustering for Geometric Graphs
In this paper, we consider the soft geometric block model (SGBM) with a fixed number $k \geq 2$ of homogeneous communities in the dense regime, and we introduce a spectral clustering algorithm for community recovery on graphs generated by this model. Given such a graph, the algorithm produces an embedding into $\mathbb{R}^{k-1}$ using the eigenvectors associated with the $k-1$ eigenvalues of the adjacency matrix of the graph that are closest to a value determined by the parameters of the model. It then applies $k$-means clustering to the embedding. We prove weak consistency and show that a simple local refinement step ensures strong consistency. A key ingredient is an application of a non-standard version of Davis-Kahan theorem to control eigenspace perturbations when eigenvalues are not simple. We also analyze the limiting spectrum of the adjacency matrix, using a combination of combinatorial and matrix techniques.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Higher-Order Spectral Clustering for Geometric Graphs
The present paper is devoted to clustering geometric graphs. While the standard spectral clustering is often not effective for geometric graphs, we present an effective generalization, which we call higher-order spectral…
ClusteringSpectral clustering on spherical coordinates under the degree-corrected stochastic blockmodel
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…
ClusteringCommunity DetectionModel SelectionRevisiting the Bethe-Hessian: Improved Community Detection in Sparse Heterogeneous Graphs
Spectral clustering is one of the most popular, yet still incompletely understood, methods for community detection on graphs. This article studies spectral clustering based on the Bethe-Hessian matrix $H_r = (r^2-1)I_n +…
ClusteringCommunity DetectionStochastic Block ModelSpectral Clustering for Directed Graphs via Likelihood Estimation on Stochastic Block Models
Graph clustering is a fundamental task in unsupervised learning with broad real-world applications. While spectral clustering methods for undirected graphs are well-established and guided by a minimum cut optimization co…
ClusteringGraph ClusteringStochastic Block ModelSpectral Clustering with Epidemic Diffusion
Spectral clustering is widely used to partition graphs into distinct modules or communities. Existing methods for spectral clustering use the eigenvalues and eigenvectors of the graph Laplacian, an operator that is close…
Clustering