Keywords

1.1 Overview

If we want to make sense of large and complicated systems via the data they leave behind, we need to simplify them systematically. Such simplifications typically need to be very drastic. A common first step is to represent the system as a network that only stores information on which units are connected to which other units. To investigate the World Wide Web with this approach, one would neglect the content, the owner, the time of creation, and the number of downloads of a web page. Instead, we would only consider individual web pages and how they are linked together. The second step is to apply network science methods to find important nodes or clusters of nodes with some special role or function or study how the network’s wiring controls some dynamical system. The fundamental idea of this book is that one can learn more about a system if one does not, at the first step of simplification, discard information about when things happen. Consequently, one needs to modify the second step and develop a science of temporal networks that exploits this additional information.

Fig. 1.1
figure 1

A schematic map of the chapters of this book, positioned with respect to the three main research themes within the study of temporal networks

Full size image

The fundamental idea of retaining information about time is evidently not a hard one to get. Temporal networks have been invented and reinvented many times. Researchers have proposed many mathematical and computational frameworks—some equivalent, some not. This is probably inevitable for such an extraordinarily interdisciplinary field of science—temporal networks have been applied to neuroscience, transportation problems (Kujala et al. 2018), criminology (Schaub et al. 2023), social theory (Brudner and White 1997), control theory (Li et al. 2017), ecology (Ushio et al. 2018), and many more areas. The many existing frameworks could be frustrating for a newcomer to temporal networks. Part of our idea with this book was to showcase this diversity; see Chaps. 3, 5, and 15 for very different ways of thinking about networks in time.

Even if you encounter a problem where both the network and the temporal aspects should play a role, there is no general recipe to follow. This introductory chapter aims to provide a rough map of the field–what types of questions researchers have been interested in and what results are out there. We will also try to place the subsequent chapters in their correct locations on this map (Fig. 1.1). This chapter is not a catalog of techniques or an introduction to a comprehensive and self-consistent theory. For readers interested in that, our review papers Holme and Saramäki (2012), Holme (2015) the book by Masuda and Lambiotte (2016) or by Batagelj et al. (2014) will be a better read.

1.2 Temporal Network Data

This section discusses the many subtleties of how to represent a system as a temporal network in a meaningful way.

1.2.1 Events

The fundamental building blocks of temporal networks are events (or contacts, links, or dynamic links). These represent units of interaction between a pair of nodes at specified times. Often, they take the form of triples (i, j, t) showing that nodes i and j are in contact at time t. Sometimes, the time can be an interval rather than just a moment.

As we will see throughout this book, temporal network modeling is far from a straightforward generalization of static networks—often, it is fundamentally different. As a first example, we note that events are not always a straightforward generalization of the static networks’ links. Take email communication as an example. In static network modeling, one typically assumes that the links (between people who have exchanged emails) indicate social relationships (Williams et al. 2022). These links can be viewed as the underlying infrastructure for e.g. information spreading since people who know each other exchange information. The links are there not only for one e-mail to be sent but represent persistent opportunities for spreading events for the duration of the relationship. In contrast, an event in a temporal e-mail network is simply one e-mail being sent. This usually happens for the explicit purpose of spreading information. But there are also systems other than e-mail communication where events are more like links of static networks. Consider, for example, transportation systems where bus, train, or flight connections are really opportunities to travel that happen whether or not a certain person needs to use them. As we will see, different approaches treat these two interpretations of events differently.

1.2.2 Boundaries

In the natural sciences, we can sometimes model time as a dimension, if not exactly like space, then at least similar to it. For temporal networks, the binary connections and the time are more fundamentally different concepts. The simplest way of seeing this is to consider the network’s boundaries (between what is contained in a data set and what is not). Regarding time, a temporal network data set almost always covers a time interval, and the interval is the same for all nodes. The structural boundaries of the network dimension are usually less controlled. Like cohort studies in the social sciences, one would like to select nodes that are as tight-knit as possible, typically defined by common features. For example, Stopczynski et al. (2014) is based on data from voluntary participants among the freshmen of a university—better than a random group of people but worse than the complete group of freshmen.

Boundaries become a problem when one wants to control the size of a data set. If a temporal network is too large to handle or one wants to understand the effects of size, how should one reduce its size without changing its structure? One could reduce the number of nodes by random subsampling or truncating the sampling time. However, both these approaches would introduce biases. While there are ways to correct some of those Kivelä and Porter (2015), it is difficult to avoid problems. For example, if one truncates the data, there might not be enough time for a spreading process to saturate before the sampling interval is over. If one deletes nodes or events, one introduces other biases. The proper way of resampling a temporal network must simultaneously vary the number of nodes and the sampling duration, but exactly how is still an open question.

1.2.3 Connectivity

It is fundamental to network modeling that being indirectly connected through a path is relevant to dynamic processes. This is true for temporal networks as well, but the connections have to happen along time-respecting paths of contacts (with strictly increasing timestamps). Indirect connections through time-respecting paths are not transitive (see Fig. 1.2)—even if one can get from A to B and from B to C, it might still be impossible to go from A to C because one would arrive at B too late for a further connection to be possible. Contrary to this, all static networks, directed networks included, are transitive.

Fig. 1.2
figure 2

An illustration of two ways to visualize small temporal networks that can be convenient for reasoning about measures and methods. Panel a shows a timeline graph where an epidemic outbreak that starts at node A is indicated by gray lines. In almost all cases, paths between nodes (which follow events) in temporal networks must go forward in time (to the right in the plot). b Shows the same data but plotted projected onto a static graph. The latter visualization highlights the underlying static network structure at the expense of the temporal information. The former, the time-line plot can capture many temporal structures but is inconvenient for network structures

Full size image
Fig. 1.3
figure 3

A time-node representation of the data in Fig. 1.2. This is a (directed, acyclic) static graph containing the same information as in Fig. 1.2, but the meaning of nodes and edges is different

Full size image

Another important difference to static networks is that connectivity is temporal: even if there is a path from A to B now, whether direct or indirect, there might be none a second later. Therefore, the statement “A is connected to B” is not necessarily even meaningful unless the time (interval) of this connection is specified. The above issues mean that one can never reduce a temporal network to a static one without losing information or changing the meaning of the nodes (cf. Fig. 1.3).

Since many static network tools are based on paths and distances, researchers have sought to generalize these concepts to static networks. Once again, the addition of a temporal dimension makes this task much more complicated. The most common generalization of distance is latency (temporal distance) Lamport (1978)—the time it would take to reach j from i starting at time t and following only time-respecting paths. For a longer discussion of paths and connectivity, see Masuda and Lambiotte (2016), Holme and Saramäki (2012), Holme (2015).

1.3 Simplifying and Coarse-Graining Temporal Networks

Even if representing data as a temporal network means that information has to be discarded for simplification, this is often not enough to understand the large-scale organization of the system. There are many ideas on how to simplify further a temporal network that we will discuss in this section.

1.3.1 Projections to Static Networks

Perhaps the most obvious way of simplifying a temporal network is to turn it into a static network. In fact, many classic examples of static networks, such as citation networks or affiliation studies (like the “Southern Women” study of 1941 Davis et al. 1941), have temporal link information. Still, the time is ignored simply by studying the network of all aggregated contacts or separate “snapshot” graphs representing different times.

If one, from time-stamped data, constructs a binary static network where nodes are only linked or not, it is obvious that a lot of information is lost. A better option is to include information on the number or frequency of connections between pairs of nodes, leading to weighted networks. In this case, the link weights can provide important insights into the network structure (see, e.g., Barrat et al. 2004; Onnela et al. 2007). However, including links between all nodes that have been in contact can, in some cases, result in a very dense network. In this case, one can threshold the network, discard the weakest links, or extract the backbone of the network Serrano et al. (2009).

The above weighted-network approach is not really temporal because if one manipulates the times of the contacts, the outcome will remain the same. The simplest static networks that truly encode some temporal effects are reachability graphs. These graphs have a directed edge (i, j) if one can reach j from i via a time-respecting path.

Another way of creating sparser static networks than thresholding weighted graphs is to aggregate contacts within a time window (Krings et al. 2012b). While the thresholded graphs contain information about the most common contacts in the whole sampling interval, time-window graphs emphasize shorter time scales (Krings et al. 2012a), and their sequence captures at least part of the network dynamics. Indeed, tuning the duration of the time windows can be a way of understanding the organization of the data (Sekara et al. 2016). Yet a similar idea is to construct networks where links represent ongoing relationships (Holme 2003)—pairs of nodes that, at some point in time, have had contacts before and will have them again.

One more elaborate way of reducing temporal networks to static ones is the extraction of backbones, specifically concerning spreading processes on temporal networks (Zhan et al. 2019) and Chap. 11. By this approach, links in the resultant network correspond to node pairs that are likely to infect each other in an epidemic outbreak.

As mentioned above, these approaches can never retain all temporal features of the original data. Nevertheless, analyzing temporal networks by making them static is rather attractive because there are a plethora of methods for static network analysis. One way of circumventing information loss is to use more elaborate mappings, where temporal networks are mapped onto static network structures whose nodes and links represent something else than the original network’s nodes and links. One example is temporal event graphs, whose nodes correspond to the original network’s events (see Mellor 2018; Kivelä et al. 2018 and Chap. 6 of this book).

One common approach that can also be interpreted as static-network projection is to use multilayer networks, as in Chap. 17 of this book: time is sliced into consequent intervals, and the layers of a multilayer network correspond to networks aggregated for each interval. Once the layers are coupled (e.g. with a directed link from a node to its future self), one can then apply (static) multilayer network methods to the system. Importantly, the layers in such a projection are ordered by time.

Finally, we can also project temporal network data to higher-order network models that retain some information about the flows over the network. Chapter 4 discusses such approaches.

1.3.2 Separating the Dynamics of Contacts, Links, and Nodes

Instead of reducing temporal network data to static networks, one can retain some but not all of the temporal features. One example is the statistics of times between contacts. It was early recognized that often, the times between events, both for nodes and links, have heavy-tailed distributions (Holme 2003; Johansen 2004) (they are bursty Barabási 2005; Karsai et al. 2018). Subsequent studies (e.g. Karsai et al. 2011; Miritello et al. 2011) found that this burstiness of inter-event times slows down spreading processes: simulated spreading that takes place on bursty networks is slower than it is on networks where the burstiness has been artificially removed. However, the result is the same when the heavy-tailed inter-event times are part of the dynamical process itself: when a spreading process with power-law distributed waiting times is placed on a static network (Min et al. 2011), it is slow, too. This is related to how events are interpreted (see Sect. 1.2.1 and Chap. 12): are they separated from the process and just passive conduits for it, as in spreading on top of bursty event sequences, or are the events actively generated by the process, as one could interpret the combination of spreading with broad waiting times and a static network? Fig. 1.4a, b illustrate homogeneous and heterogeneous (bursty) link dynamics on top of a static network. See also Chap. 9, which goes deeper into this issue. Note that under some conditions, burstiness may also speed up spreading (Rocha et al. 2011; Horváth and Kertész 2014).

Fig. 1.4
figure 4

Three scenarios of temporal edge structure. The figures show the timelines of contacts along edges in a four-node graph. Panel a shows a scenario with narrow distributed inter-event times; b shows bursty edge dynamics; c shows a scenario with a turnover of edges—where the time between the beginning of the sampling to the first contact, or from the last contact to the end of the sampling, is too long to be explained by the interevent time distributions

Full size image

Another way of simplifying temporal networks is to ignore contact dynamics and think of links as present between the first and last observations of a contact in the data and ignore the precise timing of contacts (Holme and Liljeros 2014). Compared to simplifying the system as a bursty dynamics on top of static networks, this picture emphasizes longer time structures, such as the general growth and decline of activity in the data. Figure 1.4c illustrates a data set that is well-modeled by links appearing and disappearing, disregarding the interevent time statistics.

1.3.3 Mesoscopic Structures

In science, in general, “mesoscopic” refers to the scales between macroscopic and microscopic. In network science, this would mean structures larger than nodes but smaller than the entire network, and indeed, the term is often used in the context of grouping nodes into classes based on how they are connected to each other and the rest of the network. The primary example of mesoscopic structures is the community structure—some networks have clear groups that are strongly connected within and weakly connected between each other (Schaub et al. 2017).

Most community detection methods in static networks divide the network so that every node belongs to one group only (Chaps. 10 and 20). The straightforward extension of this idea to temporal networks would be to let nodes belong to different groups at different times but only to a single group at each point in time Rossetti and Cazabet (2018). This is also the most common assumption in the literature. See e.g. Rosvall et al. (2014), Palla et al. (2007), Mucha et al. (2010). This view focuses on the individual nodes and seeks to group them in some principled way. If one, on the other hand, focuses on the communities instead of the nodes and prioritizes definitions that give interpretable communities (one temporal-network community could, for example, represent one seminar, one concert, etc.), it makes sense not to require every node to be a member of a group at every point in time (Sekara et al. 2016), as in Chap. 2.

Other mesoscopic structures, such as core-periphery structures (Rombach et al. 2014), have been less studied for temporal networks (even though there are some works—e.g. Rico-Gray et al. 2012 use core-periphery analysis to understand ant-plant networks). Finally, temporally connected components (see Chap. 6 and Kivelä et al. 2018) span the structural scale from mesoscopic to macroscopic, both in terms of network structure and with respect to time.

1.3.4 Fundamental Structures

Chapter 2 and Sekara et al. (2016), Lehmann et al. discuss the traces that the six fundamental interaction types leave on temporal networks. Chapter 2 presents a division of the interaction types in the configuration of participants (one-to-one, one-to-many and many-to-many) and synchronicity (synchronous and asynchronous). In the limit of a short time interval projection of a temporal network data set, these different communication events contribute with different subgraphs—synchronous one-to-many communication yields a star graph, and synchronous many-to-many communication yields a clique. By tuning the time window, one can identify the time scales of influence of these “fundamental structures”.

1.4 Important Nodes, Links, and Events

Perhaps the most common question for static networks is to find important nodes (where “important” should be interpreted in an inclusive sense). This question is just as relevant for temporal networks. This is perhaps the topic where the approaches borrowed from the static-network toolbox are most applicable to temporal networks. One major difference is that it is meaningful to talk about the importance of contacts (in addition to nodes and links) for temporal networks (Takaguchi et al. 2012). Another difference is that the most principled, general measures of importance are time-dependent simply because, in most contexts, a node can become more or less important in time.

1.4.1 Generalizing Centrality Measures

A huge number of papers have been devoted to the generalization of classical centrality measures to temporal networks. See Pan and Saramäki (2011), Taylor et al. (2017) and Chaps. 8 and 17. In many cases—for distance-based centrality measures—they have taken the obvious approach of replacing distances with latency. Since temporal networks are typically less connected (in the sense that the fraction of nodes that are reachable through time-respecting paths is smaller than the corresponding quantity in static networks), centrality measures have to work in fragmented networks. This means that one needs to combine information about how many nodes can be reached with information on how easily they can be reached (or whatever rationale the corresponding static centrality measure has). An example would be to generalize closeness centrality by averaging reciprocal latencies rather than taking the inverse of the averages (Tang et al. 2013). This is, however, an arbitrary combination of two aspects of centrality and quite typical for straightforward generalizations of static concepts to temporal networks—they become less principled than their static counterparts.

1.4.2 Controllability

The rationales of centrality measures come from reasoning about dynamic systems—you can reach other nodes quickly from central nodes; central nodes are in the middle of heavy traffic, etc. The purpose of measuring centrality is typically to rank the nodes and perhaps to list the most central ones. Finding control nodes involves slightly different thinking. Instead of ranking the nodes, the control nodes are minimal sets of nodes needed to be manipulated for the entire network to reach a certain state.  Li et al. (2017) and subsequent works show that temporal networks can facilitate controllability—i.e. the system can be controlled with less energy and by fewer nodes, if it has temporal heterogeneities.

1.4.3 Vaccination, Sentinel Surveillance, and Influence Maximization

The problems of vaccination, sentinel surveillance, and influence maximization are related to questions about spreading phenomena. Similarly to controllability, one assumes some objective and some intervention to the underlying temporal-network structure. In this case, however, the objective is typically to minimize or maximize the number of nodes reached by some spreading dynamics (like an infectious disease, word-of-mouth marketing, etc.).

The vaccination problem is to select nodes that would minimize or slow down disease spreading as much as possible. Typically, one assumes that the vaccinated nodes are deleted from the system so that they can no longer become infected and spread the disease. Unlike centrality measures, but similar to controllability, it usually makes no sense to talk about the importance of individual nodes for the vaccination procedure—vaccinating one or a few nodes in a large network would have no measurable effect on the epidemics. Instead, the importance of the nodes comes from the membership of a group that is vaccinated (Gu et al. 2017). Another important point is that one can typically not assume knowledge about the entire network of contacts—only the interactions that individuals could reliably report can serve as input for vaccination protocols. For example, Génois et al. (2015), Starnini et al. (2013) propose vaccination protocols that exploit temporal structures.

The influence maximization problem deals with finding seed nodes for spreading dynamics that maximize the number of reached nodes (Kempe et al. 2003). The prime application is viral marketing, but to protect against outbreaks that have not yet entered a population influence maximization is also interesting for network epidemiology. The nodes that are important for vaccination and influence maximization do not necessarily have to be the same—optimal node sets for vaccination typically fragment the network efficiently. In contrast, influence maximization emphasizes efficiently splitting the network into subnetworks of influence. The first problem is akin to network attack or network dismantling (Braunstein et al. 2016), and the second is to find a vertex cover (Dinur and Safra 2005). To exploit temporal structures, one can identify nodes in a heightened state of activity or nodes that reliably influence others (Chap. 18).

Sentinel surveillance assumes that one can put sensors (sentinels) on the nodes. The task is to choose the sensors’ locations so that disease outbreaks are discovered as reliably or quickly as possible. This is probably the least studied of these three problems on temporal networks—we are only aware of Bai et al. (2017). On the other hand, it is practically a more important problem, since it is currently used in health care systems (Arita et al. 2004). Bai et al. (2017) tests how efficient temporal network protocols originally developed for vaccination are for the problem of sentinel surveillance.

1.4.4 Robustness to Failure and Attack

A problem that is very much overlapping with influence maximization, etc., is network robustness. The scenario is that some adversary is trying to destroy a network. This adversary can have different amounts of information or resources to carry out the attack, which yields different versions of the problem. With no information about the network, the problem reduces to node percolation (or robustness to failure). With perfect information but limited computational resources, the problem is equivalent to network dismantling. It is both interesting to study optimal heuristics for this problem and what network structures contribute to the robustness of a network. For temporal networks, Trajanovski et al. (2012), Scellato et al. (2013) studied this problem. Still, there should be several ways of extending their work, and in general, temporal-network robustness seems to be an understudied area. This may have to do with the fact that the temporal dimension makes the whole percolation framework more complicated (see Chap. 6).

1.5 How Structure Affects Dynamics

For disease-spreading models, heterogeneous, heavy-tailed degree distributions are known to speed up the dynamics Barthélemy et al. (2004). One line of research in temporal network studies is to identify similar relations between the structure of the data and dynamics taking place over the contacts.

The types of dynamics people have been studying on underlying temporal networks include disease spreading of different kinds (Chaps. 7, 11, 13, 14 and 16) Fefferman and Ng (2007), threshold models of complex contagion (Takaguchi et al. 2013; Backlund et al. 2014), random walks (Chap. 12) (Starnini et al. 2012; Delvenne et al. 2015; Masuda and Lambiotte 2016; Saramäki and Holme 2015), navigation processes (Lee and Holme 2019), synchronization (Chap. 15) and even game-theoretic models (Cho and Gao 2016; Zhang et al. 2019).

1.5.1 Simulating Disease Spreading

Disease spreading typically follows standard compartmental models developed by applied mathematicians (Hethcote 2000; Britton 2010). Such models divide a population into classes with respect to the disease and then state transition rules between the classes. The key transition rule in all compartmental models is the contagion event where a susceptible individual becomes infected when in contact with an infectious individual. In the two canonical and most well-studied models—the SIS (susceptible–infectious–susceptible) and SIR (susceptible–infectious–recovered) models—the contagion event is paired with the recovery of individuals (in SIS, recovered individuals become susceptible again, whereas in SIR they become immune to the disease or die). The probability that a contact between a susceptible individual and an infectious individual results in contagion is usually a model parameter. It is assumed to be the same for all contacts (which is an assumption for convenience and not realism).

Many assumptions are needed to simulate a compartmental model on a temporal network of contacts (Masuda and Holme 2015; Enright and Kao 2018). Unless modeling bioterrorism or the spread of something other than a disease makes no sense to select more than one seed. Without prior knowledge about the disease’s entry into the population, one should choose this seed uniformly at random. By the same principle, one should choose the time of infection uniformly randomly as well. This could, of course, lead to the outbreak not being able to reach all nodes so that the measured outbreak sizes are an average of outbreak sizes of different times. For this reason, some authors choose to start the outbreak early in the interval covered by their data, although this introduces a bias if e.g. the activity in the data grows Rocha and Blondel (2013). Another commonly used approach is to use periodic boundary conditions and repeat the data from the beginning (e.g., in Karsai et al. 2011).

Another important consideration is the duration of the infectious period. In the mathematical epidemiology literature, it is usually assumed to be exponentially distributed to achieve the Markov property (that the probability of recovering is independent of the time since the infection). Markovian SIR and SIS are not only easier to analyze analytically, but also allow for some tricks to speed up simulation code (see www.github.com/pholme for fast, event-driven code for the Markovian SIR on temporal networks). Some studies use a constant duration of infection for all nodes. To the best of our knowledge, no studies have tried duration distributions inferred from data.

Another decision that anyone simulating disease spreading (or random walks) on temporal networks needs to make is what to do with contacts happening in the same time step. There are, as we see it, two principled solutions. Either one assumes that this is allowed, in which case one then needs to pick contacts with the same timestamp in random order and average over different randomizations, or one assumes that the disease cannot spread via an intermediate node in a single time step. This is effectively to assume an SEIS or SEIR model (E stands for exposed, which means that the individual will become infectious in the future but is not yet infectious), with the duration of the E state being less than the time resolution of the temporal network.

Another slight difference in approaches, especially in studies where a model generates the underlying temporal network, is that of link-centric and node-centric compartmental models. In node-centric models (Masuda and Rocha 2018; Jo et al. 2014), the time to the next contact that could spread the disease is determined at a contagion event. In link-centric models (Vazquez et al. 2007; Horváth and Kertész 2014) the contacts are generated independently of the propagation of the disease. The node-centric model simplifies analytical calculations, whereas the link-centric model is conceptually simpler and perhaps more realistic (even though the assumption that the contact dynamics are independent of what spreads on the network is probably often invalid).

Typically, papers about disease spreading have focused on understanding how network structure affects the final outbreak size (Min et al. 2011; Holme and Liljeros 2014; Masuda and Holme 2015). Some, however, have studied early outbreak characteristics such as the basic reproductive number \(R_0\) (the expected number of others an infectious individual would infect in a completely susceptible population) Liu et al. (2014), Rocha and Blondel (2013). From a medical perspective, there is no obvious choice between these two—even though the societal concern is to minimize the outbreak size. The outbreak size is also a consequence of interventions not modeled by canonical disease-spreading models such as SIS and SIR. Thus the early phase of the disease, which is better summarized by \(R_0\), could be more informative.

Random walk studies have focused on the mean-first passage time—the expected time since the beginning of a walk that the walker reaches a node—and reachability—the probability that a node is reached by a walker starting at a random node (Masuda and Lambiotte 2016; Saramäki and Holme 2015). Another topic of interest has been how the topological and temporal structures affect the speed of diffusion (Delvenne et al. 2015). As opposed to the spreading of disease, there is no directly obvious real-world phenomenon that would be well-modeled by random walks on temporal networks; however, random walks equal diffusion, and diffusion can be considered a fundamental process in any system. Often, the random walk process is simply used as a probe of the temporal network structure.

1.5.2 Tuning Temporal Network Structure by Randomization

The most straightforward way of understanding the impact of temporal network structure on dynamic processes is, of course, to tune it and monitor the response on some quantity describing the dynamics. There were important contributions (also involving temporal structures) in this direction even before the turn-of-the-millennium network boom. For example, Morris and Kretzschmar studied the effect of concurrency, or overlapping relations, on outbreak sizes (Morris and Kretzschmar 1995).

The most common way to investigate the effect of structures on a temporal network is to use randomization schemes. This approach starts with empirical networks and then destroys some specific correlation by randomizing it away. For example, one can randomly swap the timestamps of contacts or replace the timestamps with a random timestamp chosen uniformly between the first and last of the original data (Holme 2005). The former randomization is more restrictive because it preserves the overall activity pattern and per-node and per-link inter-event time statistics (see Fig. 1.5). Randomization schemes turn out to be much more versatile for temporal networks than for static ones. Gauvin et al. (2018) gives a comprehensive theory of almost 40 different randomization schemes. By applying increasingly restrictive methods to real data sets, one can see how much structure is needed to recreate the original temporal network’s behavior.

In general, the terminology of temporal networks is ambiguous. The topic itself sometimes goes by the names “dynamic networks”, “temporal graphs”, or “time-varying networks”. The randomization schemes above are no exception—Holme (2005) calls the scheme of Fig. 1.5b “permuted times”, Karsai et al. (2011) calls it “shuffled times” and Gauvin et al. (2018) calls it “shuffled timetamps”.

Fig. 1.5
figure 5

Illustrating two types of randomization procedures. Panel a shows a temporal network that is randomized by randomly swapping time stamps (b) and replacing timestamps with random ones (c). The randomization in b preserves both the number of contacts per time (the numbers above) and the number of contacts per pair of nodes (the numbers to the right). The randomization procedure of panel c preserves the number of contacts per pair of nodes but not the number of contacts per time

Full size image

1.5.3 Models of Temporal Networks

Another way of tuning temporal network structure, other than randomization, is by generative models. Generative models of temporal networks serve a different role than static networks. Static network science traditionally used network evolution models as proof-of-concept models for theories about emergent properties, like power-law degree distributions (Barabási and Albert 1999) or community structure (Grönlund and Holme 2004). There are common structures for temporal networks combining temporal and network structures in a nontrivial way that is nontrivial to explain. Nevertheless, temporal network models are needed, if for nothing else than to generate underlying data sets for controlled experimentation (Presigny et al. 2021). In this section, we will mention some of the central developments in this area. For a complete overview, see  Holme (2015).

The most straightforward approach to generating a temporal network is to generate a static network and assign a sequence of contacts to every link. For example, Holme (2013) uses the following procedure:

  1. 1.

    Construct a simple graph by first generating an instance of the configuration model (Newman 2010) and merging multiple links and self-links from it.

  2. 2.

    For every link, randomly generate an interval when contacts can happen.

  3. 3.

    Generate a sequence of contacts following an interevent time distribution.

  4. 4.

    Match the time sequence of contacts to the active intervals of the links.

This model is illustrated in Fig. 1.6.

Fig. 1.6
figure 6

Illustrating a simple generative model for temporal networks, used in Holme (2013) and Rocha and Blondel (2013). First, one generates a static network from the configuration model by creating desired degrees from a probability distribution (a) and matching them up in random pairs (b). Then, one generates intervals for the links showing when they are active (c). Finally, one generates a time series of interevent times (d) and matches it to the active intervals. This figure is adapted from Holme (2015)

Full size image

Perra et al. (2014) proposed a model of temporal networks—the activity driven model—that is even simpler than the above with the advantage that it is analytically tractable. Let \(G_t\) denote a simple graph at time t. Their generation algorithm proceeds as follows:

  1. 1.

    Increment the time to t and let \(G_t\) be empty.

  2. 2.

    Activate a node i with probability \(a_i\varDelta t\). Connect i to m other randomly chosen distinct nodes.

This model has been fundamental to analytical studies of processes on temporal networks; see e.g. Perra et al. (2012), Karsai et al. (2014), Liu et al. ( 2013, 2014), Starnini and Pastor-Satorras (2014), Sun et al. (2015), Han et al. (2015).

Starnini et al. (2013) use a two-dimensional random walk model where the chance of approaching node i is proportional to an increasing attractiveness parameter \(a_i\). This means that the more attracted a walker is to its neighbors, the slower its walk becomes (simulating acquaintances stopping to talk when they meet on the street). Furthermore, they also allow people not to socialize by having occasional inactive periods. Zhang et al. (2015) propose a similar model without an explicit representation of space.

Another model of temporal networks of social contacts was proposed in Vestergaard et al. (2014). The authors introduced a model in which temporal effects activate nodes and links. In their model, a link can be active or inactive and further characterized by the time \(\tau _{(i,j)}\) since the last time it changed state. Similarly, node i uses the time \(\tau _i\) since it was last involved in a contact as a basis for its decisions. The network is initialized to N nodes, and all links are inactive. A node can activate a link with probability depending on \(\tau \). The link is chosen from the nodes i that are currently not in contact with i with a probability depending on the \(\tau \)s of the neighbors. An active link is inactivated with a rate that is also dependent on \(\tau \).

 Masuda et al. (2013) and Cho et al. (2014) use a Hawkes process to model a similar situation to the one considered by Starnini et al. (2013) above.  Masuda et al. (2013) argues that there is a positive correlation between consecutive interevent times in empirical data that one cannot model by interevent times alone. Their model works by defining an event rate by

$$\begin{aligned} v+\sum _{i:t_i\le t}\varphi (t-t_i) \end{aligned}$$
(1.1)

where \(\phi \) is an exponentially decreasing memory kernel, and v is a base event rate. Even with an exponentially decaying kernel, the interevent time distribution becomes broader than exponential. Similar to  Masuda et al. (2013) and Cho et al. (2014), Colman and Vukadinović Greetham (2015) introduced a model of temporal networks based on stochastic point processes. In their model, the nodes form and break links following a Bernoulli process with memory. Like the Hawkes process mentioned above, the probability of an event between i and j increases with the number of recent events between i and j. Specifically, Colman and Vukadinović Greetham (2015) takes the probability that a link is activated or deactivated at time t to be proportional to the number of such events in a time window.

1.6 Other Topics

There are, of course, some themes in the temporal network literature that do not fit into the above three categories. Two examples are generalizations of link prediction (Liben-Nowell and Kleinberg 2007) and network reconstruction (Newman 2018; Peixoto 2019) to temporal networks. The motivation for both these topics is that real data is often erroneous and incomplete. In static networks, link prediction refers to the problem of finding the linkless pair of nodes that is most likely to be a false negative (falsely not having a link). In the context of temporal networks, this could be reformulated as either the question of what will be the next contact (given the information up to a point) or of which contact was missing in the past. We are not aware of any paper addressing these particular problems. Instead of solving these purely temporal network questions, there is a large body of literature on link prediction in static networks with a turnover of nodes and links—see e.g. Ahmed and Chen (2016) and references therein—i.e., assuming a slower changing network than elsewhere in this chapter.

Network reconstruction, in general, is the problem of inferring a network from secondary, incomplete, or noisy data (Newman 2018; Peixoto 2019). So far, we are unaware of such temporal network studies similar to the static network case. There are papers about the technical difficulties of inferring temporal network contacts from electronic sensors (Stopczynski et al. 2014; Barrat and Cattuto 2013) and papers about how to reconstruct static networks from temporal network data (Krings et al. 2012b; Holme 2013), but we are aware of no papers that would predict false positive and negative data in a contact sequence.

1.7 Future Perspectives

Temporal network studies have been a vivid subdiscipline of network science for around a decade. Some issues of the early days have been settled, while others remain. This period has seen a shift from research that simply extends static network ideas to temporal networks to methods that are unique to temporal networks. Still, the overall research directions are more or less the same as for static networks (cf. Fig. 1.1)—questions about identifying important nodes, how to simplify temporal networks further, and how their structure affects dynamics. Are there such larger research directions that make sense for temporal networks but not static ones? An obvious idea would be to focus on questions that involve time more directly. Researchers rarely asked what the optimal time to do something is, or the optimal duration to expose the system to some treatment, etc. Change-point detection (finding the time when a system changes between qualitatively different states) is one exception (Peel and Clauset 2015). There are also papers about time series analysis of temporal networks (Sikdar et al. 2016; Huang et al. 2017), but these typically do not ask questions about time like the ones above.

Perhaps the crudest assumption of temporal network modeling to date (as mentioned in Sect. 1.2.1) is that the existence of a contact is independent of the dynamic system of interest. As an example, there are many modeling studies of information spreading on top of empirical temporal networks (e.g. mobile-phone or e-mail data Karsai et al. 2011; Karimi and Holme 2013; Backlund et al. 2014). Of course, information spreading via email or calls does actually happen. Still, one cannot usually view it as a random process on top of some temporal contact structure independent of the information. While one can imagine less important information spreading this way—“By the way, put on that Finnish heavy metal when uncle Fredrik comes to visit, he will appreciate it”—usually, calls are made, and e-mails are sent with the explicit purpose of spreading information. Therefore, information spreading influences or even drives the contact structure. How should one then model information spreading on temporal networks? One possibility would be to give up using empirical data as the basis for the analysis; such an approach would be similar to adaptive networks (Gross and Sayama 2009). One could also go for data that contain the content of the messages or conversations instead of only their metadata; in this case, it might be possible to understand the relationship between contacts’ temporal network and the spreading dynamics. Evidently, such data is hard to come by for privacy reasons, but interestingly, early studies of electronic communications did analyze both the content and the structure of spreading (Danowski and Edison-Swift 1985). There are also communication channels where everything is public, such as Twitter.

One research direction with plenty of room for improvement is temporal-network visualization. Figure 1.2 illustrates some of the challenges where Fig. 1.2a gives a reasonable feeling for the temporal structures but none for the network structure, and for Fig. 1.2b, the situation is reversed. One can probably rule out a type of visualization that manages to show all information and convey all different aspects of the structure. However, there should be methods that discard some information but still reveal important structures. Also, animated visualization (which has the obvious limitation that not all the information is shown at once) probably has room for improvement. Some such methods are discussed in Chap. 5. The “alluvial diagrams” of Rosvall and Bergstrom (2010) are another interesting approach. Evidently, there are some available methods, but we wish for an even wider selection to choose from.

Yet another fundamental challenge for temporal networks is how to rescale or subsample a data set properly. In particular, many methods inspired by statistical physics rely on ways to change the size of a network consistently. This is a challenge even for static networks—simply making subgraphs based on a random set of nodes will most likely change the structure of a network (other than Erdős-Rényi random graphs) Lee et al. (2006). The same applies to more elaborate ways to reduce the network size by merging nodes (Kim 2004; Song et al. 2006)—there is no guarantee that such manipulation will retain the structure of networks. For temporal networks, one might think that at least the temporal dimension could be rescaled by sampling windows of different sizes, but this is not trivial either because it could change whether or not a dynamic process has the time to reach a certain state or not. For finite-size scaling, such as used in the study of critical phenomena (Hong et al. 2007), one would need a way to link the size of the network and the duration of the temporal network.

Finally, as mentioned earlier in this chapter, we feel that there is much to do regarding temporal-network robustness and fragility, with applications ranging from network security to public health and the efficient planning of robust public-transport systems. This is an area where it is possible to go beyond static network analogies. For example, while a static network may fragment when chosen nodes are attacked/immunized, the range of temporal-network responses is much broader. The network may remain temporally connected in principle, but the average latency of time-respecting paths may grow high enough to make them useless. Or, the system’s latency could temporarily grow to make it temporarily disconnected: consider, e.g., congestion in a public transport system. Furthermore, the range of possible attack or immunization strategies can be much broader too: interventions to events, attacks that aim to increase latency generally, interventions at specific times, sequences of timed interventions at different nodes or contacts, and so on. Likewise, when the aim is to improve network robustness, interventions are not limited to network topology alone. For example, to improve the reliability of public transport systems, one could only modify the temporal sequences of connections and their time-domain statistics to minimize the disruption caused by random deviations from the planned schedules, or one could aim at maximal synchronization of connections to minimize the latency of time-respecting paths.