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.
Stochastic block model with k communities: a spectral algorithm with optimal recovery
Todesco, Veronica
2021/2022
Abstract
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.File | Dimensione | Formato | |
---|---|---|---|
tesi_TodescoDef.pdf
accesso aperto
Dimensione
1.89 MB
Formato
Adobe PDF
|
1.89 MB | Adobe PDF | Visualizza/Apri |
The text of this website © Università degli studi di Padova. Full Text are published under a non-exclusive license. Metadata are under a CC0 License
https://hdl.handle.net/20.500.12608/23421