Small-World Network Spectra in Mean-Field Theory

Collective dynamics on small-world networks emerge in a broad range of systems with their spectra characterizing fundamental asymptotic features. Here we derive analytic mean-field predictions for the spectra of small-world models that systematically interpolate between regular and random topologies by varying their randomness. These theoretical predictions agree well with the actual spectra (obtained by numerical diagonalization) for undirected and directed networks and from fully regular to strongly random topologies. These results may provide analytical insights to empirically found features of dynamics on small-world networks from various research fields, including biology, physics, engineering, and social science.

Figure 1

Rewiring “on average” (cartoon for $N=16$ and $k=4$). Single realizations of rewiring for (a) undirected and (b) directed networks; (c) mean-field rewiring. From left to right: $q=0$ (regular ring network), $q=0.1$ (“small-world”) and $q=1$ (random network). The regular ring network is the same for (a), (b), and (c).

Figure 2

Accuracy of analytic prediction of second largest eigenvalues as a function of topological randomness. (a) Numerical measurements for undirected ($\times$) and directed (○) networks in comparison with the analytical mean-field predictions [Eq. (9), solid lines] as a function of $q$, for different degrees $k$. (b) Enlargement close to $q=1$ for undirected networks with the analytical predictions ${\lambda }_2^{\mathrm{Wsc}}$ via Wigner’s semicircle law (dashed lines). (c) Enlargement close to $q=1$ for directed networks with the analytical predictions ${\lambda }_2^{\mathrm{RMT}}$ from the theory of asymmetric random matrices (dashed lines). In (a), (b), and (c) error bars on the numerical measurements are smaller than the data points ($N=1000$, each data point averaged over 100 realizations).

Figure 3

Second largest eigenvalues in dependence on edge density and network size. (a) Numerical measurements for undirected ($\times$) and directed (○) networks in comparison with the analytic mean-field prediction (10). Error bars on the numerical measurements are smaller than the data points ($N=2000$, each data point averaged over 100 realizations). (b) Asymptotic ($N\to \infty$) real parts of the second largest eigenvalues ${\lambda }_2$ in dependence on the network size $N$ for fixed edge density $d=k/N=0.1$ [each data point averaged over 100 realizations; $q$ values and symbols as in (a)].

Figure 4

Analytics predicts structure of entire spectrum. Densities of states, Eq. (11), for undirected (a), directed (b), and mean-field (c) networks ($N=1000$, $k=50$). Dashed white lines show the extreme eigenvalues obtained numerically for undirected and directed networks. The solid black lines show the mean-field prediction for the extreme eigenvalues. Densities of states for directed and undirected networks are averaged over 100 realizations for a fixed $q$ value, while the mean-field density is analytically determined by Eq. (8).