Universality in network dynamics

Abstract

Despite significant advances in characterizing the structural properties of complex networks, a mathematical framework that uncovers the universal properties of the interplay between the topology and the dynamics of complex systems continues to elude us. Here we develop a self-consistent theory of dynamical perturbations in complex systems, allowing us to systematically separate the contribution of the network topology and dynamics. The formalism covers a broad range of steady-state dynamical processes and offers testable predictions regarding the system's response to perturbations and the development of correlations. It predicts several distinct universality classes whose characteristics can be derived directly from the continuum equation governing the system's dynamics and which are validated on several canonical network-based dynamical systems, from biochemical dynamics to epidemic spreading. Finally, we collect experimental data pertaining to social and biological systems, demonstrating that we can accurately uncover their universality class even in the absence of an appropriate continuum theory that governs the system's dynamics.

Fig. 1. The observed dynamical behavior of model systems

We used the response of a system to external perturbations to determine the five functions that capture the local dynamics between neighbors, the propagation of perturbations to more distant nodes and the global cascades, using numerical simulations. (a1) - (a4) For all four models we find that P(G) ∼ G^−ν, independent of the network topology (Erdős-Rényi, scale-free or empirical). For and ν = 2 and for and ε ν = 3/2, in perfect agreement with the prediction of (15) and (16) (solid red lines). (b1) - (c4) The impact and stability distributions, P(I) and P(S), show diverse behavior: for and both P(I) and P(S) are bounded independently of P(k), for P(I) is fat-tailed on a scale-free network while P(S) is bounded, and for both are fat-tailed. For scale-free networks (P(k) ∼ k^−γ) we can predict P(S) and P(I) using P(K = k^y) ∼ K^−Y, where Y = (γ + y − 1)/y (solid red lines, Sec. S.VII.E), in agreement with simulations. (d1) - (d4) The propagation of perturbations is captured by the correlation function Γ(l) (5): and exhibit conservative propagation, as perturbations penetrate the network without loss; and exhibit dissipative propagation, as perturbations decay exponentially with l. The theoretical prediction (14) (solid red lines) is in agreement with the numerical results. For l > 〈l〉 the effect of the perturbation drops sharply, as the propagation has exhausted most nodes in the network (gray circles), and Eq. (14) is no longer valid (see Sec. S.IV where we analytically predict the behavior of Γ(l) for l > 〈l〉). (e1) - (e4) The global impact of a perturbation is captured by the cascade size. While in three of the models ( , , and ε P(C) is driven by P(k), being consequently fat-tailed or bounded, has a bounded P(C) independently of the network topology. The results are consistent with the theoretical prediction of (17) and (18). The theoretical prediction for scale-free networks (solid red lines) is in agreement with the numerical results.

Fig. 2. Local dynamics: Stability and Impact

The stability S_i, characterizing a node's response to perturbations in its vicinity, features two dynamical universality classes. (a) Uniform stability: if δ = 0 in (10), the stability is independent of the node's degree and P(S) is bounded, regardless of the form of P(k). As predicted, (a1), (a2) and (a3) belong to this class, featuring $S_i\sim k_i^0$. Hence regardless of whether the underlying network is random (ER), scale-free (SF) or an empirical network (yeast protein-protein interaction (PPI) network [52]; yeast transcriptional regulatory network (TRN) [53]; see Sec S.VII) P(S) will be bounded (Fig. 1c1 - c3). (b) Heterogeneous stability: if δ > 0 in (10), S_i depends on k_i and P(S) is driven by P(k), being fat-tailed if P(k) is fat-tailed. For (b1) we predict δ = 1 (solid green line), in agreement with results obtained for both model and empirical networks (Email [48]), indicating that P(S) ∼ P(k) (Fig. 1c4). Where appropriate, here and in what follows, we used logarithmic binning to display the scaling of S_i [54]. Impact, I_i, characterizes the influence of i on its immediate neighbors. (c) Uniform impact, observed for φ = 0 in (11), leads to a bounded P(I). (c1) and (c2) belong to this class( $I_i\sim k_i^0$), a prediction supported by their bounded P(I) (Fig. 1b1 and b3). (d) Heterogeneous impact, observed when φ ≠ 0 in (11), for which P(I) is driven by P(k). For (d1) we predict φ = 3/2 and for (d2) φ = 1, in perfect agreement with the numerical results. As I_i depends on k_i in this class P(I) is driven by P(k) (Fig. 1b2 and b4).

Fig. 3. Propagation of perturbations

(a) The propagation to distant nodes is governed by the structure of g(f⁻¹(x)) through the leading terms of (8), which determine the dissipation rate, β, in (14). (b) Conservative dynamics: If the leading term in (8) is m₀ ≠ 0 we have β = 0, predicting a conservative propagation, in which perturbations penetrate the network without loss. As a result Γ(l) = 1 (14) and P(G) ∼ G⁻² (15). We predict that and are in this class, as confirmed by results in Figs. 1a1 - a2 and d1 - d2. (c) Dissipative dynamics: If the leading terms in (8) are g(f⁻¹(x)) ∼ b₀ + x^m₁ we have β = m₁ > 0 in (14), leading to a dissipative propagation, in which perturbations decay exponentially with network distance. As a result P(G) ∼ G^−ν (15) where 1 < ν < 2 (16). For and we predict β = 1 and hence ν = 3/2, in perfect agreement with the results of Figs. 1a3 - a4 and d3 - d4.

Fig. 4. Cascade sizes

(a) The cascade size is jointly driven by two mechanisms: the local impact of a node on its nearest neighbors (I_i) and the propagation from the neighbors to the rest of the network (Γ(l)). Hence $C_i\sim k_i^{\omega }$, where ω is determined by both φ and β (18). (b) Four classes of dynamical behavior emerge: (b1) For we have β = 1 and φ = 0, predicting ω = 1/2, and hence heterogeneous cascades with P(C) driven by P(k), as confirmed by Fig. 1e3. Here the local dynamics is uniform (Fig. 1b3), and yet, remarkably, the global cascades can be heterogeneous due to the dissipative propagation (β > 0). (b2) For we have β = φ = 1, predicting ω = 1, a heterogeneous cascade dynamics, as shown in Fig. 1e4. (b3) For we have β = φ = 0, and hence ω = 0, predicting uniform cascades. Here even if P(k) is fat-tailed, P(C) will be bounded, so that the dynamical behavior is largely independent of the topological heterogeneity (Fig. 1e1). (b4) For we have β = 0 and φ = 3/2, predicting ω = 3/2, a heterogeneous cascade dynamics, as shown in Fig. 1e2. The heterogeneity in this case, in which β = 0, is driven by the local dynamics and hence P(C) ∼ P(I) (Fig. 1b2).

Fig. 5. Uncovering the dynamical universality class from empirical data

Human Dynamics: We constructed G_ij from the correlations in the usage patterns of users in an email network [48] (Sec. S.VIII.A). (a1) The stability vs. k_i follows $S_i\sim k_i^{\delta }$ with δ = 2.4 ± 0.2, predicting heterogeneous stability. (a2) As expected for heterogeneous stability, the system features a fat-tailed P(S). (b1) - (b2) The local impact vs. k_i follows $I_i\sim k_i^{\phi }$ with φ = 2.1 ± 0.1, predicting heterogeneous impact with a fat-tailed P(I). (c1) The correlation function Γ(l) does not decay, indicating conservative dynamics. (c2) As expected for conservative dynamics, P(G) ∼ G^−ν with ν = 2. (d1) - (d2) From the measured β and φ we predict ω = 2.1 in (17) and hence expect a fat-tailed P(C). As β = 0 we also expect that P(C) ∼ P(I). Indeed, we find that P(C) ∼ C^−1.5 and P(I) ∼ I^−1.5, in agreement with the prediction for a scale-free network (Sec. S.VII.E). For large ki the cascades saturate due to the finite size of the network (N = 2, 668). Cellular Dynamics: To test our predictions for a biological system we collected perturbation data in which 55 yeast genes were perturbed, measuring their impact on the rest of the 6, 222 genes, giving rise to a 6, 222 × 55 correlation matrix, G_ij [49]. Lacking the wiring diagram we could not measure δ, φ, β and ω directly. Yet, we can identify the universality class by measuring P(I), P(S), P(G) and P(C), which do not require knowledge on the underlying topology (Sec. S.VIII.B). (e) P(S) indicates uniform stability (δ = 0); (f) P(I) indicates heterogeneous impact (φ ≠ 0), in which P(I) ∼ I⁻¹; (g) P(G) has ν = 2, indicating conservative dynamics (β = 0); (h) From the inferred values of φ and β we predict ω > 0, foreseeing heterogeneous cascades, a prediction supported by the fat-tailed P(C) ∼ C⁻¹. As β = 0, we expect that cascade heterogeneity is driven by the local dynamics, also supported by the fact that P(C) ∼ P(I).