Index statistical properties of sparse random graphs

Using the replica method, we develop an analytical approach to compute the characteristic function for the probability ${\mathcal{P}}_N(K,\lambda )$ that a large $N\times N$ adjacency matrix of sparse random graphs has $K$ eigenvalues below a threshold $\lambda$. The method allows to determine, in principle, all moments of ${\mathcal{P}}_N(K,\lambda )$, from which the typical sample-to-sample fluctuations can be fully characterized. For random graph models with localized eigenvectors, we show that the index variance scales linearly with $N\gg 1$ for $\left|\lambda \right|>0$, with a model-dependent prefactor that can be exactly calculated. Explicit results are discussed for Erdös-Rényi and regular random graphs, both exhibiting a prefactor with a nonmonotonic behavior as a function of $\lambda$. These results contrast with rotationally invariant random matrices, where the index variance scales only as $lnN$, with an universal prefactor that is independent of $\lambda$. Numerical diagonalization results confirm the exactness of our approach and, in addition, strongly support the Gaussian nature of the index fluctuations.

Figure 1

Numerical results for the averaged intensive index $m\left(\lambda \right)$ of Erdös-Rényi random graphs with the distribution of edges $P\left(J\right)=\delta (J-1)$, obtained using the population dynamics algorithm (solid lines) with $M={10}^6$ random variables and $\epsilon ={10}^{-3}$. Numerical diagonalization results (symbols), calculated from an ensemble of 100 matrices of size $N=3200$, are shown as a comparison.

Figure 2

Numerical results for the prefactor ${\sigma }^2\left(\lambda \right)$ of the index variance of Erdös-Rényi random graphs with the distribution of edges $P\left(J\right)=\delta (J-1)$, obtained using the population dynamics algorithm with $M={10}^6$ random variables and $\epsilon ={10}^{-3}$.

Figure 3

Numerical diagonalization results for the index variance of Erdös-Rényi random graphs with $c=3$ as a function of the number of nodes $N$. Each data point is calculated from an ensemble with $S$ independent realizations of the adjacency matrix $\mathit{A}$, where $S$ has been chosen according to $S=\frac{3.2\times {10}^5}{N}$. The solid lines represent the best fits of the numerical data. (a) Index variance for $\lambda >0$. The solid lines represent the linear fit $\langle K^2\rangle -{\langle K\rangle }^2=a+bN$, with the values of the slope $b$ indicated next to each straight line. The theoretical values for ${\sigma }^2\left(\lambda \right)$, calculated through the numerical solution of Eq. (36), are given by ${\sigma }^2\left(0.5\right)=0.015,{\sigma }^2\left(3.0\right)=0.0085$ and ${\sigma }^2\left(3.5\right)=0.0040$. (b) Index variance for $\lambda =0$. The solid line represents the logarithmic fit $\langle K^2\rangle -{\langle K\rangle }^2=a+blnN$, with the slope $b=0.47\left(6\right)$.

Figure 4

Numerical results for the averaged intensive index $m\left(\lambda \right)$ and the prefactor ${\sigma }^2\left(\lambda \right)$ of the index variance of random regular graphs with edges drawn from the Gaussian distribution $P\left(J\right)={\left(2\pi \right)}^{-\frac{1}{2}}exp\left(-J^2/2\right)$, obtained using the population dynamics algorithm (solid lines) with $M=5\times {10}^5$ random variables and $\epsilon ={10}^{-3}$. Numerical diagonalization results (symbols), calculated from an ensemble of 100 matrices of size $N=4000$, are shown as a comparison.

Figure 5

Numerical diagonalization results (symbols) for the distribution of the intensive index of random graphs with $c=5$ and $\lambda =1$. The histograms were generated from ${10}^5$ independent samples for the intensive index of the adjacency matrix $\mathit{A}$. The solid lines are Gaussian distributions with mean and variance taken from the data. (a) Erdös-Rényi random graphs with the distribution of the edges $P\left(J\right)=\delta (J-1)$. (b) Regular random graphs with the distribution of the edges $P\left(J\right)={\left(2\pi \right)}^{-\frac{1}{2}}exp\left(-J^2/2\right)$.