In network science, a temporal network is a graph with an additional time component. ^[1]

Notation

In the context of temporal networks, edges are referred to as events, since they are thought to be active or passive as a function of time. To emphasize this difference, the term static graph is used to refer to the usual notion of graphs (which lack such a dynamic component).

Types of temporal networks

Contact graphs

Contact graphs are used when only the order of the events is considered, and the duration of the events is insignificant or irrelevant. A temporal network can be represented by a graph ${\displaystyle G=(V,E)}$ and for each edge ${\displaystyle e\in E}$ a (non-empty) set of contact times

${\displaystyle T_{e}=\{t_{1},t_{2},\ldots ,t_{n}\}.}$

In other words, we consider the edge ${\displaystyle e}$ to be active only at the times ${\displaystyle t_{1},t_{2},\ldots ,t_{n}}$.

Interval graphs

If the duration of events is important, one arrives at the more complicated notion of interval graphs. An interval graph is represented by a graph ${\displaystyle G=(V,E)}$ and for each edge a (non-empty) set

${\displaystyle T_{e}={\Big \{}(t_{1},\tau _{1}),(t_{2},\tau _{2}),\ldots ,(t_{n},\tau _{n}){\Big \}}.}$

An element ${\displaystyle (t_{i},\tau _{i})\in T_{e}}$ is interpreted as an event that starts at time ${\displaystyle t_{i}}$ and has duration ${\displaystyle \tau _{i}}$. Oftentimes it is required that all events have positive duration and that events belonging to the same ${\displaystyle T_{e}}$ do not overlap, ie. ${\displaystyle (t_{j}+\tau _{j}<t_{i})\vee (t_{i}+\tau _{i}<t_{j})}$. If otherwise not stated, in the following we assume that these restrictions hold.

Representation as a static graph

As the theory and set of tools for static graphs are already developed, it is natural to try to transform a temporal network to a (set of) static graphs and perform the analysis there by well-established methods.

Contact graphs can be represented by a sequence of graphs ${\displaystyle G_{t}=(V,E_{t})}$, where

${\displaystyle E_{t}=\{e\in E\ |\ t\in T_{e}\},}$

so ${\displaystyle G_{t}}$ is the graph of events that take place at time ${\displaystyle t}$. However, this approach might not be very useful if only a handful of contacts are active at a given discrete time.

A more general approach is to take a set of time windows ${\displaystyle W=\{[s_{i},t_{i}]\ |\ i=1,2,\ldots ,N\}}$ that cover the all the events (usually ${\displaystyle t_{i}-s_{i}}$ is a constant), and for every ${\displaystyle i=1,2,\ldots ,N}$ define ${\displaystyle G_{i}=(V,E_{i})}$, where

${\displaystyle E_{i}=\left\{e\in E\ |\ \exists (t,\tau )\in T_{e}{\text{ such that }}[t,t+\tau ]\cap [s_{i},t_{i}]\neq \emptyset \right\}.}$

Generalization of network concepts to temporal networks

Any concept or property that is defined for graphs can be interpreted on a temporal network by aggregating edges over a chosen time window. However, many concepts are greatly affected by the exact order of link activations, and these concepts need to be adjusted to temporal networks.

Time-respecting paths

A path in static graphs is a sequence of edges such that the successive edges have a common node. A time-respecting path in a temporal network is a sequence of events such that the successive events have a common node and an event does not start before the event preceding it (in the sequence) started.

We can similarly define time-respecting paths with maximal wait time ${\displaystyle \Delta t}$ to be the subset of time-respecting paths which do not wait more than ${\displaystyle \Delta t}$ time at any of the nodes in the path. In other words, if an event ${\displaystyle (t_{i},\tau _{i})}$ is followed by ${\displaystyle (t_{j},\tau _{j})}$, then we require that ${\displaystyle t_{j}\leq t_{i}+\tau _{i}+\Delta t}$.

Note that even if ${\displaystyle B}$ is reachable from ${\displaystyle A}$ through time-respecting paths, there may not a time-respecting path from ${\displaystyle B}$ to ${\displaystyle A}$, ie. generally the reachability relation is not symmetric. Moreover, it is not even transitive in the general case.

Set of influence, source set, reachability ratio

Define for a node ${\displaystyle A\in V}$ in time window ${\displaystyle [t_{1},t_{2}]}$ its set of influence to be the set of nodes which can be reached from ${\displaystyle A}$ by time-respecting paths whose events take place in the time window ${\displaystyle [t_{1},t_{2}]}$. The reachability ratio is defined to be fraction of nodes in the set of influence averaged over the vertices's of the graph.

Conversely, define for a node ${\displaystyle A\in V}$ in time window ${\displaystyle [t_{1},t_{2}]}$ its source set to be the set of nodes from which ${\displaystyle A}$ can be reached by time-respecting paths whose events take place in time window ${\displaystyle [t_{1},t_{2}]}$.

Similarly, we can define the set of influence, the source set and the reachability ratio by time respecting paths with maximal waiting times.

Distances, latencies, fastest paths

In temporal networks, we define the length of a time-respecting path to be the number of contacts/events in the path, and a shortest time-respecting path between two nodes is a path connecting the two nodes which has minimal length.

The duration of a time-respecting path to be the difference between the last and the first contact time (in an interval graphs, we may choose to add the even the duration of the last event to this difference). The latency from node ${\displaystyle A}$ to node ${\displaystyle B}$ with respect to a time window ${\displaystyle [t_{1},t_{2}]}$ is the minimum of the durations of time-respecting paths from ${\displaystyle A}$ to ${\displaystyle B}$ entirely in the time window, and is denoted by ${\displaystyle \lambda _{[t_{1},t_{2}]}(A,B)}$. The time-respecting path with the shortest duration between two nodes is called the fastest path between those two nodes.

Centrality measures

The closeness centrality can be defined as follows in temporal networks

${\displaystyle C_{C}(i,[t_{1},t_{2}])={\frac {|V|-1}{\displaystyle \sum _{i\neq j\in V}\lambda _{[t_{1},t_{2}]}(i,j)}}}$

There is not such a straightforward analogue for betweenness centrality in temporal networks. Let ${\displaystyle {\mathcal {P}}_{jk}}$ be a fixed subset of paths that start at node ${\displaystyle j}$ and end at ${\displaystyle k}$ (usually only time-respecting paths are considered). Now let ${\displaystyle v_{jk}=|{\mathcal {P}}_{jk}|}$ and let ${\displaystyle v_{jk}(i)}$ be the number of paths in ${\displaystyle {\mathcal {P}}_{jk}}$ that contain ${\displaystyle i}$ as an intermediate node. Then the betweenness-centrality of node ${\displaystyle i}$ is defined as

${\displaystyle C_{B}(i)=\sum _{j\neq i\neq k}{\frac {v_{jk}(i)}{v_{jk}}}.}$

Frequent choices for ${\displaystyle {\mathcal {P}}_{jk}}$ are the set of shortest time-respecting paths or the set of fastest paths.

Notes