  Community detection in the stochastic block model is one of the central
problems of graph clustering. Since its introduction, many subsequent papers
have made great strides in solving and understanding this model. In this setup,
spectral algorithms have been one of the most widely used frameworks. However,
despite the long history of study, there are still unsolved challenges. One of
the main open problems is the design and analysis of "simple"(vanilla) spectral
algorithms, especially when the number of communities is large.
  In this paper, we provide two algorithms. The first one is based on the
power-iteration method. It is a simple algorithm which only compares the rows
of the powered adjacency matrix. Our algorithm performs optimally (up to
logarithmic factors) compared to the best known bounds in the dense graph
regime by Van Vu (Combinatorics Probability and Computing, 2018). Furthermore,
our algorithm is also robust to the "small cluster barrier", recovering large
clusters in the presence of an arbitrary number of small clusters. Then based
on a connection between the powered adjacency matrix and eigenvectors, we
provide a vanilla spectral algorithm for large number of communities in the
balanced case. This answers an open question by Van Vu (Combinatorics
Probability and Computing, 2018) in the balanced case. Our methods also
partially solve technical barriers discussed by Abbe, Fan, Wang and Zhong
(Annals of Statistics, 2020).
  In the technical side, we introduce a random partition method to analyze each
entry of a powered random matrix. This method can be viewed as an eigenvector
version of Wigner's trace method. Recall that Wigner's trace method links the
trace of powered matrix to eigenvalues. Our method links the whole powered
matrix to the span of eigenvectors. We expect our method to have more
applications in random matrix theory.
