Path lengths, correlations, and centrality in temporal networks

In temporal networks, where nodes interact via sequences of temporary events, information or resources can only flow through paths that follow the time ordering of events. Such temporal paths play a crucial role in dynamic processes. However, since networks have so far been usually considered static or quasistatic, the properties of temporal paths are not yet well understood. Building on a definition and algorithmic implementation of the average temporal distance between nodes, we study temporal paths in empirical networks of human communication and air transport. Although temporal distances correlate with static graph distances, there is a large spread, and nodes that appear close from the static network view may be connected via slow paths or not at all. Differences between static and temporal properties are further highlighted in studies of the temporal closeness centrality. In addition, correlations and heterogeneities in the underlying event sequences affect temporal path lengths, increasing temporal distances in communication networks and decreasing them in the air transport network.

Figure 1

Schematic representation of the variation of temporal distances between two pairs of nodes: (a) $i$-$j$ and (b) $k$-$l$. The period of observation is between 5 a.m. and 5 p.m. In panel (a), the two nodes are connected by an event that begins at 8 a.m and takes two hours to completion. In panel (b), the nodes are connected by an event of the same duration at 1 p.m. If the average temporal distance were defined only over its finite range, then ${\tau }_{\mathit{ij}}<{\tau }_{\mathit{jk}}$, although both pairs are connected via similar events.

Figure 2

Schematic representation of the time variation of the temporal distance between a pair of nodes $i$-$j$: (a) the actual distance and (b) the distance with periodic boundary condition on paths connecting $i$ and $j$.

Figure 3

Top: the average temporal distance ${\tau }_{\mathit{ij}}$ against the static graph distance $d_{\mathit{ij}}$ between all pair of nodes for (a) the call network, (b) the email network, and (c) the air transport network. The average temporal distances ${\tau }_{\mathit{ij}}$ were calculated using periodic boundary conditions, as detailed in the text. The colors represent the conditional probabilities of ${\tau }_{\mathit{ij}}$ for a given $d_{\mathit{ij}}$. Note the broad distribution of $P({\tau }_{\mathit{ij}}|d_{\mathit{ij}})$ in all three cases. Bottom: The fraction of finite temporal paths $f_{\mathrm{Finite}}$ as a function of $d_{\mathit{ij}}$ for (d) the mobile phone call network, (e) the email network, and (f) the air transport network. It is seen that the longer a static path, the less likely the existence of a corresponding temporal path within the observation window.

Figure 4

Cumulative distribution of the temporal distances for the (a) mobile phone call and (b) air transport network. The corresponding distribution for the time-shuffled, random-time, and equal-weight link-sequence shuffled cases are also shown. It is seen that the distances in the mobile phone call network are relatively long compared to the time-shuffled and random references, whereas they are short in the air transport transport network designed to transfer passengers in an optimal way.

Figure 5

Fraction of finite temporal paths as a function of ${\Delta }_{\mathrm{c}}$ for the (a) mobile phone call and (b) air transport network.

Figure 6

Comparison of the cumulative probability distributions of the temporal distances for the original and the randomized null models in the (a) mobile phone call network with a cutoff ${\Delta }_c=2$ days and (b) air transport network with cutoffs ${\Delta }_c^{\min }$ $=$ 30 min and ${\Delta }_c=5$ h. Line styles denote different null models, similarly to Fig. 4.

Figure 7

Static and temporal closeness centrality ($C^{\mathrm{S}}$ and $C^{\mathrm{T}}$) of the nodes against their (a), (c) degree, $k$ and (b), (d) $k^s$-shell index in the mobile phone call network. Circles denote mean values, while the shading represents conditional probabilities $P(C^{\mathrm{S},\mathrm{T}}|k)$ and $P(C^{\mathrm{S},\mathrm{T}}|k^s)$.

Figure 8

Static and temporal closeness centrality ($C^{\mathrm{S}}$ and $C^{\mathrm{T}}$) of the nodes against their (a), (c) degree, $k$ and (b), (d) $k^s$-shell index in the air transport network. Circles denote mean values, while the shading represents conditional probabilities $P(C^{\mathrm{S},\mathrm{T}}|k)$ and $P(C^{\mathrm{S},\mathrm{T}}|k^s)$.

Figure 9

Pseudocode for the temporal distance algorithm with directed and noninstantaneous events.