Relating Topological Determinants of Complex Networks to Their Spectral Properties: Structural and Dynamical Effects

The largest eigenvalue of a network’s adjacency matrix and its associated principal eigenvector are key elements for determining the topological structure and the properties of dynamical processes mediated by it. We present a physically grounded expression relating the value of the largest eigenvalue of a given network to the largest eigenvalue of two network subgraphs, considered as isolated: the hub with its immediate neighbors and the densely connected set of nodes with maximum $K$-core index. We validate this formula by showing that it predicts, with good accuracy, the largest eigenvalue of a large set of synthetic and real-world topologies. We also present evidence of the consequences of these findings for broad classes of dynamics taking place on the networks. As a by-product, we reveal that the spectral properties of heterogeneous networks built according to the linear preferential attachment model are qualitatively different from those of their static counterparts.

Popular Summary

In many social and biological systems, the pattern of interactions is described by complex networks—mathematical constructions composed of points (vertices) representing individuals, joined by lines (edges), standing for pairwise interactions between them. These structures are important because they affect the behavior of the dynamical processes they mediate. In the case of epidemic spreading, the global structure of the interaction pattern sets the epidemic threshold, i.e., the minimum value of the probability that an individual transmits the disease to one of her contacts that is sufficient to induce a global disease outbreak. The possibility to make predictions about this threshold based on simple network properties is of paramount importance in epidemiological applications. We provide a physical interpretation of the largest eigenvalue of the adjacency matrix of networks, which allows an estimation of the epidemic threshold and other dynamical processes in many types of real networks.

The value of the epidemic threshold is, in general, related to the largest eigenvalue of the adjacency matrix of the network. Previous works provided an estimate of this eigenvalue for a specific class of networks. Here, we find a much more general expression, which is shown to be accurate for over 100 real-world networked systems. Our result allows us to understand the physical origin of the new expression, pointing out that its value actually depends on the competition between two different types of subnetworks in the larger structure.

This new understanding immediately gives new predictions about the behavior of dynamical processes on networks, as well as providing hints about the effect of intervention strategies, such as immunization of individuals to curb the spreading of a disease.

Figure 1

(a) Largest eigenvalue ${\mathrm{\Lambda }}_M$ as a function of $\max \{\sqrt{q_{\max }},⟨q^2⟩/⟨q⟩\}$ in uncorrelated power-law UCM networks with different degree exponent $\gamma$ and network size $N$. (b) Inverse participation ratio $Y_4(N)$ as a function of $N$ in uncorrelated power-law UCM networks with different degree exponent $\gamma$. Each point in both graphs corresponds to an average over 100 independent network realizations. Error bars are smaller than symbol sizes. Networks have a minimum degree $m=3$.

Figure 2

(a) Largest eigenvalue ${\mathrm{\Lambda }}_M$ as a function of $\max \{\sqrt{q_{\max }},⟨q^2⟩/⟨q⟩\}$ computed for 109 different real-world networks. (b) Largest eigenvalue ${\mathrm{\Lambda }}_M$ as a function of $\max \{\sqrt{q_{\max }},{⟨q⟩}_{K_M}\}$ computed for the same real-world networks. Networks are ordered by increasing network size.

Figure 3

(a) Largest eigenvalue ${\mathrm{\Lambda }}_M$ as a function of $\sqrt{q_{\max }}$ in LPA networks with different degree exponent $\gamma$. (b) Inverse participation ratio $Y_4(N)$ as a function of $N$ in LPA networks with different degree exponent $\gamma$. Each point in both graphs corresponds to an average over 100 independent network realizations. Error bars are smaller than symbol sizes.

Figure 4

(a) Largest eigenvalue ${\mathrm{\Lambda }}_M$ as a function of $\sqrt{q_{\max }}$ in rewired LPA networks with different degree exponent $\gamma$. (b) Inverse participation ratio $Y_4(N)$ as a function of $N$ in rewired LPA networks with different degree exponent $\gamma$. Each point in both graphs corresponds to an average over 100 independent network realizations. Error bars are smaller than symbol sizes.

Figure 5

(a) Numerical estimate of the inverse epidemic threshold $1/{\lambda }_c$ in LPA as a function of $q_{\max }$, for various values of the exponent $\gamma$. We consider networks of sizes from $N={10}^2$ to $N={10}^8$. (b) Numerical estimate of the synchronization threshold ${\kappa }_c$ for $\gamma =2.2$ as a function of $q_{\text{max}}$. System size ranges from $N=300$ to $N=300\hspace{0.17em}000$. In both plots the dependence for $\gamma =2.2$ predicted by the QMF theory is represented by a thick dashed straight line, and the HMF prediction is represented by a dash-dotted line.

Figure 6

(a) Numerical estimate of the inverse epidemic threshold $1/{\lambda }_c$, in a subset of the real-world networks considered, as a function of the inverse largest eigenvalue approximation $\max \{\sqrt{q_{\max }},⟨q^2⟩/⟨q⟩\}$. (b) Numerical estimate of the inverse epidemic threshold $1/{\lambda }_c$ in real-world networks as a function of the inverse improved largest eigenvalue approximation $\max \{\sqrt{q_{\max }},{⟨q⟩}_{K_M}\}$. Data for the networks Zhishi, Web Notre Dame, Road network TX, and Road network PA are lower bounds to the real threshold due to computing-time limitations.

Figure 7

Minimum sizes $N_{\min }$ for the validity of Eq. (1) in uncorrelated power-law networks as a function of the degree exponent $\gamma$. Values in the vicinity of $\gamma =5/2$ not plotted are all larger than $10^{30}$.

Figure 8

For each of the real-world networks considered, we plot in log scale a line indicating the interval where Eq. (1) does not make any prediction. The symbols indicate the actual value of $⟨q^2⟩/[⟨q⟩\sqrt{q_{\max }}]$ for each network.

Figure 9

PEV weight concentrated on various subgraphs for UCM networks of size $N={10}^7$ with different values of $\gamma$.

Figure 10

Scatter plot of $f_i^2$ as a function of the degree $q_i$ in LPA networks of different degree exponent $\gamma$. Network size $N={10}^6$.

Figure 11

Average maximum core index $⟨K_M⟩$ as a function of network size for reshuffled LPA networks with different degree exponent $\gamma$. Error bars are smaller than symbol sizes.

Figure 12

Average maximum core index $⟨K_M⟩$ as a function of network size for reshuffled LPA networks with different degree exponent $\gamma$. Error bars are smaller than symbol sizes.

Figure 13

Average lifespan vs spreading rate ${\lambda }_c$ of SIS epidemics starting from a single infected node (the hub) and reaching the healthy absorbing state before the coverage reaches the threshold value $c=0.5$. Data are for LPA networks with $\gamma =2.6$ and various system size $N$.