Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2013:9:673-681.
doi: 10.1038/nphys2741.

Universality in network dynamics

Affiliations

Universality in network dynamics

Baruch Barzel et al. Nat Phys. 2013.

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.

PubMed Disclaimer

Figures

Fig. 1
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 formula image and formula image ν = 2 and for formula image 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 formula image and formula image both P(I) and P(S) are bounded independently of P(k), for formula image P(I) is fat-tailed on a scale-free network while P(S) is bounded, and for formula image both are fat-tailed. For scale-free networks (P(k) ∼ kγ) we can predict P(S) and P(I) using P(K = ky) ∼ KY, 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): formula image and formula image exhibit conservative propagation, as perturbations penetrate the network without loss; formula image and formula image 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 ( formula image, formula image, and ε P(C) is driven by P(k), being consequently fat-tailed or bounded, formula image 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
Fig. 2. Local dynamics: Stability and Impact
The stability Si, 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, formula image (a1), formula image (a2) and formula image (a3) belong to this class, featuring Siki0. 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), Si depends on ki and P(S) is driven by P(k), being fat-tailed if P(k) is fat-tailed. For formula image (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 Si [54]. Impact, Ii, characterizes the influence of i on its immediate neighbors. (c) Uniform impact, observed for φ = 0 in (11), leads to a bounded P(I). formula image (c1) and formula image (c2) belong to this class( Iiki0), 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 formula image (d1) we predict φ = 3/2 and for formula image (d2) φ = 1, in perfect agreement with the numerical results. As Ii depends on ki in this class P(I) is driven by P(k) (Fig. 1b2 and b4).
Fig. 3
Fig. 3. Propagation of perturbations
(a) The propagation to distant nodes is governed by the structure of g(f−1(x)) through the leading terms of (8), which determine the dissipation rate, β, in (14). (b) Conservative dynamics: If the leading term in (8) is m0 ≠ 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−2 (15). We predict that formula image and formula image 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−1(x)) ∼ b0 + xm1 we have β = m1 > 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 formula image and formula image we predict β = 1 and hence ν = 3/2, in perfect agreement with the results of Figs. 1a3 - a4 and d3 - d4.
Fig. 4
Fig. 4. Cascade sizes
(a) The cascade size is jointly driven by two mechanisms: the local impact of a node on its nearest neighbors (Ii) and the propagation from the neighbors to the rest of the network (Γ(l)). Hence Cikiω, where ω is determined by both φ and β (18). (b) Four classes of dynamical behavior emerge: (b1) For formula image 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 formula image we have β = φ = 1, predicting ω = 1, a heterogeneous cascade dynamics, as shown in Fig. 1e4. (b3) For formula image 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 formula image 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
Fig. 5. Uncovering the dynamical universality class from empirical data
Human Dynamics: We constructed Gij from the correlations in the usage patterns of users in an email network [48] (Sec. S.VIII.A). (a1) The stability vs. ki follows Sikiδ 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. ki follows Iikiφ 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, Gij [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−1; (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−1. As β = 0, we expect that cascade heterogeneity is driven by the local dynamics, also supported by the fact that P(C) ∼ P(I).

References

    1. Caldarelli G. Scale-free networks: complex webs in nature and technology. Oxfrod University Press; New York: 2007.
    1. Drogovtsev SN, Mendez JFF. Evolution of networks: from biological nets to the Internet and WWW. Oxford University Press; Oxford: 2003.
    1. Strogatz SH. Exploring complex networks. Nature. 2001;410:268–276. - PubMed
    1. Helbing D, Jost J, Kantz H, editors. Networks and Heterogeneous Media (NHM) Vol. 3. AIMS; Springfield, MO., USA: 2008. Networks and complexity; pp. 185–411.
    1. Newman MEJ. Networks - an introduction. Oxford University Press; New York: 2010.

LinkOut - more resources