论文标题
强一致性，图形拉普拉斯和随机块模型
Strong Consistency, Graph Laplacians, and the Stochastic Block Model
论文作者
论文摘要
光谱聚类已成为数据聚类和社区检测中最受欢迎的算法之一。我们研究经典的两步光谱聚类的性能通过图拉普拉斯式学习，以学习随机块模型。我们的目的是回答以下问题：何时通过图形laplacian能够实现强大的一致性，即，即基本隐藏社区的确切恢复？我们的工作提供了对射射手特征向量的进入分析（$ \ ell _ {\ infty} $ - 标准扰动结合），这两者都是与从定位块模型中采样的邻接矩阵相关的未归一化和归一化的laplacian。我们证明，在与信息理论限制相匹配的条件下，光谱聚类能够准确地恢复种植的社区结构。
Spectral clustering has become one of the most popular algorithms in data clustering and community detection. We study the performance of classical two-step spectral clustering via the graph Laplacian to learn the stochastic block model. Our aim is to answer the following question: when is spectral clustering via the graph Laplacian able to achieve strong consistency, i.e., the exact recovery of the underlying hidden communities? Our work provides an entrywise analysis (an $\ell_{\infty}$-norm perturbation bound) of the Fielder eigenvector of both the unnormalized and the normalized Laplacian associated with the adjacency matrix sampled from the stochastic block model. We prove that spectral clustering is able to achieve exact recovery of the planted community structure under conditions that match the information-theoretic limits.
