  The stochastic block model (SBM) is a fundamental model for studying graph
clustering or community detection in networks. It has received great attention
in the last decade and the balanced case, i.e., assuming all clusters have
large size, has been well studied. However, our understanding of SBM with
unbalanced communities (arguably, more relevant in practice) is still limited.
In this paper, we provide a simple SVD-based algorithm for recovering the
communities in the SBM with communities of varying sizes. We improve upon a
result of Ailon, Chen and Xu [ICML 2013; JMLR 2015] by removing the assumption
that there is a large interval such that the sizes of clusters do not fall in,
and also remove the dependency of the size of the recoverable clusters on the
number of underlying clusters. We further complement our theoretical
improvements with experimental comparisons. Under the planted clique
conjecture, the size of the clusters that can be recovered by our algorithm is
nearly optimal (up to poly-logarithmic factors) when the probability parameters
are constant.
  As a byproduct, we obtain an efficient clustering algorithm with sublinear
query complexity in a faulty oracle model, which is capable of detecting all
clusters larger than $\tilde{\Omega}({\sqrt{n}})$, even in the presence of
$\Omega(n)$ small clusters in the graph. In contrast, previous efficient
algorithms that use a sublinear number of queries are incapable of recovering
any large clusters if there are more than $\tilde{\Omega}(n^{2/5})$ small
clusters.
