Eigenvalue spectra and stability of directed complex networks

Quantifying the eigenvalue spectra of large random matrices allows one to understand the factors that contribute to the stability of dynamical systems with many interacting components. This work explores the effect that the interaction network between components has on the eigenvalue spectrum. We build on previous results, which usually only take into account the mean degree of the network, by allowing for nontrivial network degree heterogeneity. We derive closed-form expressions for the eigenvalue spectrum of the adjacency matrix of a general weighted and directed network. Using these results, which are valid for any large well-connected complex network, we then derive compact formulas for the corrections (due to nonzero network heterogeneity) to well-known results in random matrix theory. Specifically, we derive modified versions of the Wigner semicircle law, the Girko circle law, and the elliptic law and any outlier eigenvalues. We also derive a surprisingly neat analytical expression for the eigenvalue density of a directed Barabási-Albert network. We are thus able to deduce that network heterogeneity is mostly a destabilizing influence in complex dynamical systems.

Figure 1

Validity of the small-heterogeneity approximation and verification of the precise results for the bulk boundary and outlier position. The results of numerical diagonalization shown as blue crosses. In both panels, the degree distribution of the network is dichotomous $\gamma \left(k\right)=({\delta }_{k,k_1}+{\delta }_{k,k_2})/2$ with $\mu =2, \sigma =1, \mathrm{\Gamma }=0.7, N=10000$, and $p=200$. The naïve elliptical law and outlier [given in Eqs. (12) and (22), respectively] that one would obtain for an Erdős-Renyi graph or a network with vanishing degree heterogeneity is shown as a dashed yellow line with yellow triangle indicating the outlier. The small-degree-heterogeneity approximation and the unapproximated theory predictions [from Eqs. (30) and (10), respectively] are shown as black dot-dashed and red solid lines, respectively. The approximated [see Eq. (32)] and unapproximated [see Eq. (21)] predictions for the outlier eigenvalue are shown as a black square and a red circle respectively. In panel (a) $k_1=145$ and $k_2=255$ giving $s^2=0.075$, and the approximate result is seen to be accurate. In panel (b) $k_1=90$ and $k_2=310$ giving $s^2=0.3$, and the small $s^2$ approximation fails.

Figure 2

Verification of the universal circle and outlier laws for $\mathrm{\Gamma }=0$ given in Eqs. (24) and (25) (solid red lines and circular points, respectively). The prediction in the absence of degree heterogeneity ($s^2=0$) for the bulk region boundary and the corresponding outlier are represented by a dashed orange line and an orange triangle. In both panels, $\mu =1.5, \sigma =1, \mathrm{\Gamma }=0, N=10000, p=200$, and $s^2=0.2$. In panel (a), the dichotomous distribution from Fig. 1 was used but with $k_1=111$ and $k2=289$, whereas in panel (b) the uniform distribution described in Fig. 5 was used (but with $s^2=0.2$).

Figure 3

Verification of the first-order correction to the leading eigenvalue of the bulk region of the eigenvalue spectrum. The prediction for small degree heterogeneity, $[{\lambda }_{\mathrm{edge}}-(1+\mathrm{\Gamma })\sigma ]/\left(s^2\sigma \right)=1/2(1+\mathrm{\Gamma })(1+2\mathrm{\Gamma }-{\mathrm{\Gamma }}^2)$ from Eq. (31) is shown as a dashed line. This is independent of $s^2$. Exact predictions in the cases $s^2=0.05$ and $s^2=0.3$, derived from Eq. (13), are shown as solid lines. The results of numerical diagonalization are shown as markers. The remaining model parameters were $\mu =0, p/N=0.2, N=12000$, and $\sigma =1$, and the degree distribution was uniform, as specified in Fig. 5. As $s^2$ is reduced, we see better agreement with the approximate result.

Figure 4

Leading eigenvalue as a function of $\mu$ for two values of $s^2$. The small $s^2$ approximation for the bulk edge in Eq. (31) and the outlier in Eq. (32) are shown for $s^2=0.05$. Vertical dashed lines show the values of $\mu$ at which the outlier emerges from the bulk region. The solid lines show the unapproximated theory from Eqs. (13) and (21). The black dot-dashed curve shows the prediction that does not take into account network degree heterogeneity, given in Eqs. (12) and (22). The remaining model parameters are $\mathrm{\Gamma }=0.7, p/N=0.2, N=12000$, and $\sigma =1$, and the degree distribution is uniform, as specified in Fig. 5.

Figure 5

Modified eigenvalue density inside the circular bulk region due to nonzero network degree heterogeneity. The degree distribution is uniform: $\gamma \left(k\right)={\sum }_{l=p-\left[\sqrt{3}sp\right]}^{p+\left[\sqrt{3}sp\right]}{\delta }_{k,l}/\left(2\left[\sqrt{3}sp\right]\right)$. Markers are the results of the numerical diagonalization of a single random matrix. Model parameters are $\mu =0, p=200, N=10000, \mathrm{\Gamma }=0$, and $\sigma =1$. The horizontal dot-dashed line shows the uniform value that the eigenvalue density would take without network heterogeneity ($s^2=0$). Solid lines show the theory predictions from Eqs. (26). The dashed curve is the small $s^2$ approximation for $s^2=0.05$ given in Eq. (29). Vertical dashed lines show the position of the edge of the eigenvalue spectrum for each value of $s^2$.

Figure 6

Modified semicircle law due to network degree heterogeneity. The solid red line shows the prediction in Eq. (33), the dot-dashed black line shows the Wigner semicircle law in Eq. (18). The blue crosses are the results of the a single diagonalization of a random matrix with $N=12000, p/N=0.02, \mu =0, \sigma =1, \mathrm{\Gamma }=1$, and $s^2=0.05$ with the degree distribution of the network being uniform as described in the caption of Fig. 5.

Figure 7

The eigenvalue spectrum of a Barabási-Albert network with $\mathrm{\Gamma }=0, \mu =0, \sigma =1, N=12000$, and $p/N=0.02$. Points are the result of diagonalizing a single random matrix. The red line is the prediction in Eq. (37). The dot-dashed line is what one would expect from a network with vanishing degree heterogeneity (i.e., the usual circle law).