View article

In this article, we analyze the asymptotic distribution of the eigenvectors used in spectral clustering of random graphs and in kernel spectral clustering of high dimensional Gaussian random vectors. For dense random graphs drawn from the Stochastic Block Model (SBM), we prove that the isolated dominant eigenvectors of the modularity matrix behave asymptotically like Gaussian random vectors with independent components. As opposed to previous works on SBM eigenvectors, we deal with a more challenging and practically meaningful growth rate of the edge probabilities. Similarly for kernel clustering of a two-class Gaussian mixture we prove the asymptotic Gaussianity of the finite-dimensional marginals of the single isolated eigenvector. We present two practical applications of our results: predicting the classification accuracy of clustering algorithms, and speeding up the convergence of the final Expectation …