论文标题
社区检测到随机几何扰动的鲁棒性
Robustness of Community Detection to Random Geometric Perturbations
论文作者
论文摘要
我们考虑了随机块模型，其中某些潜在（和未观察到的）随机几何图会扰动顶点之间的连接。目的是证明光谱方法对这种类型的噪声是可靠的，即使它们对随机图的存在（或不存在）。我们提供明确的制度，其中邻接矩阵的第二个特征向量与真实的社区向量高度相关（因此，当可能的弱/精确恢复时）。由于对潜在随机图的频谱的详细分析，这是可能的，这是可能的。
We consider the stochastic block model where connection between vertices is perturbed by some latent (and unobserved) random geometric graph. The objective is to prove that spectral methods are robust to this type of noise, even if they are agnostic to the presence (or not) of the random graph. We provide explicit regimes where the second eigenvector of the adjacency matrix is highly correlated to the true community vector (and therefore when weak/exact recovery is possible). This is possible thanks to a detailed analysis of the spectrum of the latent random graph, of its own interest.
