  We analyze the performance of spectral clustering for community extraction in
stochastic block models. We show that, under mild conditions, spectral
clustering applied to the adjacency matrix of the network can consistently
recover hidden communities even when the order of the maximum expected degree
is as small as $\log n$, with $n$ the number of nodes. This result applies to
some popular polynomial time spectral clustering algorithms and is further
extended to degree corrected stochastic block models using a spherical
$k$-median spectral clustering method. A key component of our analysis is a
combinatorial bound on the spectrum of binary random matrices, which is sharper
than the conventional matrix Bernstein inequality and may be of independent
interest.
