High-dimensional random objects and the Stochastic Block Model

The aim of this thesis is to present an accessible approach to the community detection problem in random graphs, under the data-generating assumptions of the Stochastic Block Model (SBM). After introducing the space of subgaussian random variables and proving Hoeffding’s inequality, we establish a high-probability bound for random matrices with subgaussian entries (Chapter 1), and provide an interpretation of Davis–Kahan theory in the context of perturbation theory (Chapter 2). The assumptions of the SBM and the mathematical formalism underlying the spectral clustering oriented community detection algorithm are presented in Chapter 3.