Stochastic block model with k communities: a spectral algorithm with optimal recovery

This thesis discusses a spectral method to solve the Community Detection problem in a Stochastic Block Model (SBM) with k communities. Firstly, we analyze the easier case of a dense graph with k=2 communities and we highlight the fundamental ideas of the spectral method. Then, we study a sparse SBM with k=2 communities: due to the low edge densities, the problem requires a different approach, and we prove the correctness of a spectral method under optimal assumptions. Finally, the main result of this thesis deals with a sparse SBM with k>2 communities: we extend the method developed for k=2 adding several steps and we prove its correctness and the optimality on the assumptions.