Title: Strong Consistency of Spectral Clustering for Stochastic Block Models,
Abstract: In this paper we prove the strong consistency of several methods based on the
spectral clustering techniques that are widely used to study the community
detection problem in stochastic block models (SBMs). We show that under some
weak conditions on the minimal degree, the number of communities, and the
eigenvalues of the probability block matrix, the K-means algorithm applied to
the eigenvectors of the graph Laplacian associated with its first few largest
eigenvalues can classify all individuals into the true community uniformly
correctly almost surely. Extensions to both regularized spectral clustering and
degree-corrected SBMs are also considered. We illustrate the performance of
different methods on simulated networks.