Ensemble Averageability in Network Spectra

The extreme eigenvalues of connectivity matrices govern the influence of the network structure on a number of network dynamical processes. A fundamental open question is whether the eigenvalues of large networks are well represented by ensemble averages. Here we investigate this question explicitly and validate the concept of ensemble averageability in random scale-free networks by showing that the ensemble distributions of extreme eigenvalues converge to peaked distributions as the system size increases. We discuss the significance of this result using synchronization and epidemic spreading as example processes.

Figure 1

Numerical results for (a) the distribution $P({\widehat{\lambda }}_N)$ of ${\widehat{\lambda }}_N\equiv {\lambda }_N/(k_N+1)$ and (b) the $N$ dependence of the corresponding standard deviation $\widehat{\sigma }$. All of the numerics are obtained from $5000–{10}^5$ realizations of the networks with $k_0=3$.

Figure 2

Ensemble distributions of (a) ${\lambda }_2$ and (b) ${\mu }_2$. The statistics of ${\mu }_N$ is not shown because it is well approximated by that of $2-{\mu }_2$. The unspecified parameters are defined in Fig. 1.

Figure 3

Numerical results for the ensemble averages (a) $⟨{\lambda }_2⟩$ and (b) $⟨{\mu }_2⟩$ (dotted lines). We also show ${\lambda }^{-}$ and ${\mu }^{-}$ predicted by Eqs. (2, 3), respectively, for the same degree distribution (right-hand side symbols) and for $k$-regular graphs with degree $k_0$ (horizontal solid lines). The symbols and parameters are the same as in Fig. 1.

Figure 4

(a) $⟨f(x)⟩$ vs $f(⟨x⟩)$ for synchronization [$⟨R_{\mu }⟩$ vs $⟨{\mu }_N⟩/⟨{\mu }_2⟩$ (squares), $⟨{\widehat{R}}_{\lambda }⟩$ vs $⟨{\widehat{\lambda }}_N⟩/⟨{\lambda }_2⟩$ (circles)] and epidemics [$⟨1/{\Lambda }_N⟩$ vs $1/⟨{\Lambda }_N⟩$ (diamonds)] for networks with $N=2^8–2^{12}$ and $\gamma =2.4–5.0$. (b)–(d) show the ensemble distributions for $\gamma =3.0$ and $N=2^9–2^{11}$. Here ${\widehat{R}}_{\lambda }\equiv R_{\lambda }/(k_N+1)$. The other parameters are the same as in Fig. 1.