A0356
Title: Fundamental limits of spectral clustering in stochastic block models
Authors: Anderson Ye Zhang - University of Pennsylvania (United States) [presenting]
Abstract: A precise characterization of the performance of spectral clustering is given for community detection under Stochastic Block Models by carrying out sharp statistical analysis. Spectral clustering has an exponentially small error with matching upper and lower bounds with the same exponent, including the sharp leading constant. The fundamental limits established for the spectral clustering hold for networks with multiple and imbalanced communities and sparse networks with degrees far smaller than $\log n$. The key to the results is a novel truncated $\ell_2$ perturbation analysis for eigenvectors and a new analysis idea of eigenvectors truncation.
