A class of network models recoverable by spectral clustering
This work provides a theoretical extension for community detection methods, which is incremental as it generalizes existing results to a wider class of models.
The authors tackled the problem of community detection in networks by extending the applicability of spectral clustering to a broader class of generative models called Preference Frame Models, showing that the algorithm achieves nearly perfect recovery with high probability under similar guarantees as for simpler models.
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.