Concurrency and reachability in treelike temporal networks

Network properties govern the rate and extent of various spreading processes, from simple contagions to complex cascades. Recently, the analysis of spreading processes has been extended from static networks to temporal networks, where nodes and links appear and disappear. We focus on the effects of accessibility, whether there is a temporally consistent path from one node to another, and reachability, the density of the corresponding accessibility graph representation of the temporal network. The level of reachability thus inherently limits the possible extent of any spreading process on the temporal network. We study reachability in terms of the overall levels of temporal concurrency between edges and the structural cohesion of the network agglomerating over all edges. We use simulation results and develop heterogeneous mean-field model predictions for random networks to better quantify how the properties of the underlying temporal network regulate reachability.

Figure 1

Schematics for establishing accessibility. (a) Contact network: Each edge in the network of nodes $\left\{A,B,C,D\right\}$ is denoted by a start and end time, e.g., the contact between $A$ and $D$ starts at $t=1$ and continues for one time unit to $t=2$. (b) Aggregated static network: the static network representation aggregating temporal information. (c) Accessible network: the corresponding directed graph of accessibility, demonstrating that asymmetric accessibilities (red arrows) are possible. (d) Temporal contacts: the contacts represented along a time axis. (e) Accessibility matrix: The accessibility matrix between the four nodes, with the $(i,j)$ element, indicates if $j$ is reachable from $i$.

Figure 2

Temporal layered matrices as observed immediately before the end time of a link. Here ${\mathbf{T}}_0$ is the adjacency matrix immediately before the disappearance of the earliest ending link $(A,D)$ from Fig. 1. Similarly, ${\mathbf{T}}_1$ is the adjacency matrix immediately before the end of the next ending link $(A,B)$. That is, ${\mathbf{T}}_w$ includes all links in Fig. 1 that overlap with the disappearance of the $w\mathrm{th}$ link (counting from 0, ${\mathbf{T}}_3$ not shown). If multiple edges end at the same time, the accessibility calculation proceeds equivalently with either a separate but identical matrix for each edge ending at that time or a single matrix corresponding to that time.

Figure 3

Simulated and approximated reachability on balanced and unbalanced tree networks as a function of temporal concurrency $C$. Two different sizes of trees are tested: (a) and (c) are for $m=2$ and $h=6$ ($N=127$) for balanced and unbalanced tree networks, respectively, and (b) and (d) are for $m=3$ and $h=4$ ($N=121$) for balanced and unbalanced tree networks, respectively. Navy lines display the simulated reachability with 100 synthetic balanced and unbalanced networks. Green dashed lines represent the approximation $\overline{R}$ relying on the numbers and lengths of paths between each node pair. The dashed red line shows the approximated reachability with the node-independent path length distribution ${\tilde{R}}_n$ (which is equivalent to ${\tilde{R}}_s$ on a tree). Error bars indicate standard deviations.

Figure 4

Simulated and approximate reachability on sparse ER networks as a function of temporal concurrency $C$. Largest connected components for two different size networks are tested: (a) $\langle k\rangle \approx 2,\langle N\rangle =94$ and (b) $\langle k\rangle \approx 3,\langle N\rangle =113$. The solid line indicates the numerically measured reachability simulated over 100 ER networks for each size. Error bars indicate standard deviations. Dashed lines indicate the different approximations for the reachability.

Figure 5

Simulated reachability with edge durations distributed according to a power-law distribution $p\left(d\right)\propto d^{-\alpha }, \alpha =2.25$ (solid lines) and an exponential distribution $p\left(d\right)\propto e^{-d}$ (dashed lines) on the balanced tree network with $r=3$ and $h=4$ ($N=121$) and ER networks ($\langle k\rangle =2$ with $\langle N\rangle =94, \langle k\rangle =3$ with $\langle N\rangle =113$). We run simulations for 100 different networks to obtain the standard deviations of reachability indicated by error bars for the power-law distributions results. Standard deviations for the results with the exponential distribution, as indicated in the previous figures, appear to be comparable in magnitude.

Figure 6

Reachability frequency $f(k_i,k_j)$ and relative reachability frequency $\widehat{f}(k_i,k_j)$ for ER networks with $\langle k\rangle \approx 2$. The numbers of reachable node pairs are counted from the accessibility matrix $\mathbf{R}$ for the largest connected component of 100 ER networks. (a) and (b) show the reachability frequency $f(k_i,k_j)$, the fraction of reachable node pairs that have the indicated degrees. (c) and (d) show relative connectivity frequency $\widehat{f}(k_i,k_j)$, the fraction of node pairs with the indicated degrees that are reachable. The temporal concurrency is (a) and (c) $C\doteq 0.1$ and (b) and (d) $C\doteq 0.97$.

Figure 7

Fit of $\kappa$ for the reachability of ER network largest connected components with $\langle k\rangle =3$. The circles with error bars and the gray dashed line represent the numerical reachability and ${\tilde{R}}_s$ approximation with the shortest path length distribution, respectively. The dotted line shows ${\tilde{R}}_s$ recalculated with constant $\kappa (i,j)=1.5$, while the solid curve uses $\kappa (i,j)=3.5$ as the exponent in Eq. (10) for all node pairs.

Figure 8

Simulated and approximate reachability as a function of the temporal concurrency for empirical networks with different levels of structural cohesion: (a) sample network (i), $\langle k\rangle =3.4, \langle \kappa \rangle \doteq 1.06$, and $N=128$; (b) sample network (ii), $\langle k\rangle =3.71, \langle \kappa \rangle \doteq 1.07$, and $N=154$; (c) sample network (iii), $\langle k\rangle =5.27, \langle \kappa \rangle \doteq 1.34$, and $N=80$; and (d) sample network (iv), $\langle k\rangle =6.16, \langle \kappa \rangle =1.61$, and $N=148$. Means of simulated results $R$ are indicated by solid lines with error bars indicating standard deviations over 50 different simulated timings. The green dashed line indicates the approximation $\overline{R}$ obtained from the measured numbers and lengths of node-independent shortest paths between each node pair, as in Eq. (8). The other dashed lines indicate the approximations ${\tilde{R}}_s$ and ${\tilde{R}}_n$ using path length distributions, as in Eq. (11). Each network sample is visualized in the corresponding panel, with node shade indicating degree.

Figure 9

Approximated and numerically estimated structural cohesion of ER and exponential degree distribution networks (EXP) as a function of average degree $\langle k\rangle$. (a) Dashed lines show the approximated structural cohesion averaging ${\kappa }_{max}(i,j)=\min (k_i,k_j)$ over node pairs for ER (light blue) and EXP (light green) networks with $N=200$. (b) Solid lines are numerical estimations of the structural cohesion for ER (blue shades, circles) and EXP (green shades, triangles) networks of different network sizes ($N=100$, 200, and 400). Standard deviations are shown.

Figure 10

Reachability $R$ versus temporal concurrency $C$ for random graphs with different degree distributions. The ER origin graphs are Erdős-Rényi graphs with mean degree $\langle k\rangle =3$, yielding an empirically expected cohesion $\langle \kappa \rangle =2$ (magenta line). The ER graphs are with mean degree $\langle k\rangle =3$ rewired to obtain expected cohesion $\langle \kappa \rangle =1.7$ (red line). The EXP origin graphs here are exponential degree distributions with the same $\langle k\rangle =3$, yielding an empirically expected cohesion $\langle \kappa \rangle =1.6$ (green line). The EXP denotes rewired graphs having exponential degree distribution, yielding expected cohesion $\langle \kappa \rangle =1.7$ as described in the Appendix. The filled area shows the standard deviation.