A class of network models recoverable by spectral clustering
  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.
