标题： 多社区谱聚类用于几何图 显示英文标题

标题： Multi-Community Spectral Clustering for Geometric Graphs

摘要： 在本文中，我们考虑在密集区域内具有固定数量$k \geq 2$的同质社区的软几何块模型（SGBM），并引入了一种用于由此模型生成的图上的社区恢复的谱聚类算法。 给定这样的图，该算法使用与图的邻接矩阵的最接近由模型参数确定的值的$k-1$个特征值相关的特征向量，将图嵌入到$\mathbb{R}^{k-1}$中。 然后对嵌入结果应用$k$-均值聚类。 我们证明了弱一致性，并表明一个简单的局部精修步骤可以确保强一致性。 关键要素是对非标准版本的Davis-Kahan定理的应用，以在特征值不是简单的情况下控制特征空间的扰动。 我们还分析了邻接矩阵的极限谱，使用了组合和矩阵技术的结合。 显示英文摘要

摘要： 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.