2025/07/27 by Luiz Emílio Allem, Konstantin Avrachenkov, Allem, Luiz Emilio +7
Physics and Astronomy · Mathematics · #Complex Network Analysis Techniques #Opinion Dynamics and Social Influence #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.2508.00893
In this paper, we consider the soft geometric block model (SGBM) with a fixed number k ≥ 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 ℝ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.