Local law and Tracy--Widom limit for sparse stochastic block models

Abstract

We consider the spectral properties of sparse stochastic block models, where $N$ vertices are partitioned into $K$ balanced communities. Under an assumption that the intra-community probability and inter-community probability are of similar order, we prove a local semicircle law up to the spectral edges, with an explicit formula on the deterministic shift of the spectral edge. We also prove that the fluctuation of the extremal eigenvalues is given by the GOE Tracy--Widom law after rescaling and centering the entries of sparse stochastic block models. Applying the result to sparse stochastic block models, we rigorously prove that there is a large gap between the outliers and the spectral edge without centering.

arXiv comment68 pages. 2 Figures

References in corpus (10)

• Community structure in social and biological networks
• The structure of scientific collaboration networks
• Functional cartography of complex metabolic networks
• Social Structure of Facebook Networks
• Spectral redemption: clustering sparse networks
• Central limit theorem for linear eigenvalue statistics of random matrices with independent entries
• Spectral Statistics of Erd{\H o}s-Rényi Graphs II: Eigenvalue Spacing and the Extreme Eigenvalues
• Edge Universality of Beta Ensembles
• Ferromagnetic to paramagnetic transition in spherical spin glass
• Transition from Tracy-Widom to Gaussian fluctuations of extremal eigenvalues of sparse Erdős-Rényi graphs