Understanding dynamic networked systems: when ordering matters
A novel way to analyse time-stamped data from networked systems enables better understanding of the way in which network dynamics can change the properties of complex adaptive systems.
In the connected world we live in, complex networked systems are all around us. Obvious examples of these include telecommunication networks like the Internet, interconnected infrastructures like the electrical grid and the social fabric in which we are embedded. Less obviously, our lives also depend on networks that are at work within us, such as those formed by the interactions of proteins, connections between neurons and chains of chemical reactions within our cells. We often study the properties of complex systems such as these from the perspective of complex networks, which abstract the elements of a system into nodes connected via links. This network perspective provides us with rich tools which enable us to address important questions about complex systems. Which of the nodes are crucially important for the functioning of systems, and how does their link topology influence their resilience and performance? How does the spread of information, rumours and epidemics occur in social systems, and who are the most influential individuals? Finally, how can we purposefully manipulate biological networks to prevent or cure diseases? These are the questions we hope to address.
Although these questions raise some promising prospects, an important problem becomes apparent as fine-grained data on real-world systems is made available: the network topologies of these systems are not fixed, but rather change continuously. For example, members of a social network are not in touch with all of their acquaintances at all times. Instead, they contact each other in certain temporal patterns. This may seem obvious, but it poses a problem in terms of how we typically represent networked systems. We generally consider these systems to be static, aggregating all links that occur over a certain time. This approach neglects the temporal dimension of complex systems. Consequently, the wrong conclusions may bedrawn regarding the robustness of systems, the importance of nodes or the evolution of dynamical processes.
These problems have been addressed extensively only recently, under the umbrella of `temporal networks’. Taking a macroscopic perspective, most of the work in this area has focused on the statistics of inter-event times, such as those between consecutive link or node activations. Highlighting the importance of temporal characteristics, these efforts constitute important contributions. However, they do not answer a simple yet important question: How does the order of links affect networked systems? Notably, this ordering is disregarded when we aggregate links into static networks—see Figure 1—just as it is when we study the way in which links are statistically distributed across time.
It is easy to see that the ordering of links critically affects causality in temporal networks. Consider a simple system with three nodes A, B and C, connected by two links, A-B and B-C. Clearly, A is only connected to C via a so-called time-respecting path if the link A-B appears before B-C. If the ordering of links is reversed, A cannot influence C. Based on this simple idea, we have studied the effect of the order of links in complex networked systems using two approaches.
In our first study, we calculated the statistics of time-respecting paths for real networked systems and compared them to the statistics obtained from a random model. Importantly, this model was chosen such that it corresponded to what we expected from a static, time-aggregated representation of the system (i.e., the perspective commonly used in network-theoretic studies). Our results show that time-respecting paths in real systems differ significantly from what we expect from a static perspective. We further introduced an information-theoretic measure and used it to quantify the information hidden in the order of links. We found ordering to matter in all of the real-world systems that we studied.
An important additionalquestion is how this ordering affects dynamical processes such as diffusion, or the spread of information or diseases. By studying a model for epidemics, we found that the ordering of links alone can slow down spreading by as much as 80%. While this work highlights the magnitude of the problem, we have also addressed how we can more reasonably analyse time-stamped network data. A major problem with static network representations is that they give rise to false expectations about transitivity. In the example introduced above, from the presence of a link A-B and B-C we would expect a transitive relation between A and C to exist. However, the order of links breaks this transitivity, rendering concepts such as adjacency or Laplacian matrices, which are commonly used in the analysis of complex networks, useless.
To solve this problem, we introduce higher-order time-aggregated networks, which can be defined based on higher-order Markov models of link sequences. Importantly, this representation allows both the topology and the ordering of links to be captured while simultaneously incorporating memory effects present in empirical link sequences. Furthermore, this representation enables the application of standard techniques from network theory. We were able to demonstrate the power of this framework in real-world data sets. Not only does this allow us to analytically and accurately predict how the ordering of links slows down diffusion processes, it also helps us to understand why, in some systems, the mere ordering of links speeds up dynamical processes.
In summary, we have been able to show that the ordering of links in temporal networks significantly affects the characteristics of complex systems. Furthermore, we have shown how these order-dependent changes can be understood using a generalization of the commonly applied network perspective. Our approach opens interesting perspectives for analytical studies of dynamical processes, the development of new clustering techniques for application in data mining and machine learning, and the design of novel centrality measures. Our results further highlight the need for both the temporal and topological dimension of complexity in biological and socio-technical systems to be taken into account. We are currently exploring the ways in which our novel perspective can help us to better retrieve relevant documents in information systems, and how network-based measures can be extended in such a way that they do not neglect the order of links in time-stamped relational data.
- P. Holme and J. Saramäki, Temporal networks, Phys. Rep. 519, pp. 97–125, 2012.
- M. Morris and M. Kretzschmar, Concurrent partnerships and transmission dynamics in networks, Soc. Networks 17, pp. 299–318, 1995.
- M. Karsai, M. Kivelä, R. K. Pan, K. Kaski, J. Kertész, A.-L. Barabási and J. Saramäki, Small but slow world: how network topology and burstiness slow down spreading, Phys. Rev. E 83, p. 025102, 2011.
- N. Perra, B. Gonçalves, R. Pastor-Satorras and A. Vespignani, Activity driven modeling of time varying networks, Sci. Rep. 2, 2012.
- M. Starnini, A. Baronchelli, A. Barrat and R. Pastor-Satorras, Random walks on temporal networks, Phys. Rev. E 85, p. 056115, 2012.
- L. E. C. Rocha and V. D. Blondel, Bursts of vertex activation and epidemics in evolving networks, PLoS Comput. Biol. 9, p. e1002974, 2013.
- R. Pfitzner, I. Scholtes, A. Garas, C. J. Tessone and F. Schweitzer, Betweenness preference: quantifying correlations in the topological dynamics of temporal networks, Phys. Rev. Lett. 110, p. 198701, 2013.
- I. Scholtes, N. Wider, R. Pfitzner, A. Garas, C. J. Tessone and F. Schweitzer, Causality-driven slow-down and speed-up of diffusion in non-Markovian temporal networks, Nat. Commun. 5, p. 5024, 2014.
- M. Rosvall, A. V. Esquivel, A. Lancichinetti, J. D. West and R. Lambiotte, Memory in network flows and its effects on spreading dynamics and community detection, Nat. Commun. 5, p. 4630, 2014.