Universality in Network Dynamics
Authors: Baruch Barzel1,2 and Albert- László Barabási1,2.3
1Center for Complex Network Research and Departments of Physics, Computer Science and Biology, Northeastern University, Boston, USA
2Center for Cancer Systems Biology, Dana-Farber Cancer Institute, Harvard Medical School, Boston, USA
3Department 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 
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, xi, of all nodes
To observe the system’s macroscopic behavior we use a perturbative approach. First we induce a small permanent perturbation dxj 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
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, Ii , of i ’s perturbation on its direct neighbors; (ii) the response of i to neighboring perturbations. The latter quantifies i ’s dynamical stability, Si , 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
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 Gij (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
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 Gij . 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 Si , Ii 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.
 Leo P. Kadanoff. "Scaling and Universality in Statistical Physics", Physica A 163, 1 (1990). Article.
 Kenneth G. Wilson. "The renormalization group: critical phenomena and the Kondo problem". Review of Modern Physics, 47, 773 (1975). Abstract.
 Mark E.J. Newman. "Networks - an introduction". Oxford University Press, New York, (2010).
 Duncan J. Watts and Steven H. Strogatz. "Collective dynamics of ‘small-world’ networks". Nature, 393, 442 (1998). Abstract.
 Albert-László Barabási, Réka Albert. "Emergence of scaling in random networks". Science, 286, 509 (1999). Abstract.
 Eberhard O. Voit. "Computational analysis of biochemical systems" (Cambridge University Press, 2000). Google Book.
 Guy Karlebach and Ron Shamir. "Modelling and analysis of gene regulatory networks". Nature Reviews, 9, 770–780 (2008). Abstract.
 P.S. Dodds and D.J. Watts. "A generalized model of social and biological contagion". Journal of Theoretical Biology, 232, 587–604 (2005). Abstract.
 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.
 Chikara Furusawa and Kunihiko Kaneko. "Zipf's law in gene expression". Physical Review Letters, 90, 088102 (2003). Abstract.
 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.
 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).
 Paolo Crucitti, Vito Latora and Massimo Marchiori. "Model for cascading failures in complex networks". Physical Review E, 69, 045104 (2004). Abstract.
 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.