key: cord-0059921-75wjgufr authors: Zhao, Xunyi; Wang, Huijuan title: Suppressing Epidemic Spreading via Contact Blocking in Temporal Networks date: 2020-11-25 journal: Complex Networks & Their Applications IX DOI: 10.1007/978-3-030-65347-7_37 sha: 6153db796d5407af6e5ea1558f563888c9f9e960 doc_id: 59921 cord_uid: 75wjgufr In this paper, we aim to effectively suppress the spread of epidemic/information via blocking/removing a given fraction of the contacts in a temporal (time evolving) human contact network. We consider the SI (Susceptible- Infected) spreading process, on a temporal contact network to illustrate our methodology: an infected node infects a susceptible node with a probability [Formula: see text] when a contact happens between the two nodes. We address the question: which contacts should be blocked in order to minimize the average prevalence over time. We firstly propose systematically a set of link properties (centrality metrics) based on the aggregated network of a temporal network, that captures the number of contacts between each node pair. Furthermore, we define the probability that a contact c(i, j, t) is removed as a function of the centrality of the corresponding link l(i, j) in the aggregated network as well as the time t of the contact. Each of the centrality metrics proposed can be thus regarded as a contact removal strategy. Empirical results on six temporal contact networks show that the epidemic can be better suppressed if contacts between node pairs that have fewer contacts are more likely to be removed and if contacts happened earlier are likely removed. A strategy tends to perform better when the average number contacts removed per node pair has a lower variance. Strategies that lead to a lower largest eigenvalue of the aggregated network after contact removal do not mitigate the spreading better. This contradicts the finding in static networks, that a network with a small largest eigenvalue tends to be robust against epidemic spreading, illustrating the complexity introduced by the underlying temporal networks. Since the outbreak of the Covid-19, most countries have taken mitigation measures to stop or at least reduce the spread. Citizens reduce significantly their transportation and social activities and human contact in general. However, applying the same mitigation measure (e.g. everyone reducing their physical contact by 10%) to all citizens might not be the most efficient way to stop the virus's spread. The fundational question is which type of social contacts should be blocked in order to slow down the epidemic spreading. Human contact networks like face-to-face contact networks are in general evolving over time. In such so-called temporal networks, two nodes are connected at a given time step when they have a face-to-face contact. Physical contact networks become available thanks to the development of sensor and communications technologies. In contract to static networks, where links remain constantly active, the link between a node pair is active (or the two nodes have a contact) only at specific time steps in a temporal network. A temporal network G = (N , C) observed within a given time window [0, T ] among a set N of N nodes can be represented by a set of contacts C = {c(i, j, t), t ∈ [0, T ], i, j ∈ N }, where contact c(i, j, t) occurs between node pair (i, j) at time step t. In this work, we explore the question which contacts could be removed in order to suppress the epidemic spreading effectively. As a simple start, we consider the Susceptible-Infected (SI) epidemic model, which models information diffusion and epidemic spreading when the spreading is much faster than the recovery. Initially, a seed node is randomly selected and infected at t = 0, whereas all the other nodes are susceptible. An infected node infects a susceptible node with a probability β when a contact happens between the two nodes. The prevalence i.e. the percentage of individuals that are infected grows over time. The prevalence over time could be reduced via the removal of contacts. Such reduction in prevalence over time is used to quantify the effect of contact removal. In practice, the temporal contact network at large scale e.g. country level is likely unavailable. We assume that we could obtain the corresponding aggregated network G W , where two nodes i and j are connected by a link l(i, j) if the two nodes have at least one contact and the link is associated with a weight representing the number of contacts in between. We aim to design contact removal strategies based on the aggregated network. We propose systematically a set of link centrality metrics or properties based on the aggregated network. Furthermore, we define the probability that a contact c(i, j, t) is removed as a generic function of a centrality metric of link l(i, j) in the aggregated network and the time t of the contact. Each centrality metric thus leads to a different mitigation strategy to select the contacts to block. The average fraction φ of contacts to be removed is considered as a control parameter, indicating the mitigation cost. We evaluate the performance of all the strategies that we have proposed in 6 real-world temporal networks. We find that the epidemic prevalence can be better suppressed when contacts between node pairs that have fewer contacts are more likely to be removed, i.e. using the metric one over the number of contacts between a node pair. Removing contacts that happen earlier in time also further enhance the mitigation effect. The number of contacts between a node pair is heterogeneous. It seems that the mitigation effect is better if the average number of contacts removed per node pair varies less. Static network studies have shown that a weighted network tends to be more robust against epidemic spreading with respect to its epidemic threshold if its largest eigenvalue is smaller. The resultant aggregated network after contact removal, however, may have a lower prevalence if its largest eigenvalue is larger. This implies that the underlying temporal network may lead to new phenomena in epidemic spreading that differ from what we have learned from static networks. The influence of temporal networks on dynamic processes has been widely investigated [1] [2] [3] . Gemmetto et al. have studied the epidemic mitigation via excluding a sub-group of nodes in a temporal network [10] . Link blocking strategies using link centrality metrics to suppress information diffusion has been explored in [4] . The links to block are selected from the aggregated network. When a link is blocked, all contacts associated with the links are all removed. In this work, we investigate more in-depth at contact level, i.e. how to choose the contacts to block when the total number of contacts to block is given. Moreover, the consideration of the time of a contact in contact removal strategies may inspire the decision when a mitigation should be implemented. We propose firstly a set of link centrality metrics/properties based on the aggregated network G W . Furthermore, the probability that a contact is removed is defined step by step as a function of a given centrality metric and the time of the contact, which also ensures that a fraction φ of contacts are removed on average. We evaluate the effect of the mitigation strategies via the extent that the prevalence is reduced over time. An aggregated network G W can be constructed based on the temporal network G observed over time window [1, T ] . We propose the following link centrality metrics based on the weighted aggregated network: -Degree product: the product of the degrees of the two end nodes of a link, where the nodal degree is defined as the number of neighbors of a node. -Strength product : the product of the strengths of the two end nodes of a link, where the nodal strength is the sum of weights of all the links incident to the node, or equivalently the total number of contacts the node involves in the temporal network. For each metric m ij , we consider 1 mij as an extra centrality metric, except for the random. For any centrality metric, the centrality value of every link in the aggregated network is positive. The motivation to consider the reciprocal metrics 1 mij is explained in the design of the removal probabilities of contacts (2) . Link centrality metrics can be correlated [5, 6] . We find that the Spearman rank correlation between any two metrics proposed above is weak, i.e. below 0.2. This implies that each metric captures a specific property that can not be captured by another metric. For a given link centrality metric, we can compute the centrality for m ij for each link l(i, j). We propose the probability p ij that a contact c(i, j, t) between i and j is removed as where w ij is the weight of link l(i, j) in the aggregated network, and the normalization ensures that on average a fraction φ of contacts will be removed. The probability that a contact is removed is assumed to be proportional to the centrality m ij of the corresponding link l(i, j). We found that some centrality metrics are highly heterogeneous. Hence, it is possible that the removal probability calculated by (1) is larger than 1 for contacts whose associated link l(i, j) has an extremely large centrality m ij . In such cases, the actual fraction of contacts removed can be lower than the expected φ, if all contacts with removal probability larger than 1 are removed. Therefore, we set the removal probabilities of those contacts to 1 and re-normalize the removal probability among the rest contacts. This process is repeated until the removal probabilities of all remaining contacts are between 0 and 1, while the actual fraction of contacts removed is the same as expected φ. The probability p ij that a contact between i and j is removed can be defined in a more general way The removal probability of a contact between i and j is proportional to a polynomial function of m ij . Our choice in (1) corresponds to the case when α = 1. The random strategy, i.e. every contact has the same probability to be removed, corresponds to the case when α = 0. The choice of the reciprocal metric 1 mij in (1) is equivalent to the general definition (2) when metric m ij is considered and α = −1. Hence, we consider removal probability (1) using the list of centrality metrics proposed and their reciprocals as well as the random strategy, which correspond to the general definition of (2) where α = 1, −1, 0, respectively. Furthermore, we wonder whether removing contacts that happen earlier or introducing the mitigation intervention earlier in time would better reduce the prevalence. To take the time factor of the contacts into account, we propose the probability p ij (t) that a contact c(i, j, t) between i and j at t is removed as where f (t) implies the preference to block contacts at specific period. The prob- As a simple start, we consider f (t) = 4 · 1 t≤T /2 + 1 t>T /2 , f (t) = 1 t≤T /2 + 4 · 1 t>T /2 and f (t) = 1, where the indicator function 1 y is one is the condition y is true, and otherwise it is 0. These three functions corresponds to the preference to block contacts happening in [1, T/2], in (T /2, T ] and no preference over the time of the contacts, respectively. We consider six real-world temporal physical contact networks, measured in three scenarios: -HighSchool11&12 [7] capture the physical contacts between students in a high school in Marseilles, France. The two datasets consider two different groups of students. -WorkPlace13&15 [8] are the temporal networks of contacts between individuals measured in an office building in France. Different groups of individuals are considered in the two datasets respectively. -MIT1&2 [9] contain human contact data among students of the Massachusetts Institute of Technology. In order to keep the duration of the observation time window relatively comparable with the other networks, we randomly select two one-week periods as two temporal networks. All networks are considered as undirected. Some basic properties of the networks are shown in Table 1 . We consider as an example the infection probability β = 0.01, the probability that a susceptible gets infected by an infected node when they have a contact. This infection probability leads to a prevalence around the order of 10% by the end of the time window in each temporal network. For each centrality metric and each temporal network, we select each node in the network as a possible seed node. For each seed node, we iterate the following for five times. In each iteration, the fraction φ of contacts to be removed are selected according to the centrality metric thus the probability (1) using the given link centrality metric; The SI process starting from the given seed is performed on the temporal network where the selected contacts are removed; the prevalence ρ over time is recorded. For each network and centrality metric, we could obtain the prevalence at any time as the average over all possible seed nodes and the five iterations for each seed node. The fraction φ of contacts to be removed is a control parameter and φ = 10% and φ = 30% have been considered. Simulations are performed in the same way when the time factor f (t) are taken into account via the removal probability of a contact defined in (3). First of all, we evaluate the performance of all strategies as defined in (1) where the time of a contact has no influence on its probability of being blocked. The performance of the strategies in each network can be also compared via the average prevalence E[ρ] over the whole time window, as shown in Table 2 and 3, where φ = 10% and φ = 30% percent of contacts are removed respectively. The 1/link weight performs the best in all networks except for MIT2 and/or WorkPlace13. These observations imply that it is more effective to suppress the epidemic by removing contacts between node pairs that have few contacts. For any node pair (i, j), the average number of contacts removed between i and j is p ij w ij . For strategy 1/link weight, the average number of contacts removed is the same for all node pairs or for all links in the aggregated network 1 . We wonder whether a more similar number of contacts removed per node pair leads to a better mitigation effect. Hence, we derive further the variance V ar[p ij w ij ] for each strategy in each network. Figure 2( In the studies of the Susceptible-Infected-Susceptible SIS epidemic spreading model on a static weighted network, the largest eigenvalue of the weighted network has been shown to suggest the robustness of the network against epidemic [11] [12] [13] [14] . The infection rate between two individuals is assumed in the SIS model to be proportional to the infection rate of the epidemic multiply by , where matrix W with its element w ij captures the weights of all links in the aggregated network. When the effective infection rate, i.e. infection rate normalized by the recovery rate of the epidemic, is above the threshold, a none-zero fraction of the population gets infected in the meta-stable state, whereas below the threshold, the epidemic dies out in the meta-stable state. A static weighted network with a small largest eigenvalue tends to be more robust against epidemic. We explore further the largest eigenvalue λ 1 (W * ) of the resultant aggregated network after contact removal whose weighted adjacency matrix is W * . Would a strategy that leads to a smaller λ 1 (W * ) be more effective in suppress the prevalence according to the findings of SIS model on static networks? The scatter plot in Fig. 2(b) of the average prevalence E[ρ] versus λ 1 (W * ) shows the contrary: the prevalence tends to be low when the resultant network has a large largest eigenvalue. This inconsistency can be possibly introduced by the following. Removing many contacts from few links whose end nodes have a high strength may better reduce the largest eigenvalue. This is less effective in mitigation an SI spreading process where each link can transmit the epidemic maximally once dependent also on the time ordering of contacts. It can be, however, effective to mitigate an SIS epidemic where such links could transmit the epidemic frequently. Finally, we take the time of a contact into account when selecting the contacts to remove via the contact removal probability p ij (t) defined in (3) . When f (t) = 1 t≤T /2 +4·1 t>T /2 , contacts happening late i.e. t > T/2 in time are more likely to be removed. When f (t) = 4 · 1 t≤T /2 + 1 t>T /2 , contacts happening early i.e. t < T /2 are 4 times more likely to be removed compared to contacts happening late t > T/2. Comparing Table 3 , 4 and 5, where the contact removal is independent of the time of a contact, favors the removal of late and early contacts respectively, we find that the suppressing effect is better when early contacts are more likely to removed. Furthermore, the metric 1/link weight tends to perform the best independent of the choice of f (t). Hence, the mitigation effect tends to be better if contacts between node pairs that have few contacts and earlier contacts are more likely to be removed. Node pairs with few contacts are usually referred as weak social ties. Removing the contacts along weak social ties seems an effective and likely socially feasible mitigation strategy. In this work, we have introduced the methodology of suppressing the epidemic spreading via removing a given fraction of contacts in a temporal network. The choice of the contacts to remove is designed in a generic and probabilistic way. The probability that a contact c(i, j, t) is removed is a function of the centrality or property of the corresponding link l(i, j) in the aggregated network as well as the time t of the contact. A large number of relatively independent link centrality metrics have been considered. We find that removing the contacts between the node pairs that have few contacts and removing contacts in an earlier phase tend to suppress the prevalence more. This implies that the removal of contacts along weak social ties in an early phase tends reduce the prevalence more effectively. On the other hand, removing the large number of contacts of few node pairs is likely too costly to be effective. To illustrate the methodology, we have confined ourselves to the SI spreading model, limited number of real-world networks and limited choices of the parameters. Our methods may inspire further studies beyond the limited scenarios that we have considered. Our mitigation method is based on the aggregated network over the whole time window [1, T ] , when the mitigation is supposed to be carried out. It is interesting to explore whether we can estimate this aggregated network based on the observation of the aggregated network in the past. The performance of the mitigation strategies may depend on the properties of the underlying temporal networks. A fundamental question is which temporal network properties favor which mitigation strategies. This requires the expertise in the modeling of temporal networks and temporal network randomization. The effect of mitigation strategies depends as well on the relative spreading probability/rate. When an epidemic spreads extremely fast, e.g. all nodes have already been infected before T /2, the aggregated network information is likely not ideal to determine the contact removal probabilities, though this scenario is less realistic. Temporal networks Modern temporal network theory: a colloquium Information diffusion backbones in temporal networks Suppressing information diffusion via link blocking in temporal networks Correlation between centrality metrics and their application to the opinion model The correlation of metrics in complex networks with applications in functional brain networks Contact patterns among high school students Data on face-to-face contacts in an office building suggest a low-cost vaccination strategy based on community linkers Reality mining network dataset-KONECT Mitigation of infectious disease at school: targeted class closure vs school closure Virus spread in networks Effect of the interconnected network structure on the epidemic threshold Community networks with equitable partitions SIS epidemic spreading with heterogeneous infection rates