Universality in Network Dynamics

Baruch Barzel (left) and Albert- László Barabási (right)

Authors: Baruch Barzel^1,2 and Albert- László Barabási^1,2.3

Affiliation:
¹Center for Complex Network Research and Departments of Physics, Computer Science and Biology, Northeastern University, Boston, USA
²Center for Cancer Systems Biology, Dana-Farber Cancer Institute, Harvard Medical School, Boston, USA
³Department of Medicine, Brigham and Women’s Hospital, Harvard Medical School, Boston, USA.

We think of statistical mechanics as the theory of interacting particles, gases and liquids. Its toolbox, however - indeed, its way of thought - goes beyond the domain of material science. In a broader perspective what statistical mechanics provides us with is a bridge between the microscopic description of a system and its observed macroscopic behavior. With it we can track the way in which system-level phenomena emerge from the mechanistic description of the system’s interacting components. For instance how the blind interactions between pairs of magnetic spins lead to the seemingly cooperative phenomena of magnetism, or, alternatively, how individual human interactions lead to the spread of ideas and perceptions.

At the heart of many of these emergent behaviors lies a rather simple characteristic of the system – its geometry. Indeed, many predictions in statistical mechanics can be traced back to the underlying geometry of the system’s interactions; most importantly, the system’s dimension [1,2]. This focus on geometry and dimensionality naturally portrays a picture of particles interacting in a defined topological structure, such as a lattice (or lattice-like) embedding. Recently, however, we have begun to shift our attention towards less structured systems – complex systems - which exhibit highly random and non-localized interaction patterns. Social networks, biological interactions and technological systems, such as the Internet or the power grid, are just a few examples, all of which are described by complex interaction networks, profoundly different from lattices, and hence they confront us with a potentially new class of observed dynamical behaviors.

The complex network geometry is distinguished by two key topological properties. First is the famous small world phenomenon. To understand it let us begin by observing the behavior of structured, lattice-like, systems. In such systems the number of nodes, i.e. the volume, and the typical distance between nodes are closely related – they follow the scaling law N (l )∼l ^d, where d represents the system’s dimension. In contrast networked systems are much more crowded. Within a small distance you can visit an exponentially proliferating volume of nodes [3]

so that the average distance between nodes does not scale with the system’s volume. This is the secret that allows enormous systems, such as society, to be connected by extremely short paths. Even just a small amount of structural randomness is sufficient to push the system into the small world limit [4], rendering the unique geometry described by (1) to be, in fact, not so unique. Indeed, Eq.(1) is observed by practically all complex systems, biological, social and technological. The second notion we must put aside when dealing with complex systems is the idea of a uniform pattern of connections. The random nature of complex systems invokes heterogeneity between the nodes and each node interacts with a different number of neighbors, leading to a distribution of node degrees P (k ). Most complex systems have been shown to feature a fat-tailed P (k ), describing an extremely heterogeneous structure in which a majority of low degree nodes coexists with a small amount of highly connected hubs [5].

This complex geometry raises an array of questions on the expected behavior of complex systems: What role does the broad span of degrees play in the system? Are the hubs really more influential than the average node? Are they more or, perhaps, less sensitive to their neighbors’ influence? We would also like to understand the impact of the small world topology. If all nodes are connected by short network paths, does that imply that they are also within each other’s dynamical reach? That would describe a system in which all nodes are impacted by all other nodes, a rather unstable scenario.

Of course, the answer to these questions is not purely in the geometry, but rather in the interplay between this geometry and the dynamics of the system, specifically in the meaning that lies behind the network links. By meaning we refer to the fact that the reduction of a complex system into a network structure gives no account to the type of interaction that occurs between node pairs – from chemical binding in biological networks to viral infection in social systems – the links in different systems represent different dynamical mechanisms or rules of interaction. We account for this diversity, by writing a most general equation for the activities, x_i, of all nodes

The first term on the r.h.s. of (2) accounts for the self-dynamics and the second term sums over all of i’s interacting partners (A_ij is the adjacency matrix, or the network). With the proper choice of the non-linear W (x_i) and Q (x_i ,x_j), Eq. (2) quite generally covers a broad array - indeed almost all - deterministic pairwise dynamics, among which are models frequently implemented on networks, such as biochemistry [6], genetic regulation [7], social [8] and ecological phenomena [9]. Hence Eq. (2) accounts for the inner mechanisms of the interaction rules, providing the microscopic description of the system’s dynamics.

To observe the system’s macroscopic behavior we use a perturbative approach. First we induce a small permanent perturbation dx_j on the steady state of node j, representing, for instance the knockout of a gene in a cellular network or the failure of a node in a technological system. We then measure the response of all other nodes in the system, constructing the response matrix

This translates the structural properties of the system – who is connected to whom – into its dynamical patterns of influence, namely who is affected by whom. The G_ij matrix provides an extremely detailed account of the system’s response to external perturbations – a term for each pair of nodes in the system. We obtain more meaningful insight on the system’s behavior by focusing on a set of aggregate functions extracted from (2), that are designed to directly answer the questions posed above.

Local dynamics: To understand the dynamical role of a node’s degree we characterize the dynamics between a node, i, and its immediate surrounding by measuring: (i) the impact, I_i , of i ’s perturbation on its direct neighbors; (ii) the response of i  to neighboring perturbations. The latter quantifies i ’s dynamical stability, S_i , since a dramatic response to perturbations characterizes i as unstable, whereas a suppressed response implies high stability. We show that these two functions depend on i’s degree as

where the exponents δ and φ are fully determined by the leading terms of the functions W (x_i) and Q (x_i ,x_j) of Eq. (2). The exponents δ and φ determine the dynamical consequence of the network’s degree heterogeneity by relating the dynamical impact/response of a node to its degree. Eq. (4) tells us that different dynamical systems will be characterized by different exponents δ and φ, depending on the form of Eq. (2), and consequently they will express different patterns of influence between hubs and peripheral nodes.

Most importantly, δ and φ predict the existence of four highly distinctive dynamical universality classes. If, for example, φ=0, we find that a node’s impact is independent of its degree. All nodes exhibit uniform impact, regardless of the nature of the degree distribution, P (k ) (fat-tailed or bounded). Hence even under extreme structural heterogeneity, i.e. a fat-tailed P (k ), all nodes will have a comparable dynamical impact. If, however φ≠0, the dynamical impact is driven by P (k ), and consequently, for a scale-free network, the system will feature heterogeneous impact, in which most nodes have a tiny effect on their surrounding and a small group of selected nodes dominate the system’s local dynamics. A similar distinction, between uniform and heterogeneous stability, emerges from the universal value of δ. What is striking is that these crucial distinctions are determined by a rather general formulation of the dynamics (2), just a small number of leading terms. Finer details, such as higher order terms of (2), specific rate constants or the detailed structure of the network, play no role. As a result the predicted universality classes encompass a broad range of distinctive dynamics. For instance, all biochemical interactions are predicted to feature uniform stability; epidemic spreading processes will inevitably display heterogeneous impact.

Figure 1: From microscopic diversity to macroscopic universality. (a) Dynamical networks exhibit diverse types of interaction dynamics, from ecological to biological and social networks. (b) This diversity is described by a general dynamical equation (2), whose terms account for the microscopic interaction mechanisms between the nodes. (c) We observe the system’s behavior through G_ij (3), capturing the patterns of influence characterizing the system. Systems are restricted to limited classes of dynamical behavior: uniform (blue) versus heterogeneous (orange) impact (top-left); uniform versus heterogeneous stability (bottom-left); conservative versus dissipative propagation (bottom-center). These classes determine other dynamical functions such as the cascade size distribution (top-right) and the correlation distribution (bottom-right).

Propagation: Perhaps the most crucial, and yet quite elusive, dynamical function in a network environment is the propagation of perturbations from the perturbed source to more distant nodes. This is captured by the distance dependent correlation function, Γ(l ), which tracks the impact of a perturbation at distance l. We find, analytically, that perturbations decay exponentially as

where, like δ and φ, the dissipation rate, β, is fully determined by the leading terms of W (x_i) and Q (x_i , x_j) in (2). The correlation function describes the efficiency of the network in propagating information. A rapid decay of Γ(l ) ensures that perturbations remain localized, dying out before they reach most nodes. A slow decay describes efficient penetration of perturbations. Again, we find two distinctive dynamical classes: if β=0 in (5) we observe conservative dynamics, in which perturbations penetrate the network without loss, conserving the mass of the initial perturbation. If, however, β>0, the system is dissipative, perturbations decay exponentially, and the dynamics is localized in the vicinity of the perturbed node. The case where β<0, describing an unstable response with perturbations growing out of control, is prohibited in the limit of the small-world topology (1), a crucial feature explaining the observed resilience of many complex systems to perturbations.

As for δ and φ, the value of β is insensitive to details. The specific parameters and detailed network structure have a marginal effect. Hence this distinction between conservative vs. dissipative dynamics represents a broad classification, where each class consists of many different dynamical systems. For instance, all spreading processes are dissipative; and all biochemical or population dynamics are conservative. Another way to state this is that in order to transfer a system between any of the above universality classes, uniform vs. heterogeneous or conservative vs. dissipative, it is not enough to tune a parameter or make a minor change in the dynamics. One must change the leading terms of Eq. (2), that is essentially alter the internal mechanisms of the interactions: change the system from, say, an epidemic spreading social system to a genetically regulated biological system. Hence the predictions (4) and (5) touch upon the defining features of the network’s dynamics.

The prediction of the local dynamics (4) together with the propagation (5) allows us to predict a much broader set of macroscopic dynamical functions. Indeed, the global response of the system to a perturbation is a direct consequence of the coupling between the local response and the propagation to more distant nodes. In that sense the universal exponents δ, φ and β serve as building blocks for the construction of a broad range of universal functions extracted from G_ij . To demonstrate this we found that we can use (4) and (5) to predict the precise form of the cascade size distribution, P (C ), and the correlation distribution P (G ). These two functions, among the most frequently pursued in empirical observations of complex systems’ dynamics [10-14], have long been known to exhibit universal behavior, for which we lacked an adequate theoretical explanation. Now we can use Eqs. (4) and (5) to predict these functions and express them in terms of δ, φ and β. The meaning is that P (C ) and P (G ) inherit their universality from S_i , I_i and Γ(l ). Hence our formalism not only provides a general explanation for the universality of P (C ) and P (G ), but also allowed us to analytically predict them directly from the structure of (2), connecting these pertinent macroscopic observations with a microscopic understanding of the system’s mechanistic interactions.

Going back to the fundamental paradigm of statistical mechanics, we make a rather strong prediction: that the observed macroscopic dynamics of complex systems can be predicted directly from its microscopic description (Eq. (2)), providing a set of universal exponents. Hence, while microscopically, complex systems exhibit a broad range of diverse dynamical models, across multiple fields and scientific domains, their macroscopic behavior condenses into a discrete set of dynamical universality classes. This is an optimistic message if our goal is to predict the behavior of complex systems. Indeed, universality provides us with predictive power, as it shows little sensitivity to microscopic details. It therefore helps make complex systems, a bit more… simple.

References: 
[1] Leo P. Kadanoff. "Scaling and Universality in Statistical Physics", Physica A 163, 1 (1990). Article.
[2] Kenneth G. Wilson. "The renormalization group: critical phenomena and the Kondo problem". Review of Modern Physics, 47, 773 (1975). Abstract.
[3] Mark E.J. Newman. "Networks - an introduction". Oxford University Press, New York, (2010). 
[4] Duncan J. Watts and Steven H. Strogatz. "Collective dynamics of ‘small-world’ networks". Nature, 393, 442 (1998). Abstract. 
[5] Albert-László Barabási, Réka Albert. "Emergence of scaling in random networks". Science, 286, 509 (1999). Abstract.
[6] Eberhard O. Voit. "Computational analysis of biochemical systems" (Cambridge University Press, 2000). Google Book.
[7] Guy Karlebach and Ron Shamir. "Modelling and analysis of gene regulatory networks". Nature Reviews,  9, 770–780 (2008). Abstract.
[8] P.S. Dodds and D.J. Watts. "A generalized model of social and biological contagion". Journal of Theoretical Biology, 232, 587–604 (2005). Abstract.
[9] Artem S. Novozhilov, Georgy P. Karev and Eugene V. Koonin. "Biological applications of the theory of birth-and-death processes". Briefings in Bioinformatics, 7, 70–85 (2006). Article.
[10] Chikara Furusawa and Kunihiko Kaneko. "Zipf's law in gene expression". Physical Review Letters, 90, 088102 (2003). Abstract.
[11] Victor M. Eguíluz, Dante R. Chialvo, Guillermo A. Cecchi, Marwan Baliki, A. Vania Apkarian. "Scale-free brain functional networks". Physical Review Letters, 94, 018102 (2005). Abstract. 
[12] J. Leskovec M. Mcglohon, C. Faloutsos, N. Glance and M. Hurst. "Patterns of cascading behavior in large blog graphs". Proceeding of the SIAM International Conference on Data Mining , 551–556 (2007). 
[13] Paolo Crucitti, Vito Latora and Massimo Marchiori. "Model for cascading failures in complex networks". Physical Review E, 69, 045104 (2004). Abstract.
[14] Ian Dobson, Benjamin A. Carreras, Vickie E. Lynch and David E. Newman. "Complex systems analysis of series of blackouts: Cascading failure, critical points, and self-organization". Chaos 17, 026103 (2007). Abstract.