Temporal network
A temporal network, also known as a time-varying network, is a network whose links are active only at certain points in time. Each link carries information on when it is active, along with other possible characteristics such as a weight. Time-varying networks are of particular relevance to spreading processes, like the spread of information and disease, since each link is a contact opportunity and the time ordering of contacts is included.
Examples of time-varying networks include communication networks where each link is relatively short or instantaneous, such as phone calls or e-mails. Information spreads over both networks, and some computer viruses spread over the second. Networks of physical proximity, encoding who encounters whom and when, can be represented as time-varying networks. Some diseases, such as airborne pathogens, spread through physical proximity. Real-world data on time resolved physical proximity networks has been used to improve epidemic modeling.
Neural networks and brain networks can be represented as time-varying networks since the activation of neurons are time-correlated.
Time-varying networks are characterized by intermittent activation at the scale of individual links. This is in contrast to various models of network evolution, which may include an overall time dependence at the scale of the network as a whole.
Applicability
Time-varying networks are inherently dynamic, and used for modeling spreading processes on networks. Whether using time-varying networks will be worth the added complexity depends on the relative time scales in question. Time-varying networks are most useful in describing systems where the spreading process on a network and the network itself evolve at similar timescales.Let the characteristic timescale for the evolution of the network be, and the characteristic timescale for the evolution of the spreading process be. A process on a network will fall into one of three categories:
- Static approximation – where. The network evolves relatively slowly, so the dynamics of the process can be approximated using a static version of the network.
- Time-varying network – where. The network and the process evolve at comparable timescales so the interplay between them becomes important.
- Annealed approximation – where. The network evolves relatively rapidly, so the dynamics of the process can be approximated using a time averaged version of the network.
Representations
There are three common representations for time-varying network data.- Contact sequences – if the duration of interactions are negligible, the network can be represented as a set of contacts where and are the nodes and the time of the interaction. Alternatively, it can be represented as an edge list where each edge is a pair of nodes and has a set of active times.
- Interval graphs – if the duration of interactions are non-negligible, becomes a set of intervals over which the edge is active.
- Snapshots – time-varying networks can also be represented as a series of static networks, one for each time step.
Properties
Time respecting paths
Time respecting paths are the sequences of links that can be traversed in a time-varying network under the constraint that the next link to be traversed is activated at some point after the current one. Like in a directed graph, a path from to does not mean there is a path from to. In contrast to paths in static and evolving networks, however, time respecting paths are also non-transitive. That is to say, just because there is a path from to and from to does not mean that there is a path from to. Furthermore, time respecting paths are themselves time-varying, and are only valid paths during a specific time interval.Reachability
While analogous to connectedness in static networks, reachability is a time-varying property best defined for each node in the network. The set of influence of a node is the set of all nodes that can be reached from via time respecting paths, note that it is dependent on the start time. The source set of a node is the set of all nodes that can reach via time respecting paths within a given time interval. The reachability ratio can be defined as the average over all nodes of the fraction of nodes within the set of influence of.Connectedness of an entire network is less conclusively defined, although some have been proposed. A component may be defined as strongly connected if there is a directed time respecting path connecting all nodes in the component in both directions. A component may be defined as weakly connected if there is an undirected time respecting path connecting all nodes in the component in both directions. Also, a component may be defined as transitively connected if transitivity holds for the subset of nodes in that component.
Causal fidelity
Causal fidelity quantifies the goodness of the static approximation of a temporal network. Such a static approximation is generated by aggregating the edges of a temporal network over time. The idea of causal fidelity is to compare the number of paths between all node pairs in the temporal network with the number of paths between all nodes in the static approximation of the network. The causal fidelity is then defined bySince in only time respecting paths are considered,, and consequently. A high causal fidelity means that the considered temporal network is well approximated by its static counterpart. If, then most node pairs that are reachable the static representation are not connected by time respecting paths in the temporal network.
Latency
Also called temporal distance, latency is the time-varying equivalent to distance. In a time-varying network any time respecting path has a duration, namely the time it takes to follow that path. The fastest such path between two nodes is the latency, note that it is also dependent on the start time. The latency from node to node beginning at time is denoted by.Centrality measures
Measuring centrality on time-varying networks involves a straightforward replacement of distance with latency. For discussions of the centrality measures on a static network see Centrality.- Closeness centrality is large for nodes that are close to all other nodes
- Betweenness centrality is large for nodes that are often a part of the smallest latency paths between other pairs of nodes. It is defined as the ratio of the number of smallest latency paths from and that pass through to the total number of smallest latency paths from and
Temporal patterns
- Characteristic times of the system can be found by looking for distinct changes in a variable, such as the reachability ratio. For example, if one allows only a finite waiting time at all nodes in calculating latency, one can find interesting patterns in the resulting reachability ratio. For a mobile call network, the reachability ratio has been found to increase dramatically if one allows delays of at least two days, and for the airline network the same effect has been found at around 30 minutes. Moreover, the characteristic time scale of a temporal network is given by the mode of the distribution of shortest path durations. This distribution can be calculated using the reachability between all node pairs in the network.
- Persistent patterns are ones that reoccur frequently in the system. They can be discovered by averaging over different across the time interval of the system and looking for patterns that reoccur over a specified threshold.
- Motifs are specific temporal patterns that occur more often the expected in a system. The time-varying network of Facebook wall postings, for example, has higher frequency of chains, stars, and back and forth interactions that could be expected for a randomized network.
Dynamics
Burstiness
The time between two consecutive events, for an individual node or link, is called the inter-event time. The distribution of inter-event times of a growing number of important, real-world, time-varying networks have been found to be bursty, meaning inter-event times are very heterogeneous – they have a heavy-tailed distribution. This translates to a pattern of activation where activity comes in bursts separated by longer stretches of inactivity.Burstiness of inter-event times dramatically slows spreading processes on networks. Since many real-world networks exhibit burstiness this has implications for the spread of disease, computer viruses, information, and ideas.
Burstiness as an empirical quantity can be calculated for any sequence of inter-event times,, by comparing the sequence to one generated by a Poisson process. The ratio of the standard deviation,, to the mean,, of a Poisson process is 1. This measure compares to 1.
Burstiness varies from −1 to 1. B = 1 indicates a maximally bursty sequence, B = 0 indicates a Poisson distribution, and B = −1 indicates a periodic sequence.