Eigenvalues of Stochastic Blockmodel Graphs and Random Graphs with Low-Rank Edge Probability Matrices

We derive the limiting distribution for the outlier eigenvalues of the adjacency matrix for random graphs with independent edges whose edge probability matrices have low-rank structure. We show that when the number of vertices tends to infinity, the leading eigenvalues in magnitude are jointly multivariate Gaussian with bounded covariances. As a special case, this implies a limiting normal distribution for the outlier eigenvalues of stochastic blockmodel graphs and their degree-corrected or mixed-membership variants. Our result extends the classical result of Furedi and Komlos on the fluctuation of the largest eigenvalue for Erdős–Renyi graphs.