Report

The fundamental advantages of temporal networks

See allHide authors and affiliations

Science  24 Nov 2017:
Vol. 358, Issue 6366, pp. 1042-1046
DOI: 10.1126/science.aai7488

In network science, change is good

Historically, network science focused on static networks, in which nodes are connected by permanent links. However, in networked systems ranging from protein-protein interactions to social networks, links change. Although it might seem that permanent links would make it easier to control a system, Li et al. demonstrate that temporality has advantages in real and simulated networks. Temporal networks can be controlled more efficiently and require less energy than their static counterparts.

Science, this issue p. 1042

Abstract

Most networked systems of scientific interest are characterized by temporal links, meaning the network’s structure changes over time. Link temporality has been shown to hinder many dynamical processes, from information spreading to accessibility, by disrupting network paths. Considering the ubiquity of temporal networks in nature, we ask: Are there any advantages of the networks’ temporality? We use an analytical framework to show that temporal networks can, compared to their static counterparts, reach controllability faster, demand orders of magnitude less control energy, and have control trajectories, that are considerably more compact than those characterizing static networks. Thus, temporality ensures a degree of flexibility that would be unattainable in static networks, enhancing our ability to control them.

Traditionally, network science has focused on static networks, whose links offer permanent connections between their nodes. Yet, it is increasingly recognized that most natural and social systems are best described as “temporal” networks, with links existing only intermittently. For example, within metabolic networks (1), the links correspond to brief chemical reactions; in social networks (2, 3), friendship links are inferred from face-to-face or digital communications of short duration. Such temporality has profound effects on most dynamical processes taking place on networks (47), slowing down synchronization and the diffusion of innovative information (4), impeding exploration and navigation (7), and raising barriers to accessibility (5). Similar limitations are expected for control—the ability to drive a system with input signals to any desired final state in finite time. Control is essential for the operation of most real systems (814), yet controllability normally requires the existence of continuous paths capable of carrying the input signals to the rest of the network (1518). Whereas in static networks such signal-carrying paths are permanently available, in temporal systems, complete instantaneous paths between the inputs and the rest of the nodes are not guaranteed, potentially degrading our ability to control a system.

A temporal network is an ordered sequence of m = 1, , M separate networks on the same set of N nodes (Fig. 1, A and B), with each such “snapshot” m characterized by a (weighted) adjacency matrix Amfor a duration Δtm. As we aim to uncover the role of the changing network topology, rather than the effect of specific dynamics, we consider that, in each snapshot, the system is governed by the canonical linear time-invariant dynamics Embedded Image(1)valid over the time interval Embedded Image, where the Embedded Image is the “switching time” between snapshots m – 1 and m. We assume that the system spends a finite amount of time in each snapshot (1, 19), hence the Zeno phenomenon, or infinitely fast switching, is unlikely to occur in real temporal networks. The state vector Embedded Image captures the state of the whole system at time t, and xi(t) represents the state of node i, like the concentration of metabolite i within a cell. The input matrix Bm identifies the set of driver nodes through which we attempt to control the system using Embedded Imageindependent control inputs Embedded Image, like manipulating the input concentration of p metabolites. To avoid conferring an unfair advantage to temporal networks, we use the same set of driver nodes across all snapshots, i.e., Bm = B (Fig. 1C), and we assume that we have no control over the order of the snapshots nor over the timings of the topology changes, hence our influence on the system is confined to the control inputs (1517, 20, 21). Consequently, in this work we can regard temporal networks with dynamics described by Eq. 1 as switched linear systems (22) with specified switching sequences. If the switching sequence depends on the state vector x(t), the system can display strong nonlinear behavior, even if the dynamics (Eq. 1) within each snapshot is linear (22).

Fig. 1 Temporal versus static networks.

(A) The sequence of contacts among three nodes, capturing, for example, the connection patterns between three individuals. We draw a line between two nodes if they interact with each other during a 20 s interval. (B) The temporal networks constructed from the contact sequence shown in (A) depend on the length of the time window Δt over which we aggregate the interactions. For short Δt, we obtain a large number of disconnected networks (snapshots); for sufficiently large Δt, these collapse into a single static network. (C) Four snapshots of a temporal network, constructed from (A) for Δt = 40. According to Kalman’s rank condition (8), none of the snapshots are individually controllable from the top node. Yet, Eq. 3 predicts that the temporal network becomes controllable after the second snapshot. (D) A static network, obtained by aggregating the first two snapshots in (C), is uncontrollable from the top node, as the controllable space Ωs is two dimensional. This is illustrated by the yellow region on the right showing the set of all points xf that can be reached in finite time from a given initial state 0 with an appropriate u(t). (E) We must aggregate at least three (Ss = 3) for the corresponding static network to become controllable. (F) The first two snapshots of a temporal network (top) shown in (C) and the controllable space for each snapshot (bottom). In this case, the temporal network becomes controllable after St = 2 snapshots. In other words, an appropriate signal acting on the green node can send the system to an arbitrary point in the x1x2 plane; a subsequent temporal signal acting on the blue node can take the system to the desired x3 point in the space. Consequently, the controllable space of the temporal network is the full cube in the bottom right corner.

To understand why temporal networks are easier to control than static networks, consider the static three-node network of Fig. 1D, which is uncontrollable by any single driver node. Indeed, we can show that for almost all values of the link weights, we can only steer the static network within a two-dimensional subspace of the three-dimensional state space (Fig. 1D). Yet, we can also show that the temporal version of the same network—in which the two links are nonsimultaneously active—is controllable by the top node (Fig. 1F). This is because although each snapshot of the temporal network is by itself an uncontrollable system, they contribute independent two-dimensional controllable subspaces (Fig. 1F), meaning that by combining the two, we can reach any point within the full three-dimensional state space. This renders the system as a whole controllable.

Consider a system initially at x0 = 0. By considering all possible trajectories from the initial time t0 = 0 to the final time tf = tM , we can write the controllable space [see supplementary materials (SM) section S1.1] asEmbedded Image(2)Here, Embedded Image denotes the controllable space of snapshot m, where Embedded Image is the column space of B. Hence, a temporal network of N nodes is controllable if and only ifEmbedded Image(3)meaning that we can steer the system to an arbitrary state of the state space Embedded Image in finite time. For a static network, whose snapshots are identical (i.e., Am = A), Eq. 3 reduces to the classic Kalman’s rank condition for controllability (8).

According to Eq. 2, the controllable space will never shrink as the network structure changes, allowing us to determine the minimum number of snapshots St that must elapse before a temporal network becomes fully controllable. For comparison, we also calculate the minimum number of snapshots Ss for the corresponding controllable static network, which represents an aggregation of a temporal sequence of snapshots (SM section S4). Consider for example Fig. 1C, which shows a temporal network with four snapshots, none of which is individually controllable by using the top node as the sole driver node. According to Eq. 3, the temporal sequence becomes controllable at the second snapshot, i.e., St = 2 (Fig. 1F). By contrast, we must aggregate Ss = 3 snapshots to obtain a controllable static network (Fig. 1E). The difference between Ss and St captures the relative control benefits of a dense (but fixed) network topology versus a relatively sparse (but time-varying) topology, respectively. Although there is no theoretical guarantee that St is always less than Ss (fig. S1), as we show next, we find that real temporal networks reach controllability much faster than their static counterparts. Here “faster” refers to the number of snapshots we need to reach full controllability. Hence, the time to control (embodied in St and Ss) is distinct from tf, representing the time a system needs to reach its final state (8, 15, 2224).

To demonstrate the practical relevance of our finding, we explore an empirical communication data set collected by the SocioPatterns collaboration, capturing face-to-face conversations between the attendees of a conference (25); an ecological network, capturing antenna-body interactions between ants (26); a biological network with time-varying protein-protein binding interactions (27); and the real-time communication patterns observed in a technological network, extracted from observed data-packet exchanges within a mobile ad hoc network that emulates the true stationary communication activity of several mobile devices. For each data set, we condense interactions into snapshots over successive time windows of equal length Δt, a parameter that offers a measure of temporality: For small Δt, we obtain a large number of sparse, disjointed snapshots, whereas for large Δt, we approach a single snapshot corresponding to the full static network (Fig. 1, A and B). In this view, each snapshot represents the network structure over the full aggregation window Δt for the purposes of the dynamics (Eq. 1). Figure 2 shows St and Ss for different time windows Δt, indicating that the number of snapshots required to control a temporal network St is less than that required for its static counterpart, Ss. The smaller the Δt, the more pronounced the advantage of temporal networks. For example, for the face-to-face interactions at Δt = 103, the temporal networks reach controllability after only 71 time steps (19.72 hours), whereas we must aggregate 185 snapshots over two days to obtain a static network that is controllable. The difference between St and Ss is significant in all systems, obtaining P < 0.001 for face-to-face interactions, P < 0.05 for ants, P < 0.001 for the protein network, and P < 0.001 for the technological network.

Fig. 2 Faster paths to controllability in temporal networks.

Time needed to control four kinds of temporal networks: (A) 20,818 face-to-face interactions between the attendees of an ACM hypertext conference with 113 participants, recorded over 2.5 days in 2009 (25); (B) 1911 antenna-body interactions between 89 ants over 1438 s (26); (C) dynamic protein-protein interactions in the yeast Saccharomyces cerevisiae annotated by the three domains of gene ontology—cellular component (CC), molecular function (MF), and biological process (BP). The data consist of 22,570 protein-protein interactions between 84, 74, and 85 nodes, recorded within 33, 50, and 50 snapshots, respectively (SM section S2) (27); (D) data packet exchanges in an emulated mobile ad hoc network, capturing 304, 383, and 3287 interactions between 34 nodes (mobile devices) occurring over 50 snapshots each from three simulations, 1-ip6, 2-ip6, and 3-ip6 (SM section S2). For each time window Δt, St is the minimum number of snapshots required to achieve full control of a temporal network, and Ss is the minimum number of snapshots we must aggregate to obtain a controllable static network. We find that St < Ss for any Δt, both for the original sequence of snapshots and when the sequence of interactions is randomized, meaning that the result is not an artifact of the original data (see SM sections S3 and S4). For the significance test, we obtain ***P < 0.001 and **P < 0.05; Student’s t test. The weight of each link is set randomly between 0 and 1. The number of driver nodes is fixed to 20% of the network size, and each point represents an average over 103 realizations of link weights on the same network structure (temporal or static).

To determine to what extent these gains in controllability depend on the topology of the underlying snapshots, we calculate St and Ss for randomized versions of the empirical data, using null models that permute the overall network structure, the relative time orderings of the edges, or both (19). In all cases, we find that St < Ss (fig. S8), indicating that the observed advantage is independent of how the network changes in time. We also find that with increasing numbers of snapshots, temporal networks have more opportunities to reach full controllability than their static counterparts (fig. S9), a finding further validated by using a toy model that considers random switching sequences (SM section S4). Finally, we also explore whether the gains in controllability depend on the timing of the interactions between the nodes, specifically the interevent characteristics. For this, we randomly distribute time stamps for each interaction event (fig. S7), erasing the inherent burstiness (periods of intense activity separated by periods of relative quiescence) and other temporal correlations from the data (28), while leaving the number of interactions involving each node unchanged [(19), SM section S4]. We still find that St < Ss in all cases (fig. S13), indicating that the observed controllability gains are independent of the nature of temporal signal. The combined results, obtained by using real and synthetic data, indicate that temporality alone can considerably improve controllability.

It is well established that sparse and/or heterogeneous networks—common among real networks—face barriers to control, requiring many more driver nodes than dense or homogeneous networks. Our results indicate that natural and human-built systems can overcome this barrier by evolving or being engineered to be temporal. For example, systems like the Association for Computing Machinery (ACM) conference and the technological network, which show dramatic differences between Ss and St, can be steered to a large number of states within a short time window. Deviations from the strong link we observe between temporality and controllability are also informative. For instance, the slower growth of the controllable space and correspondingly modest gains in global controllability for the temporal ant-to-ant and protein-protein networks imply that the topology of these systems changes in ways that tend to revisit previous network structures and dynamics. As such, temporality, though present, offers less flexibility and may point to the importance of partial or “target” control in these systems (29). Taken together, we may be able to use the difference between Ss and St as a measure of the flexibility offered by temporality for a given system.

Our ability to control a system is determined not only by the time it takes to reach controllability but also by the amount of effort (energy) required to reach a particular final state. We develop a formalism to calculate the minimum input energy Embedded Image required to drive a temporal network from an initial state x0 to final state xf. For systems following (Eq. 1), we have (SM section S5)Embedded Image(4)where d is the difference vector between the desired final state xf and the natural final state that the system reaches without control inputs, and the N × N matrix Weff encodes the energy structure of the temporal network. For identical snapshots, Weff reduces to the controllability matrix and Eq. 4 provides the control energy of a static network (SM, section S5.4). Computing Weff scales in time as Embedded Image, where Nd is the number of driver nodes, and involves Embedded Image nearly noninvertible matrices, with orders-of-magnitude differences in their elements. Hence, the limiting factor in calculating (Eq. 4) are the number of nodes and snapshots, not the number of interactions. This places high demands on numerical precision and renders the control energy calculation challenging for large networks. We can, however, numerically determine the energy for the technological system (N = 34, M = 2), but not for the next larger system, the protein-interaction network (N = 74, M = 33). We therefore calculate the minimum control energy E for small synthetic networks and test the implications of our results in real systems using the technological network.

Figure 3 compares the control energy (Eq. 4) of a synthetic temporal network and the technological network with that of their static counterparts as a function of Δt. We find that the average control energy of a temporal network is many orders of magnitude smaller than that of the corresponding static network, particularly in the highly temporal regime (with very small Δt). Indeed, for Δt = 10–6, the energy difference between the static and temporal network exceeds 130 orders of magnitude (Fig. 3A). In other words, high temporality, corresponding to rapid changes in the network topology, offers remarkable energy savings. Applying this to a real system, we find that the energy required to control the technological network of Fig. 2D decreases by 274 orders of magnitude when the true temporal nature of the network is taken into account (Fig. 3B). In both temporal and static networks, we can reduce the control energy by using more driver nodes (24) (fig. S15). Yet the gap between the temporal and static network persists until all nodes are directly controlled (fig. S15). Finally, a direct comparison of the control energy distributions for static versus temporal networks reveals only a small overlap in certain regimes (Fig. 3, insets). This indicates that the worst-case control direction in a temporal network is often better than the best-case control direction in its static counterpart.

Fig. 3 Temporal networks require less control energy.

(A) Control energy for temporal and static networks. We consider a temporal network with two snapshots, each lasting Δt time. Embedded Image (solid line) is the average minimum energy over 104 randomly selected final states xf from a unit sphere centered on x0 = 0. The shaded area is enclosed by the minimum and maximum E obtained numerically. Embedded Image (dashed line) is the theoretical upper bound of Embedded Image (SM section S6). With increasing Δt, Embedded Image (and Embedded Image) decreases as Embedded Image, where γ is indicated with a black dashed line, before reaching a plateau. The fraction of driver nodes is 0.1, and increasing the number of driver nodes reduces the necessary control energy both for temporal and static networks, yet temporal networks continue to require less energy (see fig. S15 for the case of more driver nodes). Insets show the distribution of minimal energy for two specific Δt. The small overlap between temporal and static networks indicates that temporal networks are energetically preferable and that this is largely independent of the control direction (fig. S15). Here, a1 = –3, a2 = –1, N = 20. a1 and a2 are self-loop weights chosen to stabilize the standalone dynamics of each snapshot, and the average degree within each snapshot is 6 (see SM section S8 for details). (B) The distribution of E with one driver node for the technological network with Δt = 10–6 (see fig. S15 for more details).

In some systems, from social systems to biological ones, a full comparison of the control cost of temporal and static networks might require us to consider the costs necessary to switch the network structure in temporal networks, or conversely, the potential costs of maintaining the network structure in static networks. For example, it would take exceptional effort to force a regulatory network not to change in time. Lacking measurements and models to estimate these costs, we have neglected them here. Yet, given the truly exceptional control cost differences between static and temporal networks (Fig. 3), we note that these coordination costs would need to differ in many orders of magnitude to alter our fundamental conclusion that temporal networks typically require less control energy.

The extreme energy savings characterizing temporal networks arise because of the orders-of-magnitude difference in the energy required to move in different directions in the state space (24). In a static network, if we must travel in an energetically costly direction, we have no choice but to spend the required energy to “push” against the system’s dynamics. By contrast, in a temporal network, we can exploit the changing topology to avoid these expensive directions. Much like navigating a sailboat, it is easier to travel in a particular direction if we exploit the shifts in the wind direction (the vector field of the network dynamics): We raise the sails when the wind helps us and pull them back when it works against us. In other words, we only push toward the desired final state when the topology renders the energy cost acceptable, and pause when the topology makes the cost prohibitive.

The orders-of-magnitude decrease in control energy induced by temporality has implications for natural and human-built systems alike. Our calculations (Fig. 3) show that the key determinant of a temporal system’s energy advantage is the parameter Δt representing how long each snapshot is active. Systems in which the network’s structure evolves rapidly (relative to its intrinsic dynamics) can have huge savings in terms of the effort needed to control them. By contrast, if the network’s structure evolves slowly relative to its dynamics, then static and temporal networks require comparable control energy. Indeed, as shown in Fig. 3, for small Δt, temporal networks display a decided energy advantage; by contrast, for large Δt, the energy advantage of temporal networks is not obvious. The exact Δt value at which transition occurs depends on the number of driver nodes (Nd), as well as the details of the network’s structure such as its average degree and link strengths.

Real systems often obey constraints that forbid the states of the nodes from taking arbitrary values. For instance, the generator frequencies in the power grid can only vary within a narrow range around their normal operating point, without inducing failures, and metabolite concentrations (1) within a cell must always be nonnegative. These limitations mean that the control trajectories cannot wander arbitrarily far into the state space but must exhibit a high degree of locality (23).

To test the degree of locality in temporal networks, we calculate the length of each control trajectory using Embedded Image, where the energy-optimal trajectory for temporal networks as they move from x0 to xf followsEmbedded Imagefor Embedded Image, where Embedded Image is the matrix corresponding to the snapshot m and Embedded Image is a constant vector of dimension N (SM section S9). In general, L depends on the initial state x0 and the state-space distance Embedded Image between the origin and destination points (Fig. 4, A and B). For x0 = 0, in both static and temporal networks, L increases linearly with δ (Fig. 4B). Yet for any δ, the optimal control trajectories in temporal networks are about five orders of magnitude shorter than trajectories in their static counterparts (Fig. 4B). The difference is particularly notable in real systems: For the technological network, the temporal trajectory is 29 orders of magnitude shorter than the trajectory for the corresponding static network (Fig. 4C). Indeed, it is known that, in static networks, L can be large even when δ approaches zero, implying static control generally demands highly nonlocal control trajectories (23). By contrast, we find that the dynamical flexibility offered by temporality allows x(t) not to have to wander far into phase space as it moves from x0 to xf. The sailing analogy helps us once again to understand this difference: Travel against the prevailing wind is possible, but we must use complicated zigzag maneuvers to reach our destination. If, however, the wind occasionally changes direction, a strategic use of the sails allows us to travel more directly to our destination.

Fig. 4 Temporal networks exhibit more local trajectories.

(A) Three trajectories (triangle, circle, and square) for static (blue lines) and temporal (red lines) networks starting from x0 = 0, controlled to reach ‖xf‖ = 10–3 after a unit time with a1 = –10 and a2 = 2. (B) The length of the control trajectory L as a function of control distance Embedded Image. L is always much smaller for the temporal networks than for their static counterparts, regardless of the control distance (see SM section S9). Each point represents an average over 104 final states; we choose N = 10, M = 5. See SM section S9 for other parameters. (C) For the technological network, we track the evolution of x1(t) (corresponding to the maximum length of all state components) from Embedded Image to Embedded Image, finding that L is in the order of 1035 for the temporal network, in contrast with 1064 for the corresponding static network (see SM section S9 for more details).

The stark drop in control trajectory lengths observed here helps us resolve a fundamental conundrum about the inner workings of real systems. In real systems (particularly in subcellular networks), only a small number of “sensory” nodes are generally available for direct manipulation; however, the use of fewer driver nodes can drastically increase the length of the control trajectories (23), meaning that the nodes will have to take up extreme state values as the system converges to the desired final state. Temporality unlocks a mechanism through which typically underactuated natural systems can smoothly glide between required states—e.g., different stages of the cell cycle—without the need to pass through highly extreme states that might be potentially destructive to the system as a whole. That is, we can drive these sytems to their desired final state without drastically altering the state variables of the individual nodes. This could be particularly important in subcellular networks, where large changes in the concentrations of individual molecules may be toxic for a cell, or in technological systems, where the individual components must operate within their design specifications.

Our results demonstrate that temporality has profound dynamical consequences, fundamentally improving our ability to control real networks. This is consistent with previous findings that nonlinear dynamics, in this case induced by temporality, can be an asset rather than an obstacle to control (30). Beyond control, the measures introduced here offer a general glimpse into the dynamical flexibility of temporal networks. Indeed, these networks that exhibit a rapid growth of their controllable space (small St), and with concomitantly low control costs, represent dynamical “Swiss army knives,” capable of displaying a wide range of behaviors with a relatively small number of network links. Thus, our findings open the door to the design of networks that are adaptive to changing environments while using the same set of underlying nodes. This insight may lead to new, robust cyber networks, adaptive “smart” infrastructures, and new strategies for intervening in natural systems that capitalize on the best parts of each snapshot to obtain “the best of all worlds.”

Supplementary Materials

www.sciencemag.org/content/358/6366/1042/suppl/DC1

Materials and Methods

Figs. S1 to S25

References (3141)

References and Notes

  1. Acknowledgments: We thank G. Xie, Y. Guan, G. Yan, I. Kovács, I. Scholtes, M. Angulo, E. Guney, B. Barzel, J. Gao, R. Sinatra, S. Mou, Z. Ji, T. Gibson, J. Huang, K. Albrecht, M. Santolini, M. Szell, I. Donnelly, R. Rajaei, S. Aleva, B. Common, and J. De Nicolo for valuable discussions and help. We appreciate J. Wang and X. Peng for supplying the data of dynamic protein-protein interaction networks. We thank M. Gavin and the Defense Advanced Research Projects Agency project W911NF-12-C-002 for providing the mobile network data sets. This work is supported by Army Research Laboratories Network Science Collaborative Technology Alliance grant number ARL NS-CTA W911NF-09-2-0053; the John Templeton Foundation Mathematical and Physical Sciences grant numbers PFI-777 and 60478; European Commission grant numbers FP7 317532 (MULTIPLEX) and 641191 (CIMPLEX). A.L. and L.W. are supported by the National Natural Science Foundation of China (grants 61375120 and 61533001). A.L. also acknowledges the support from the China Scholarship Council (no. 201406010195). A.-L.B. and S.P.C. conceived the project. All authors designed and performed the research and analyzed the results. A.L. and L.W. performed all the analytical calculations. A.L. performed all the numerical calculations (except the technology network that was analyzed by Y.-Y.L. independently). A.-L.B., A.L., and S.P.C. led the writing of the manuscript, Y.-Y.L. and L.W. edited the manuscript.
View Abstract

Navigate This Article