Finite-size corrections to the spectrum of regular random graphs: An analytical solution

We develop a thorough analytical study of the $O(1/N)$ correction to the spectrum of regular random graphs with $N\to \infty$ nodes. The finite-size fluctuations of the resolvent are given in terms of a weighted series over the contributions coming from loops of all possible lengths, from which we obtain the isolated eigenvalue as well as an analytical expression for the $O(1/N)$ correction to the continuous part of the spectrum. The comparison between this analytical formula and direct diagonalization results exhibits an excellent agreement, confirming the correctness of our expression.

Figure 1

The $O(1/N)$ correction to the average eigenvalue distribution of the adjacency matrix of an ensemble of regular random graphs with degree $c$, where the isolated eigenvalue $\lambda =c$ has been omitted. In the main graph, the solid black curves depict the analytical result of Eq. (60) for different $c$, while the symbols represent numerical diagonalization results obtained from matrices of size $N=500$. In the inset, the solid black line shows the analytical expression for $c\gg 1$, given by Eq. (62), and the red symbols are direct diagonalization results for $c=40$ and $N=500$. The histograms from numerical diagonalizations are obtained by averaging the results over $5\times {10}^6$ samples.