A class of network models recoverable by spectral clustering

Abstract

Finding communities in networks is a problem that remains difficult, in spite of the amount of attention it has recently received. The Stochastic Block-Model (SBM) is a generative model for graphs with "communities" for which, because of its simplicity, the theoretical understanding has advanced fast in recent years. In particular, there have been various results showing that simple versions of spectral clustering using the Normalized Laplacian of the graph can recover the communities almost perfectly with high probability. Here we show that essentially the same algorithm used for the SBM and for its extension called Degree-Corrected SBM, works on a wider class of Block-Models, which we call Preference Frame Models, with essentially the same guarantees. Moreover, the parametrization we introduce clearly exhibits the free parameters needed to specify this class of models, and results in bounds that expose with more clarity the parameters that control the recovery error in this model class.

arXiv comment15 pages

References in corpus (2)

• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Equitable random graphs

Cited by in corpus (6)

• Spectral gap in random bipartite biregular graphs and applications
• Spectra of random regular hypergraphs
• Extreme singular values of inhomogeneous sparse random rectangular matrices
• The decomposition of the higher-order homology embedding constructed from the $k$-Laplacian
• Distribution free optimality intervals for clustering
• Measuring the Robustness of Graph Properties