Lifetime-preserving reference models for characterizing spreading dynamics on temporal networks

Abstract

To study how a certain network feature affects processes occurring on a temporal network, one often compares properties of the original network against those of a randomized reference model that lacks the feature in question. The randomly permuted times (PT) reference model is widely used to probe how temporal features affect spreading dynamics on temporal networks. However, PT implicitly assumes that edges and nodes are continuously active during the network sampling period - an assumption that does not always hold in real networks. We systematically analyze a recently-proposed restriction of PT that preserves node lifetimes (PTN), and a similar restriction (PTE) that also preserves edge lifetimes. We use PT, PTN, and PTE to characterize spreading dynamics on (i) synthetic networks with heterogeneous edge lifespans and tunable burstiness, and (ii) four real-world networks, including two in which nodes enter and leave the network dynamically. We find that predictions of spreading speed can change considerably with the choice of reference model. Moreover, the degree of disparity in the predictions reflects the extent of node/edge turnover, highlighting the importance of using lifetime-preserving reference models when nodes or edges are not continuously present in the network.

Figure 1

Distribution of lifespans of edges for four temporal networks. L_E is the lifespan of an edge, calculated as the time difference between the timestamps of the last and the first contact of the edge; 〈L_E〉 is the mean of L_E. Edges with a single contact are assigned a lifespan equal to the sampling resolution. Bin widths are uniform in log space on the interval [10⁻⁵, 10]. The Prostitution network has a large number of edges with a single contact, resulting in a peak at the left end of the distribution.

Figure 2

Distributions of activation times, deactivation times, and lifespans of nodes for four empirical networks. The columns present probability density distributions of normalized activation times, deactivation times, and lifespans of nodes, respectively, while rows correspond to results for the Ant, Prostitution, Conference and Workplace networks, respectively. In all cases, bin sizes are set to 0.1.

Figure 3

Construction of the PTE and PTN reference models. In (A), we illustrate PTE by considering two edges (a, b) and (c, d) with 5 contacts each, labelled 1–5 and 6–10 respectively. Vertical lines represent the time when a contact is initiated. Red lines are contact initiation times that “activate” or “deactivate” an edge. We only permute times that do not activate or deactivate an edge. In this example, eligible permutations are (4, 7) and (4, 8). By contrast, (2, 7) is ineligible because the lifespan of (c, d) would be extended. In (B), we illustrate PTN. Vertical lines represent contact initiation times between nodes (a, b, c, d). Blue lines are node activation and deactivation times. Shaded areas depict the lifespans of nodes. To permute contact pairs from edges (a, b) and (c, d), we first obtain the intersection of the lifespans of nodes a, b, c and d, which is highlighted in green. The permutation of contact times is allowed only if the two contacts to be permuted are both located within the green interval. For instance, (4, 8) is an eligible permutation while (2, 9) is rejected because it would extend the lifespans of nodes a and c.

Figure 4

Mean prevalence evolution on empirical networks and the corresponding reference models. Each panel shows the mean fraction of infected nodes, 〈I(t)/N〉, at each point in time for the original contact sequence (black solid line) and the PT, PTN, and PTE reference models (each averaged over four reference networks). (A) Ant, (B) Prostitution, (C) Conference, and (D) Workplace. In panel (B), the prevalence curves for the empirical network and the PTN and PTE models are so close as to be indistinguishable.

Figure 5

Simulation results for synthetic networks under variations in edge heterogeneity λ. Panel (A) shows the average speed-up S_0.2 for the three reference models. In panel (B), we give the relative differences of t_0.2 of PTE and PTN, respectively, with respect to PT.

Figure 6

Simulation results for synthetic networks under variations in edge IET power-law distribution exponent β. Panel (A) shows the relative average speed-up S_0.2 for the three reference models. Panel (B) shows the burstiness coefficient B_E of edge IETs for the synthetic networks and the analytical solution predicted by the truncated power-law distribution.