  New phase transition phenomena have recently been discovered for the
stochastic block model, for the special case of two non-overlapping symmetric
communities. This gives raise in particular to new algorithmic challenges
driven by the thresholds. This paper investigates whether a general phenomenon
takes place for multiple communities, without imposing symmetry.
  In the general stochastic block model $\text{SBM}(n,p,Q)$, $n$ vertices are
split into $k$ communities of relative size $\{p_i\}_{i \in [k]}$, and vertices
in community $i$ and $j$ connect independently with probability
$\{Q_{i,j}\}_{i,j \in [k]}$. This paper investigates the partial and exact
recovery of communities in the general SBM (in the constant and logarithmic
degree regimes), and uses the generality of the results to tackle overlapping
communities.
  The contributions of the paper are: (i) an explicit characterization of the
recovery threshold in the general SBM in terms of a new divergence function
$D_+$, which generalizes the Hellinger and Chernoff divergences, and which
provides an operational meaning to a divergence function analog to the
KL-divergence in the channel coding theorem, (ii) the development of an
algorithm that recovers the communities all the way down to the optimal
threshold and runs in quasi-linear time, showing that exact recovery has no
information-theoretic to computational gap for multiple communities, in
contrast to the conjectures made for detection with more than 4 communities;
note that the algorithm is optimal both in terms of achieving the threshold and
in having quasi-linear complexity, (iii) the development of an efficient
algorithm that detects communities in the constant degree regime with an
explicit accuracy bound that can be made arbitrarily close to 1 when a
prescribed signal-to-noise ratio (defined in term of the spectrum of
$\diag(p)Q$) tends to infinity.
