key: cord-0601030-6a84vmw0
authors: Chen, Qinyi; Porter, Mason A.
title: Epidemic Thresholds of Infectious Diseases on Tie-Decay Networks
date: 2020-09-27
journal: nan
DOI: nan
sha: f85de1c322da4947601575a0734598535a444384
doc_id: 601030
cord_uid: 6a84vmw0

In the study of infectious diseases on networks, researchers calculate epidemic thresholds to help forecast whether a disease will eventually infect a large fraction of a population. Because network structure typically changes in time, which fundamentally influences the dynamics of spreading processes on them and in turn affects epidemic thresholds for disease propagation, it is important to examine epidemic thresholds in temporal networks. Most existing studies of epidemic thresholds in temporal networks have focused on models in discrete time, but most real-world networked systems evolve continuously in time. In our work, we encode the continuous time-dependence of networks into the evaluation of the epidemic threshold of a susceptible--infected--susceptible (SIS) process by studying an SIS model on tie-decay networks. We derive the epidemic-threshold condition of this model, and we perform numerical experiments to verify it. We also examine how different factors---the decay coefficients of the tie strengths in a network, the frequency of interactions between nodes, and the sparsity of the underlying social network in which interactions occur---lead to decreases or increases of the critical values of the threshold and hence contribute to facilitating or impeding the spread of a disease. We thereby demonstrate how the features of tie-decay networks alter the outcome of disease spread.

Infectious diseases spread over social networks, and there is thus much research on the spread of diseases on networks [24, 30, 31] . The simplest type of network is a graph, in which each node represents an entity (e.g., an individual who is prone to infection) and each edge represents a tie (such as a social relationship) between two entities. Disease transmission occurs across edges. Each node has an associated state-such as susceptible, infected, recovered, zombified, or something else-and different states are appropriate for different diseases. Each state is called a "compartment", and models of infectious diseases with such compartments are called "compartmental models" [6] . Common compartmental models of infectious diseases include susceptible-infected-susceptible (SIS) processes, susceptible-infected-recovered (SIR) processes, and susceptible-exposed-infected-recovered (SEIR) processes. By modeling the contact patterns of a set of individuals using a network, one can examine the spread of an infectious disease on a social network. This, in turn, helps improve forecasts of disease epidemiology examine the spread of diseases in a so-called "quenched" state (in which the spreading process is faster than the evolution of the network on which it spreads) or in a so-called "annealed" state (in which a network evolves more rapidly than a spreading process on it) [34] , but a tie-decay network need not possess such a separation into distinct time scales. On a tie-decay network, the evolution of the network and the spreading process can take place at comparable time scales. The tie strengths of a tie-decay network evolve continuously as a disease spreads, thereby influencing both the final outbreak size and the time at which the disease dies out or leads to a large-scale outbreak. Another way in which a tie-decay network differs from many other types of networks, such as those that arise from activitydriven models or when one just considers a sequence of network snapshots, is that tie strengths are not specified arbitrarily or determined by time-invariant activity rates that are associated with each node. Instead, the tie strengths in a network are governed both by the frequencies of the interactions between nodes and by the decay rates of these strengths. These features of tie-decay networks make them relevant for modeling social relationships, and we are thus motivated to investigate how these features influence the dynamics of disease spread.

In the study of the spread of infectious diseases, it is common to assume that a disease spreads only when two entities interact with each other [24, 31] . A tie-decay network is able to model the spread of a disease both through direct "contact" from close proximity (i.e., when an interaction takes place) and through indirect means (such as transmission through the air or by touching the same contaminated surface). A decaying tie can perhaps model the decrease in the likelihood of disease transmission following a direct interaction between individuals. For instance, when there is a direct contact between an infected individual and a susceptible one, a disease may not spread immediately from the former to the latter. It is also possible for disease transmission to occur after the susceptible individual touches an item that was exposed previously to the infected individual. Such indirect disease transmissions occur with lower probability as time elapses, and decaying ties between individuals can perhaps capture such situations. Employing tie-decay networks thus allows the possibility of disease spread even when there is no face-to-face interaction between entities. Studying disease dynamics on tie-decay networks can contribute to the understanding of how diseases spread in a real-world social network that evolves continuously in time. Additionally, compartmental models such as SIS processes have also been applied to studying the spread of information or attitudes in a population [14, 42] . It seems potentially suitable to use tie-decay networks in such settings. For instance, an interaction can encode one entity informing another entity about some information, but the receiver of the information does not change their opinion until an "infection" event takes place. Additionally, because the strength of the tie between these two entities decays over time, the likelihood that the entity that receives information changes their beliefs from a new interaction between these two entities decreases with the amount of time since their last interaction. The use of tie-decay networks to study the spread of information or opinions allows one to differentiate an instantaneous transmission of information (through an interaction) from the long-lasting influence of information that was received in the past (as encoded in tie strength).

In the present paper, we study the dynamics of disease spread on a tie-decay network by examining the epidemic threshold of an SIS process. We first discuss the modeling choices that we make to associate the tie strengths with the spreading rates. Our mathematical formulation allows us to derive the epidemic threshold of an SIS process on a tie-decay network by extending the derivation of the epidemic threshold on other types of temporal networks. In our study, we build on methods that were designed for a sequence of network snapshots [35, 40] . 1 We then evaluate our theoretical expression for the epidemic 4 of 24 Q. CHEN AND M. A. PORTER threshold using numerical experiments on both synthetic and real-world networks, and we explore the impact of the network parameters on the spreading process.

Our paper proceeds as follows. In Section 2, we mathematically formalize an SIS process on a tie-decay network. In Section 3, we derive the epidemic threshold of an SIS process on a tie-decay network using two different methods. One is based on a nonlinear dynamical system, and the other is based on a tensor representation. In Section 4, we construct tie-decay networks from both synthetic and real-world data, and we simulate SIS processes on them. The results of the numerical experiments validate our theoretical expression for the epidemic threshold, and they also illustrate the influence of the network parameters on the spreading dynamics. In Section 5, we conclude and propose future research directions.

We first construct a tie-decay network using the formulation from [1] . Let B(t) be an N × N matrix of the tie strengths between each pair of the N nodes in a network. The entry b i j (t) of B(t) encodes the tie strength between nodes i and j at time t. Following an interaction between nodes i and j, the strength of the tie between them decays exponentially according to the differential equation

where α > 0 is the decay coefficient. If nodes i and j interact at time t, then the strength of the tie between them increments by 1 at time t. Therefore, if nodes i and j interact with each other at times t = t 1 ,t 2 , . . ., the tie strength between them satisfies

where H(t) is the Heaviside step function. The following ordinary differential equation (ODE) describes the dynamics of the tie strengths:

The interactions between nodes i and j are undirected in nature, so b i j (t) = b ji (t) for all times t. We do not consider self-interactions, so b ii (t) = 0 for any node i and any time t.

In practice, to model and analyze the spread of an infectious disease on a tie-decay network, we discretize time with a small time step of length ∆t. Ahmad et al. [1] chose a value of ∆t that is sufficiently small such that there is at most one interaction between agents. With this choice, one can convert a tie-decay network into a discrete set of temporal networks with adjacency matrices B (τ) = B(τ∆t), where τ = 0, 1, 2, . . . indicates the time step. At each of these time steps, we suppose that the disease spreads, such that any change in network structure directly impacts the spreading properties at the τth time step. Although we discretize our tie-decay networks, we treat the underlying time as continuous. Additionally, we have the following relationship between a temporal snapshot and its predecessor:

where A (τ) is an indicator matrix in which either 2 or 0 entries are nonzero (because we are considering undirected networks). A pair of nonzero entries represents the single interaction that takes place during the τth time step. Although Ahmad et al. [1] required ∆t to be small enough such that there is at most one interaction in one time step, in practice, one can relax this requirement as long as the number of interactions in any time step ((τ − 1)∆t, τ∆t] is not too large. In this way, we avoid binning interactions EPIDEMIC THRESHOLDS OF INFECTIOUS DISEASES ON TIE-DECAY NETWORKS   5 of 24 into intervals of a fixed length. In Section 4.5, we compare our results on a tie-decay network versus results that we obtain using a traditional temporal network in which we bin interactions into adjacent windows of a fixed length. If there is an interaction between nodes i and j at time t that satisfies

ji = 1 and set all other entries of A (τ) to 0. This interaction thus changes the network structure and influences the spreading behavior of a disease during the τth time step. In Section 4.4, we discuss how we choose ∆t for networks that we construct from empirical data. Because we discretize our tie-decay networks using a small time step, we obtain a number of temporal snapshots that tends to be much larger than the number of temporal snapshots that are often studied in practice in discrete-time temporal networks. In Section 4.3, we show that if we discretize a tie-decay network into T temporal snapshots, it is possible to estimate the epidemic threshold using only the first T 0 T snapshots. This enables us to use a reasonable amount of computational time for studying disease dynamics on tie-decay networks.

As a case study, we consider a susceptible-infected-susceptible (SIS) model [6, 24] (one of the most common types of compartmental models), where the nodes can be either in a susceptible state or in an infected state (i.e., a "compartment" in the language of mathematical epidemiology). At each time step, a susceptible node can be infected by each of its infected neighbors with independent probability λ , and each infected node can recover from the disease and become susceptible again with independent probability µ. We make a slight modification to the definition of a traditional SIS model to incorporate the traits of a tie-decay network. Suppose that an SIS process occurs on a tie-decay network with a tie-strength matrix B(t) with entries b i j (t). We also assume that λ max is the maximum possible infection probability and that the probability that an infected node i infects a susceptible node j at time t is λ max min{b i j (t), 1}. That is, for nodes i and j with a tie strength b i j (t) that exceeds 1, the infection probability is λ max . If the tie strength between them is less than or equal to 1, then the infection probability is λ max b i j (t). When b i j (t) = 0, there is no tie between nodes i and j, so no infection event can take place between them. Therefore, the infection probabilities, which are different for different pairs of nodes, in a tie-decay network depend on how the network evolves in time. At each time t, an infected node recovers with probability µ, and it is then in the susceptible state again at time t + 1.

When modeling an SIS process on a tie-decay network, we first determine the duration of the time step ∆t in our discretization, and we discretize the network into a total of T temporal snapshots. At each time step, we update the tie strengths B (τ) by letting all ties decay exponentially and incrementing the ties for which an interaction takes place. For each infected node, we then see if there are any infection or recovery events. After the T th time step, the dynamics stop and we examine the final outbreak size of the epidemic. In Table 1 , we summarize the main notation in our paper.

We now derive the epidemic threshold of an SIS process on a tie-decay network. The way that we perform time discretization allows us to extend methods that were designed for deriving epidemic thresholds in discrete temporal-network models to tie-decay networks.

We derive the same epidemic threshold using two different methods. The first method is based on a derivation in Aditya et al. [35] , who modeled an SIS process as a nonlinear dynamical system and derived the epidemic threshold using linear stability analysis. The second method that we use was employed by Valdano et al. [40] , who modeled disease transmission using a multilayer representation [9, 25] of a temporal network and an associated adjacency tensor. We discuss both methods to demonstrate two distinct approaches for deriving an epidemic threshold. We thereby illustrate that any method that one can apply to an arbitrary sequence of network snapshots is suitable for tie-decay networks because the set of neighbors of node i µ the recovery probability in the SIS process N the total number of nodes in a tie-decay network p the edge-creation probability of an Erdős-Rényi network α the decay coefficient of tie strengths in a tie-decay network ∆t the duration of one time step T the total number of temporal snapshots after we discretize a tie-decay network l the minimal length of the period for which the periodic boundary condition B (τ) = B (τ+l) is satisfied S the system matrix of an SIS process on a tie-decay network ρ cr (S) the spectral radius of the matrix S (if S is the system matrix of the SIS process, then ρ cr (S) is the critical value of the epidemic-threshold condition)

the ensemble of Erdős-Rényi networks with N nodes and edge-creation probability p G(N, p) an instance of an Erdős-Rényi network with N nodes and edge-creation probability p such methods utilize the temporal changes of a network. Both approaches rely on the use of a periodic boundary condition in time to derive an epidemic threshold. This is essential to guarantee stability of the disease-free state, and we thereby also use such boundary conditions in our derivations.

We derive the epidemic threshold of an SIS model on a tie-decay network by extending the approach in Aditya et al. [35] , who modeled an SIS process using a nonlinear dynamical system. As we discussed in Section 2, we discretize a tie-decay network such that each time step is of length ∆t. We thereby convert a tie-decay network into a discrete set of temporal networks with tie-strength matrices B (τ) , where τ ∈ {1, 2, . . . , T }. At each of the time steps, an infection of a susceptible node j by an infected node i occurs with probability λ

i j , 1} and each infected node recovers with independent probability µ. Let ξ τ (i) denote the probability that node i does not become infected in the τth time step, and let p (τ) i denote the probability that node i is in the infected state at time τ. We use Γ (i) to denote the set of neighbors of node i, and we assume that the states of the nodes in Γ (i) are uncorrelated with each other. The following relationship holds:

where g τ is a function that depends on B (τ) . The nonlinear dynamical system (3.4) describes the dynamics of disease spread on a tie-decay network. To determine whether a disease dies out or leads to an outbreak, we assume that we have boundary periodic conditions in time (see [35] ). That is, after we discretize a tie-decay network, we assume that B (τ) = B (τ+l) for some constant l, which allows us to examine the asymptotic stability of the system by looking at just one period. Although a periodic boundary condition in time are not something that one expects to observe in temporal networks that one constructs from empirical data, we choose l to be arbitrarily large so that we do not need to lose generality, because we can set l = T (where we recall that T is the final time). Additionally, in Section 4.3, we demonstrate that even with this periodic boundary condition, we can approximately characterize SIS spreading dynamics on a tie-decay network using a shorter period l. Given the discrete dynamical system (3.4), we recall the following theorem [16] .

is asymptotically stable at the fixed point x * if the magnitude of the dominant eigenvalue of the Jacobian J = ∇g(x * ) is less than 1.

Using this result gives the following lemma.

If the magnitude of the dominant eigenvalue of S is less than 1, then p τ is asymptotically stable at 0.

Proof. Because of the periodic boundary condition in time, it follows that S τ = S τ+l . The choice of τ is arbitrary, so it suffices to show that p lτ is asymptotically stable at time 0. Consider p l(τ+1) = g l−1 (g l−2 (· · · (g 1 (g 0 (p lτ ))) · · · )). We have

Consequently, by Theorem 3.1, if the magnitude of the dominant eigenvalue of S is less than 1, it follows that p lτ is asymptotically stable at 0. We also obtain asymptotic stability of p lτ+1 , . . . , p lτ+l−1 because the dominant eigenvalue of the product of invertible matrices is invariant under a cyclic permutation.

If the magnitude of the dominant eigenvalue of each matrix S τ is less than 1, then the magnitude of the dominant eigenvalue of S is also less than 1 and the system is asymptotically stable at 0. However, this is a much more conservative condition than our epidemic-threshold condition:

where ρ cr (Θ ) is the spectral radius of the matrix Θ . Even when the dominant eigenvalues of some of the S τ matrices have magnitudes that are larger than 1, the disease can still die out asymptotically, depending on the spectrum of S. We refer to S as the system matrix of our SIS process on a tie-decay network, and we refer to ρ cr (S) as the critical value of the epidemic-threshold condition (and hence of the epidemic threshold).

We now derive the epidemic threshold of an SIS process on a tie-decay network by extending the derivation in [40] that is based on a multilayer representation of a temporal network. We again consider our SIS model on a tie-decay network with tie-strength matrix B(t), which we discretize into snapshots B (τ) , where τ ∈ {1, 2, . . . , T }. As in Section 3.1, we use the periodic boundary condition B (τ) = B (τ+l) with period l and we seek the asymptotic solution for one period. We define a tensor M with components

to reflect the dynamics of (3.3). This tensor encodes information about the probability that node i is infected by node j when we advance from time step τ to time step τ + 1. One can also represent M 9 of 24 using a supra-adjacency matrix M ∈ R Nl×Nl (see [9, 13] ), where N is the total number of nodes. Let p(k) be the state vector of the kth time period, which covers time steps in the interval [kl, (k + 1)l]. Let α = Nτ + i, and let p α (k) denote the probability that node i is in the infected state in time step kl + τ.

Using this notation, we write (3.3) as

The asymptotic solution of the state vectorp for one period iŝ

By the analysis in [40] , the epidemic-threshold condition is

, which matches the formulation in Lemma 3.1. This again yields the epidemic-threshold condition (3.6).

We now conduct numerical experiments in which we simulate an SIS process on various tie-decay networks. We perform our computations on a workstation using code that we wrote in PYTHON 2 . In Section 4.1, we validate the epidemic-threshold condition (3.6) by comparing our theoretical results with our numerical simulations. In Section 4.2, we construct tie-decay networks with different decay coefficients, temporal interactions, and sparsities 3 to explore how these factors influence the outcome of disease spread. In Section 4.3, we discuss the periodic boundary condition B (τ) = B (τ+l) that we stated in Section 3 and check numerically how the choice of period l affects the epidemic threshold. In Section 4.4, we explore disease dynamics on tie-decay networks that we construct from empirical data. Finally, in Section 4.5, we compare the results on a tie-decay network that we construct from an Erdős-Rényi (ER) network with those on a traditional temporal network that we construct from binning interactions of the same ER network. This further motivates the use of tie-decay networks as a viable modeling framework for studying dynamical processes on temporal networks.

To simplify our notation, we use λ to denote the maximum infection probability λ max throughout this section.

To validate the epidemic-threshold condition (3.6) in Section 3, we construct a tie-decay network from an Erdős-Rényi (ER) network in the following way. Let G(N, p) be an instance of the G (N, p) ensemble of ER networks, where N is the number of nodes and p is the probability of an edge between each pair of nodes. To create a tie-decay network, we assign a sequence T e = t 1 ,t 2 , . . j. We generate the sequences of time stamps using an exponential waiting-time distribution with scale β . That is, the difference t k+1 − t k between two consecutive event times, t k and t k+1 , has a mean of β . We suppose that our tie-decay network starts from a tie-strength matrix B(0) with all edges of equal tie strength 0.5. The tie strengths then evolve continuously following (2.1). We increment the tie strength of edge e at each t i ∈ T e , and the strength of a tie decays exponentially when there are no interactions. We then discretize the tie-decay network (see our discussion in Section 2) and simulate an SIS process with maximum infection probability λ and recovery probability µ on this network.

In our numerical experiments in Figure 1 , we construct a tie-decay network from an instance G ER has a single connected component) and a tie-decay coefficient of α = 10 −1 . We generate interactions with an exponential distribution with scale β = 100, and the simulations each last 10 3 time steps. We simulate our SIS process on this tie-decay network with various infection and recovery probabilities that each range from 0.05 to 1. In Figure 1 , we show the outbreak sizes that we obtain at the end of our simulations and the associated critical value ρ cr (S) of the epidemic-threshold condition (3.6). In our examination of different pairs of infection and recovery probabilities, we observe transitions in both the final outbreak sizes and the critical values. In Figure 1b , for a fixed maximum infection probability λ , we highlight the recovery probability µ for which the critical value is closest to 1. We then highlight the same (λ , µ) pairs in Figure 1a . We observe for all of the (λ , µ) pairs that yield critical values less than 1 that the disease always dies out by the end of our simulations. This supports our theoretical result (3.6) that if ρ cr (S) is less than 1, then the disease-free state (in which no nodes are infected) is asymptotically stable. Because we perform our simulations on a network with finitely many nodes over finitely many time steps, there are some (λ , µ) pairs for which the critical values are slightly larger than 1 but have 0 final outbreak sizes. Typically, however, we observe that after critical values exceed 1, a larger critical value usually corresponds to a larger final outbreak size at the end of our simulations.

To further illustrate the correlation between the final outbreak size and the critical value of the epidemic-threshold condition, we plot their relationships as a scatter plot. In Figure 2a , we again work with the tie-decay network that we constructed from the network G (1) ER , the decay coefficient α = 10 −1 , and the scale β = 100. In the scatter plot, we see that when we reach disease-free state (i.e., when the final outbreak size is 0), most of the critical values of the epidemic-threshold condition are less than 1, which again agrees with our theoretical results in (3.6) . Additionally, when the final outbreak size exceeds 0, its value appears to be positively correlated with the critical value ρ cr (S) of the epidemicthreshold condition (3.6). We also study this correlation on tie-decay networks that we construct from the same network G

ER with different decay coefficients (α = 10 −1 , α = 10 −2 , and α = 10 −3 ) and scales (β = 10, β = 50, and β = 100). In Figure 2b , we show the Pearson correlation coefficient (PCC) between the final outbreak size and the critical value for each of these tie-decay networks. All of our scenarios have a PCC of at least 0.5, which confirms the strong positive correlation between the final outbreak size and the critical value ρ cr (S).

We just demonstrated (see Section 4.1) that the final outbreak size and the critical value ρ cr (S) of the epidemic-threshold condition (3.6) has a strong, positive correlation. Therefore, we can potentially use this critical value can potentially as an indicator of the scale of the spread of a disease. Because the critical value is an important quantity, we study how different factors influence disease spread on tie-decay networks by comparing their critical values. There are three primary parameter choices that influence the spreading dynamics: (1) the tie-decay coefficient α, which determines how fast tie strengths decay;

(2) the interaction frequency between nodes, which one can tune using the scale β of the exponential waiting-time distribution; and (3) the sparsity of the underling network, which we determine using the edge-creation probability p of an ER network. We have an intuitive expectation of how each of these features influences disease dynamics. For instance, when interactions take place more frequently, one usually expects a disease to spread more easily and hence to infect more people. When a network is sparse (i.e., there are many fewer edges in it than the maximum possible number of edges), it tends to be more difficult for a disease outbreak to occur. By computing the critical values of SIS processes on different tie-decay networks, we examine if our intuition is correct.

DECAY COEFFICIENT. We construct tie-decay networks using one network G

ER of the G (N, p) ER network ensemble with N = 100 nodes and edge-creation probability p = 0.05 (where we ensure that G

ER has a single connected component), and we generate time stamps for each edge using an exponential waiting-time distribution with scale β = 100. We then create three variants of this tie-decay network by using decay coefficients of α = 10 −1 , α = 10 −2 , and α = 10 −3 . In Figure 3 , we compute the critical values of SIS processes with different infection rates and recovery probabilities for each of these tiedecay networks. As in Section 4.1, we highlight the (λ , µ) pairs that have critical values that are closest to 1. This enables us to roughly divide the (λ , µ) parameter plane into two regions. For (λ , µ) pairs in the upper-right part of each plot in Figure 3 , the disease eventually dies out. For the rest of the (λ , µ) pairs, the initial infection tends to result in an outbreak. In Figure 3 , we observe that there are many more (λ , µ) pairs for which the disease dies out for α = 10 −1 than for α = 10 −2 and α = 10 −3 . For progressively smaller values of α, it becomes more likely for an outbreak to occur. A larger decay coefficient α leads to stronger tie strengths in the long run. (See the discussion in [1] .) This, in turn, makes it easier for a disease to spread because the transmission of an infection between two nodes is ER . For each fixed value of the maximum infection probability λ , the star symbol indicates the smallest recovery probability µ that gives a critical value that is closest to 1. The line signifies the rough boundary between critical values that are larger than 1 and those that are smaller than 1. We draw the lines manually to guide human eyes; we do not generate them using either mathematical reasoning or computations.

INTERACTION FREQUENCY. We also examine the influence of interaction frequency on disease spread in our SIS model. We construct tie-decay networks using the same ER network G (2) ER and a decay coefficient of α = 10 −2 . For each edge, we generate time stamps with an exponential waiting-time distribution with scales β = 10, β = 50, and β = 100. The interactions between nodes is the most frequent when β = 10; in this case, the mean time between two consecutive interactions is 10∆t, where ∆t is the duration of a time step. In Figure 4 , we observe that the dividing line for the epidemic threshold shifts gradually to the left for progressively larger values of β . We also observe this in the colors of the heat maps, for which a darker green indicates a larger critical value. For progressively larger values of β (i.e., for decreasingly frequent interactions between nodes), the number of grids that are covered in dark green also becomes smaller. In other words, when interactions between nodes occur more frequently, it is easier for a disease to spread through a population. SPARSITY OF THE NETWORKS. We construct tie-decay networks using three networks from the G (N, p) ER network ensemble with N = 100. The network G ER (which we also examined previously) has an edge-creation probability of p = 0.05, and the network G ER has an edge-creation probability of p = 0.02. We ensure that each of the three networks consists of a single connected component. We generate the time stamps for each edge from exponential distributions with decay coefficient α = 10 −2 and scale β = 100. We compare the dividing line of the epidemic threshold and the colors of the heat maps in Figure 5 . In the densest tie-decay network (which we construct using G 

In Section 3, we used the periodic boundary condition B (τ) = B (τ+l) , which requires the tie-strength matrix to be periodic in time with period l. However, for most tie-decay networks, such periodic behavior does not occur. Tie strengths increment instantaneously and decay continuously in time, so it would be very surprising for such periodicity to occur. Valdano et al. [40] proposed that as long as the datacollection time period l is long enough, the data gives 'an approximately complete reconstruction of the temporal network properties', and once hence ought to be able to accurately estimate the epidemic threshold of a contagion model on a temporal network, even if it constructed from empirical data. In our tie-decay networks, we demonstrate using numerical computations that one can characterize the outcome of an entire SIS process by computing the epidemic threshold over a time period that is smaller than the entire time span.

We simulate two SIS processes on a tie-decay network that we construct from the ER network G with a decay coefficient of α = 10 −1 . We generate the interactions from an exponential waiting-time distribution with scale β = 100. The first SIS process has a maximum infection probability of λ = 0.3 and a recovery probability of µ = 0.7, and the second SIS process has a maximum infection probability of λ = 0.4 and a recovery probability of µ = 0.6. We simulate each SIS process for 10 3 time steps.

If we compute the critical threshold ρ cr (S) using the period l = 10 3 , we obtain ρ cr (S 1 ) ≈ 0.816 for the first SIS process and ρ cr (S 2 ) ≈ 1.088 for the second SIS process. In Figure 6 , we plot the evolution of the critical values for different choices of the time period l. In Figure 6a , we see that although the critical value starts above the threshold and changes rapidly at first, it stabilizes after a fairly small The critical values ρ cr (S) that we compute for different time periods l for SIS processes. In each case, the SIS process occurs on a tie-decay network that we construct from the ER network G

ER with a decay coefficient of α = 10 −1 and interactions that we generate using an exponential waiting-time distribution with scale β = 100.

Because we compute the system matrix only for the first l time steps, instead of for the entire time span, the fast convergence of critical values also allows us to save computation time when computing estimates of the critical values of the epidemic-threshold condition. Let ρ cr (S (l) ) denote the estimated critical value that we compute when the period is l. For the numerical experiments in Section 4.1 and Section 4.2, we estimate the critical value for each period l until we satisfy the following stopping criterion: max k∈{l−9,...,l} ρ cr (S (k) ) − min k∈{l−9,...,l} ρ cr (S (k) ) 0.02. We usually finish this computation of critical values within about 100-200 time steps, which is much smaller than the 10 3 time steps when we conduct numerical simulations of SIS dynamics over the entire time span.

We now construct tie-decay networks using data from real-world examples and explore the dynamics of our SIS model on these networks. We consider two real-world data sets: (1) a workplace network of interactions between individuals in an office building in France between 24 June and 3 July in 2013 [11] and (2) a conference network of face-to-face contacts over 2.5 days between conference attendees during the ACM Hypertext 2009 conference [21] . For each data set, we use the time stamps of the interactions between people when we construct its tie-decay network. Given a data set, we initialize the state of a tie-decay network as follows: (1) we use the nodes that are present in the data set; (2) an edge exists between each pair of distinct nodes with an independent, homogeneous probability of 0.1 (i.e., we create a network from the ensemble G (N, 0.1), where N is the number of nodes), and we assign an initial tie strength of 0.5 to each edge that exists. For each data set, we consider only a single initial network. We use the time stamps from the empirical data for the interactions and hence to determine the evolution of the tie strengths. The ties decay exponentially with a decay coefficient of α = 10 −2 , and we increment the tie strengths whenever an interaction takes place. As before, we validate our theoretical results using numerical simulations of SIS dynamics, and we also examine the influence of different choices of the time period l on our computational estimates of the epidemic thresholds.

In Figure 7 and Figure 8 , we compare the final outbreak sizes and estimated critical values in the workplace network and the conference network, respectively. These two real-world examples are both fairly small; the workplace network has 93 nodes, and the conference network has 113 nodes. The interactions in the workplace network have a roughly periodic pattern, with individuals interacting more frequently during work hours than during other hours. The conference network (which also was used in Valdano et al. [40] to validate their epidemic threshold) has a different interaction pattern-for example, some individuals are in sequences of interactions during a short period of time, but then have few or no further interactions-than the workplace network because of the nature of a scientific conference. Despite the differences between the two real-world examples, we observe a strong correlation between the estimated critical values and the final outbreak sizes in both of them. Although the epidemicthreshold condition (3.6) does not explicitly state that a larger critical value corresponds to a larger number of nodes in the infected state at t = T (when we finish our simulations), this positive correlation tends to hold for both real-world networks. As in Section 4.1, we highlight the (λ , µ) pairs that yield critical values that are closest to 1 and we indicate their corresponding outbreak sizes. In both real-world examples, whenever the critical values fall below 1, the disease dies out at the end of a simulation. This supports our theoretical formulation of the epidemic-threshold condition in (3.6).

As we discussed in Section 2, to discretize time in the real-world networks, we choose a sufficiently small ∆t so that there are not too many interactions in the time interval ((τ − 1)∆t, τ∆t]. Specifically, for each of our real-world networks, we choose ∆t to ensure that the number of interactions in each time interval is no more than 10. In the workplace data set, interactions were recorded every 20 seconds, and we take ∆t to be 1000 seconds in our discretization. Interactions were also recorded every 20 seconds in the conference data set, but this time we take ∆t to be 200 seconds in our discretization. We define one time step ∆t differently in the two data sets because of distinct features that we observe in their contact patterns. In the workplace network, there are many time intervals without any interactions, so we use a coarse discretization to ensure that the evolution of tie strengths is meaningful. In the conference network, interactions are more frequent, so we use a finer discretization. After discretization, each of the real-world networks has about 1,000 time steps in total. For each network, we estimate the epidemic threshold using approximately one tenth of the entire time span; specifically, we use a time period of l = 100. For the workplace network, this choice entails examining the critical value of the epidemicthreshold condition using all contacts from the first day; for the conference network, we use all contacts from the first 5.5 hours. Our discussion in Section 4.3 suggests that data from the early stages of these temporal networks is sufficiently representative of the entire data set to allow us to successfully estimate the epidemic thresholds for the entire time span. Furthermore, for the workplace network, it is reasonable to assume that the contact patterns of the workers are somewhat periodic, with similar patterns during each work day. The contact patterns in the conference network also appear to have a somewhat periodic pattern, as there is a spike in the number of contacts approximately every 6 hours. In summary, for both networks, using the period l = 100 seems to give a good estimate of the epidemic threshold, as we observe a close relationship between the magnitudes of the critical values and the final outbreak sizes with this choice.

Our accurate estimations of critical values of the epidemic-threshold condition using only early times in disease dynamics suggests the possibility of control measures for slowing down the spread of a disease. For instance, government regulations such as rules for physical distancing (which is also called "social distancing") can decrease the interaction frequencies of social contacts. As we saw in Figure 4 , as we lower the interaction frequency β , the dividing line for the epidemic threshold shifts to the left. Therefore, for fixed infection and recovery probabilities, when the interaction frequency is sufficiently small, the critical value can become smaller than 1, so a disease outbreak is unlikely. Additionally, the use of personal protective equipment (PPE) like masks can reduce infection probabilities, thereby also leading to a decrease of the critical value of the epidemic threshold.

To highlight how features of tie-decay networks assist in the forecasting of epidemic outbreaks, we compare the epidemic thresholds that we obtain using a tie-decay network with ones that we obtain using a traditional temporal network that we construct from binning interactions in a time window. We also illustrate some challenges that arise if one simulates a model of disease spread on a network that aggregates all of the interactions into adjacent time windows of length w. This further motivates the use of tie-decay networks for studying spreading behavior on temporal networks.

To construct a traditional temporal network by binning interactions, we work with the ER network G (1) ER and the same sequence of interactions (with time stamps T e = t 1 ,t 2 , . . . for each edge e = (i, j)) that we used in Section 4.1. We build a traditional temporal network using adjacent windows of length w = 10 [5] . That is, we first divide the time span into adjacent, disjoint time windows (10(k − 1), 10k] and we then aggregate all of the interactions within each window. Let A k denote the adjacency matrix of the kth window (10(k − 1), 10k]. To make sure that it is reasonable to compare our results from using tie-decay networks with those from using traditional temporal networks, we also rescale the tie strengths of A k such that their sum is equal to the time-averaged sum of tie strengths B(t) within the kth time window. We then simulate an SIS process with a maximum infection probability of λ and a recovery probability of µ on the traditional temporal network that consists of the sequence {A 1 , A 2 , . . .} of adjacency matrices. Within the kth window (10(k − 1), 10k], we simulate the SIS process for 10 steps; within this window, the tie strengths are constant and given by A k−1 . Using methods that were designed for discrete temporal networks [35, 40] , we derive the epidemic-threshold condition for the traditional temporal network to be ρ cr (S ) = 1, where S ∏ k (1 − µ)I + λ max min{A k , 1} is the system matrix that is associated with the traditional temporal network and ρ cr (Θ ) denotes the spectral radius of the matrix Θ . As in our terminology for tie-decay networks, we refer to ρ cr (S ) as the "critical value" of the traditional temporal network.

In our comparison, we simulate an SIS process with different maximum infection probabilities λ and a fixed recovery probability of µ = 0.5 on the tie-decay network (see Section 4.1 for details of its properties) and the traditional temporal network that we construct from G (1) ER and the same sequence of interactions. In Figure 9 , we plot their critical values and final outbreak sizes versus the recovery probability. One major difference between the dynamics on the two types of networks is the magnitudes of their critical values. The critical values ρ cr (S) for the tie-decay network range from 0.64 to 3.40, whereas the critical values ρ cr (S ) for the traditional temporal network range from 0.94 to 1.06 and remain close to 1. The proximity of ρ cr (S ) to the threshold value 1 poses two challenges. First, although theoretical results [35] suggest that, as time t → ∞, one can successfully predict whether or not an outbreak will take place based on the epidemic-threshold condition, it may be difficult to obtain an accurate prediction in networks with finitely many nodes that one examines for only a finite amount of time. When the critical value is close to 1, even a very small perturbation can change whether or not an epidemic-threshold condition is satisfied. In Figure 9 , the critical value of the traditional temporal network exceeds 1 for λ 0.4, but we observe outbreaks only for λ 0.7. The second challenge is that the proximity of ρ cr (S ) to 1 also makes it difficult to discern the extent to which the critical values correlate with the final outbreak sizes. In Section 4.1, we examined the positive correlation between the critical value and final outbreak size for an SIS process on a tie-decay network. However, one can see in Figure 9 that such a correlation is less evident for an SIS process on a traditional temporal network.

Another difficulty in constructing a traditional temporal network is determining an appropriate timewindow length w (or multiple such lengths, if one allows them to be nonuniform) [36] . When one has prior knowledge of seasonality (or other regularity, such as periodicity) in data, it can be worthwhile to use a traditional network that is divided into a sequence of time windows. However, in many applications, such prior knowledge is typically not available. Modeling the spread of an infectious disease on a tie-decay network does not require tuning a time-window length, and it is thus worthwhile to investigate disease dynamics on tie-decay networks.

We studied the epidemic threshold of an SIS process on tie-decay networks, which model relationships between nodes in a way that distinguishes between tie strengths and interactions between the nodes. In these tie-decay networks, the tie strengths increase instantaneously when there is an interaction and decay continuously in time between interactions. We demonstrated how to mathematically formulate an SIS process on a tie-decay network and then derived the epidemic threshold of this process by extending methods that were designed for networks that consist of sequences of temporal snapshots. Based on our theoretical results, we performed numerical simulations on both synthetic and real-world networks to obtain several insights into SIS dynamics on tie-decay networks. First, we showed numerically that the epidemic-threshold condition is successful at estimating the final outbreak sizes in the numerical FIG. 9: The critical values and final outbreak sizes that we obtain from simulating an SIS process on a tie-decay network and on a traditional temporal network with a time-window length w = 10. We build the two networks using the same underlying ER network. (See the text for details.) The SIS process has a maximum infection probability of λ and a fixed recovery probability of µ = 0.5. In each network, we simulate the SIS process for 10 3 time steps. We repeat each simulation 10 times and report the means of the final outbreak sizes and critical values. We color the critical values and the final outbreak sizes for the tie-decay network in dark blue and those for the traditional temporal network in light blue. We mark the critical values with discs and the final outbreak sizes with triangles. The dotted red line marks the threshold value 1.

simulations. We also showed that the critical value of the epidemic threshold is positively correlated with the final outbreak size of a disease. Our numerical experiments on synthetic networks illustrated how various factors-the decay coefficient of the tie strengths, the interaction frequency between nodes, and the sparsity of a network-impact the spread of a disease on a tie-decay network. Our numerical experiments on the length of the time period over which we computationally estimate the epidemic threshold demonstrated the possibility of estimating the critical values of disease dynamics using data from the early stages of disease spread. Finally, we demonstrated that one can estimate the epidemic threshold successfully in tie-decay networks that one constructs from real-world contact data.

There are a variety of interesting ways to build on our work. When deriving the epidemic threshold of our SIS model on a tie-decay network, we first discretized the network using a sufficiently small time step and we then applied methods that were designed for discrete-time temporal networks. It is also important to extend approaches for deriving epidemic thresholds that were designed for continuoustime temporal networks (see [38, 41] ). Although the existing approaches to do this do not appear to be immediately applicable to tie-decay networks (because one cannot necessarily assume that the adjacency matrix at any time t commutes with the aggregated matrix up to time t due to the particular structure of tie-decay networks), it should be possible to modify them to incorporate the features of tie-decay networks. Another worthwhile research direction is to study epidemic thresholds in more complicated epidemic models, such as SEIR processes (and models of disease spread with many more compartments), on tie-decay networks. It is valuable to examine new approaches on simplistic models such as SIS processes and SIR processes, but realistic models of disease dynamics are typically more complicated [6] . When studying such models, it will be especially interesting to examine whether or not it is still possible to accurately estimate critical values of disease dynamics at early stages of disease spread. It is also relevant to compare disease dynamics on tie-decay networks to disease dynamics in different types of continuous-time network models (such as Hawkes processes [26, 48] ) that integrate a 22 of 24 Q. CHEN AND M. A. PORTER point process with a network of interacting entities. Because of the self-exciting properties of a Hawkes process, it produces interactions that cluster in time. Prior studies have illustrated that such burstiness in contact patterns impacts epidemic-threshold conditions [47] , so it will be interesting to investigate how to incorporate such point-process models into a tie-decay framework. Researchers continue to develop new types of temporal networks, and it is important to compare disease dynamics on tie-decay networks to such dynamics on these temporal networks. For example, as in the tie-decay networks that we employed, Gelardi et al. [10] recently examined temporal network data in the form of evolving weighted networks with edge weights that update from each interaction. However, unlike in our tie-decay networks, they took interconnections between social relationships into account. For example, an interaction between two individuals may simultaneously strengthen their relationship with each other while weakening their relationships with other individuals. It is important to explore how such interdependencies affect disease dynamics and other spreading processes.

Tie-decay networks in continuous time and eigenvector-based centralities

Modeling the spatiotemporal epidemic spreading of COVID-19 and the impact of mobility and social distancing interventions

2021) Describing, modelling and forecasting the spatial and temporal spread of COVID-19 -A short review

Absence of epidemic threshold in scale-free networks with degree correlations

Time-Dependent Complex Networks: Dynamic Centrality, Dynamic Motifs, and Cycles of Social Interactions

Mathematical Models in Epidemiology

Decay functions

Thresholds for epidemic spreading in networks

Mathematical formulation of multilayer networks

From temporal network data to the dynamics of social relationships

Data on faceto-face contacts in an office building suggest a low-cost vaccination strategy based on community linkers

Discrete-time Markov chain approach to contact-based disease spreading in complex networks

Diffusion dynamics on multiplex networks

Information diffusion in online social networks: A survey

Why COVID-19 models should incorporate the network of social interactions

Differential Equations, Dynamical Systems, and an Introduction to Chaos

Modern temporal network theory: A colloquium

Temporal network structures controlling disease spreading

Temporal Network Theory

Temporal networks

What's in a crowd? Analysis of face-to-face behavioral networks

Structure of growing social networks

Message passing approach for general epidemic models

Mathematics of Epidemics on Networks: From Exact to Approximate Models

Multilayer networks

Toward epidemic thresholds on temporal networks: A review and open questions

Predicting and controlling infectious disease epidemics using temporal networks

Epidemic outbreaks in complex heterogeneous networks

Epidemic processes in complex networks

Epidemic dynamics and endemic states in complex networks

Activity driven modeling of time varying networks

Dynamical Systems on Networks: A Tutorial

Virus propagation on timevarying networks: Theory and immunization algorithms

Probabilistic Inference in Ecological Networks: Graph Discovery, Community Detection and Modelling Dynamic Sociality

Percolation and epidemic thresholds in clustered networks

Epidemic Threshold in Temporally-Switching Networks

Temporal percolation in activity-driven networks

Analytical computation of the epidemic threshold on temporal networks

Epidemic threshold in continuous-time evolving networks

Forecasting elections using compartmental models of infection

Epidemic thresholds in dynamic contact networks

An evaluation of mathematical models for the outbreak of COVID-19

Predicting the epidemic threshold of the susceptible-infected-recovered model

Epidemic spreading on complex networks with general degree and weight distributions

Modeling memory effects in activity-driven networks

Point-process models of social network interactions: Parameter estimation and missing data recovery

We thank Eugenio Valdano for helpful discussions.