Guide To Temporal Networks, A

Naoki Masuda, Renaud Lambiotte

• Publisher: WSPC (EUROPE)
• Year: 2016
• ISBN:
  9781786341167
• Topic: Biological Sciences
• Subtopic: Science General
• Index: Biological Sciences

Network science offers a powerful language to represent and study complex systems composed of interacting elements — from the Internet to social and biological systems. In its standard formulation, this framework relies on the assumption that the underlying topology is static, or changing very slowly as compared to dynamical processes taking place on it, e.g., epidemic spreading or navigation. Fuelled by the increasing availability of longitudinal networked data, recent empirical observations have shown that this assumption is not valid in a variety of situations. Instead, often the network itself presents rich temporal properties and new tools are required to properly describe and analyse their behaviour.

A Guide to Temporal Networks presents recent theoretical and modelling progress in the emerging field of temporally varying networks, and provides connections between different areas of knowledge required to address this multi-disciplinary subject. After an introduction to key concepts on networks and stochastic dynamics, the authors guide the reader through a coherent selection of mathematical and computational tools for network dynamics. Perfect for students and professionals, this book is a gateway to an active field of research developing between the disciplines of applied mathematics, physics and computer science, with applications in others including social sciences, neuroscience and biology.

Chapter 1

Introduction

A network is a collection of nodes and links, where a link connects two nodes. Many social, natural and engineered systems can be represented as networks. Examples include friendship networks, international relationships, gene regulatory networks, food webs, airport networks and the Internet just to name a few. Since the late 1990s, our understanding of real networks, from large to small ones, has been significantly advanced with the integration of theoretical, computational and conceptual tools from statistical physics, computer science, engineering, mathematics and other domains. Many networks have been recognised to be complex but governed by beautiful and universal laws. Together with applications, this field of research can be collectively called network science.

Evidence suggests that empirical networks observed in a variety of domains are far from static. It has been known since the advent of network science, and even earlier, that many networks grow in time. However, growth is not the only way in which networks evolve. Nodes and links may emerge and disappear during the lifetime of a network. For instance, the same link may be active just for a short period but repetitively with intermittent periods. Moreover, a rate of link activation may depend on time. Complex dynamical patterns of networks may arise for many reasons — circadian and weekly rhythms of actors, interactions between different links, stochasticity, finite response time of a system and so forth. These issues are at the core of the study of temporal networks, also called time/temporally varying networks/graphs, evolving graphs and evolutionary network analysis. The present book is about temporal networks and focuses on mathematical and computational tools to describe and model their behaviour.

As an illustration, let us consider the networks composed of pupils and teachers in a primary school at four time points in a day, shown in Fig. 1.1. The figure indicates that the network varies over time, reflecting the daily schedule of the school. We would lose a lot of information by aggregating the four networks into one and discarding the temporal information in the original data. This includes possible correlations between link activations, the order in which links appear and disappear, circadian rhythms of human activity and so on.

Fig. 1.1 Snapshots of dynamic face-to-face contact patterns in a primary school [Stehlé et al. (2011)]. A circle represents a school class. A node in the centre of a circle is a teacher. The other nodes are pupils. Networks at four time points are shown. This figure is generated from the video available at http://www.sociopatterns.org/gallery/ with a permission.

Why does temporality matter? Do we have to bother and consider this additional dimension of networks on top of already complex static networks, making things even more complicated? Does the temporality of networks significantly alter our understanding of how networked systems function? Figure 1.2 provides affirmative evidence. Figure 1.2(a) shows a temporal network composed of four individuals. The time flows along the horizontal axis. Two individuals have a conversation event when there is a vertical line. There are four conversation events. In the third one, individuals 2 and 4 talk with each other without involving individual 3. If individual 1 starts propagating a news that the other three individuals have not heard of, the news reaches the entire network via conversation events. For example, individual 4 hears it from individual 2 through the path shown by the dotted arrows. However, if the news starts from individual 4, it cannot reach individual 1 within this temporal network. Although each conversation event is a symmetric event, allowing the information flow in both directions (e.g., from 1 to 2 and from 2 to 1), temporality of the network introduces asymmetry in the information flow at a network level.

Fig. 1.2 Comparison of temporal and static networks. (a) A temporal network composed of four individuals and four events. (b) Aggregate network corresponding to the temporal network shown in (a). The width of the line represents the weight of the communication between the two individuals as quantified by the number of events observed on a link.

If we aggregate the temporal network, we obtain the static network shown in Fig. 1.2(b), which we call the aggregate network. In the aggregate network, the information on the timing of the events is discarded, and the fact that individuals 2 and 3 communicate twice in Fig. 1.2(a) is represented by a link twice thicker than the other two links. Aggregate networks, which are static objects, are often deceptive. In Fig. 1.2(b), individual 2 connects to everybody else and acts as a hub. A news starting from anybody can eventually reach anybody else through individual 2. However, if we unfold the temporal information, we clearly see that this conclusion is incorrect (Fig. 1.2(a)). A news starting from individual 4 cannot reach individual 1. This example is anecdotal, but it warns us of the importance of temporality in understanding network phenomena.

In this book, we are interested in the combination of complexity of network structure and complexity induced by temporal behaviour of the network. There are already excellent review papers [Holme and Saramäki (2012); Aggarwal and Subbian (2014); Holme (2015)] and an edited book [Holme and Saramäki (2013)] on temporal networks. The objective of this book is to be an entry point to the mathematical and computational analysis of temporal networks. Therefore, we do not provide an exhaustive list of recent literature in the field. We instead provide an introduction to tools required for analysing temporal networks and focus on a selection of models and algorithms. Among the subjects that we do not treat in this book, let us mention adaptive networks, where the structure of the network and the state of the nodes co-evolve in time [Gross and Blasius (2008); Gross and Sayama (2009)]. In the following, we thus assume that temporal dynamics of networks are exogenously given by data or models.

The organisation of the book is as follows. In Chapter 2, we introduce mathematical tools from probability theory, linear algebra and others, which are used in the subsequent chapters. In Chapter 3, we summarise basics and a selection of advanced topics on temporally static networks. Because there are various monographs, review papers and online resources on static networks already (e.g., [Newman (2010); Barabási (2016)]), our exposure is not intended to be comprehensive but limited to the materials used in the later chapters on temporal networks. Therefore, we deliberately omitted some of the topics that would be contained in standard network science books. Examples include the Watts-Strogatz model, small-world effects, degree correlation, much of centrality measures, much of percolation, spatial networks and much of multilayer networks. Except for random walks, which are crucial in a variety of algorithms, dynamics on networks are not treated in this chapter. They are introduced later in Chapter 6. The last three chapters are the main chapters of this book, where we discuss temporal networks, with an emphasis on mathematical and computational tools. In Chapter 4, we explain various measurements and properties of temporal networks. In particular, we stand on two main representations of temporal networks among others and emphasise which representation is amenable to which measurements. In Chapter 5, we introduce generative models of temporal networks. In Chapter 6, we introduce a selection of models and analysis of dynamics on temporal networks.

Table 1.1 Main variables.

Variable	Meaning
N	number of nodes
M	number of links
tmax	number of snapshots; sometimes the observation period
τ	inter-event time
ψ(τ)	distribution of inter-event times
A	adjacency matrix
L	Laplacian matrix
d	distance, variously defined
Q	modularity
vi	ith node
ki	degree of node vi
〈x〉	mean of x

Main notations used throughout the book are summarised in Table 1.1. Furthermore, we use two order notations;

in this book indicates that a quantity is proportional to

indicates that a quantity is much less than

. We use ∝ to indicate proportional to, and ≈ to approximately equal to.

We conclude this introductory chapter by stating some outstanding questions that warrant future work and could be tempting for the reader. First, many temporal networks occur as a result of mobility of individuals. Examples include social contact networks of humans, where a contact is defined by physical proximity, animals’ networks due to animal trades and networks of robots exploring a two-dimensional arena. Relationships between mobility and temporal networks are yet unclear. In fact, mobility is regulated by spatial constraints. For example, individuals tend to visit nearby rather than remote sites. One place may not be able to host individuals beyond its capacity, which provides another constraint on mobility. Extending spatial networks [Barthélemy (2011)] and temporal networks to spatio-temporal networks may be an interesting line of research.

Second, related to spatial networks, metapopulation models (Sections 5.8 and 6.4.2) are a powerful framework with which to theoretically and empirically study the impact of human mobility on population dynamics, such as epidemic processes. Individuals in a metapopulation model network can be considered to form a temporal network. What is the relationship between the two?

Third, temporal networks are time series of networks. Time series analysis including multivariate ones has been studied for a long time in statistics, signal processing and other research communities. We will glimpse into the intersection between time series analysis and temporal networks when we discuss change point analysis (Section 4.10) and link prediction (Section 4.11). Nevertheless, various tools and concepts available in time series analysis have been underused for analysing temporal networks.

Fourth, related to time series analysis, there are methods to infer causality between time series, such as the Granger causality [Granger (1969)], transfer entropy [Schreiber (2000)] and convergent cross mapping [Sugihara et al. (2012)]. Once detected, causality may be represented as a directed link in a network. These methods as w...

Table of contents

• Cover
• Halftitle
• Series Editors
• Title
• Copyright
• Preface
• Acknowledgments
• Contents
• 1. Introduction
• 2. Mathematical toolbox
• 3. Static networks
• 4. Analysis of temporal networks
• 5. Models of temporal networks
• 6. Dynamics on temporal networks
• Appendix A Discrete-time random walks on the line
• Appendix B Transient and absorbing states of Markov chains
• Appendix C Derivation of the degree distribution of the Barabási-Albert model
• Bibliography
• Index