## 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 (*4*–*7*), 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 (*8*–*14*), yet controllability normally requires the existence of continuous paths capable of carrying the input signals to the rest of the network (*15*–*18*). 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 **A**_{m}_{}for a duration Δ*t _{m}*. 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
(1)valid over the time interval , where the 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 captures the state of the whole system at time

*t*, and

*x*(

_{i}*t*) represents the state of node

*i*, like the concentration of metabolite

*i*within a cell. The input matrix

**B**

*identifies the set of driver nodes through which we attempt to control the system using independent control inputs , like manipulating the input concentration of*

_{m}*p*metabolites. To avoid conferring an unfair advantage to temporal networks, we use the same set of driver nodes across all snapshots, i.e.,

**B**

*=*

_{m}**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 (

*15*–

*17*,

*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*).

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 **x**_{0} = **0**. By considering all possible trajectories from the initial time *t*_{0} = 0 to the final time *t*_{f} = *t _{M}* , we can write the controllable space [see supplementary materials (SM) section S1.1] as(2)Here, denotes the controllable space of snapshot

*m*, where is the column space of

**B**. Hence, a temporal network of

*N*nodes is controllable if and only if(3)meaning that we can steer the system to an arbitrary state of the state space in finite time. For a static network, whose snapshots are identical (i.e.,

**A**

*=*

_{m}**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 *S*_{t} that must elapse before a temporal network becomes fully controllable. For comparison, we also calculate the minimum number of snapshots *S*_{s} 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., *S*_{t} = 2 (Fig. 1F). By contrast, we must aggregate *S*_{s} = 3 snapshots to obtain a controllable static network (Fig. 1E). The difference between *S*_{s} and *S*_{t} 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 *S*_{t} is always less than *S*_{s} (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 *S*_{t} and *S*_{s}) is distinct from *t*_{f}, representing the time a system needs to reach its final state (*8*, *15*, *22*–*24*).

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 *S*_{t} and *S*_{s} for different time windows Δ*t*, indicating that the number of snapshots required to control a temporal network *S*_{t} is less than that required for its static counterpart, *S*_{s}. The smaller the Δ*t*, the more pronounced the advantage of temporal networks. For example, for the face-to-face interactions at Δ*t* = 10^{3}, 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 *S*_{t} and *S*_{s} 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.

To determine to what extent these gains in controllability depend on the topology of the underlying snapshots, we calculate *S*_{t} and *S*_{s} 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 *S*_{t} < *S*_{s} (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 *S*_{t} < *S*_{s} 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 *S*_{s} and *S*_{t}, 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 *S*_{s} and *S*_{t} 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 required to drive a temporal network from an initial state **x**_{0} to final state **x**_{f}. For systems following (Eq. 1), we have (SM section S5)(4)where **d** is the difference vector between the desired final state **x**_{f} and the natural final state that the system reaches without control inputs, and the *N* × *N* matrix **W**_{eff} encodes the energy structure of the temporal network. For identical snapshots, **W**_{eff} reduces to the controllability matrix and Eq. 4 provides the control energy of a static network (SM, section S5.4). Computing **W**_{eff} scales in time as , where *N*_{d} is the number of driver nodes, and involves 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.

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 (*N*_{d}), 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 , where the energy-optimal trajectory for temporal networks as they move from **x**_{0} to **x**_{f} followsfor , where is the matrix corresponding to the snapshot *m* and is a constant vector of dimension *N* (SM section S9). In general, *L* depends on the initial state **x**_{0} and the state-space distance between the origin and destination points (Fig. 4, A and B). For **x**_{0} = **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 **x**_{0} to **x**_{f}. 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.

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 *S*_{t}), 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

This is an article distributed under the terms of the Science Journals Default License.

## References and Notes

- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
**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.