key: cord-1017401-ag77vg4n
authors: Bartesaghi, Paolo; Estrada, Ernesto
title: Where to cut to delay a pandemic with minimum disruption? Mathematical analysis based on the SIS model
date: 2021-01-04
journal: Mathematical Models & Methods in Applied Sciences
DOI: 10.1142/s0218202521500561
sha: d48a6dcac4dda03dcfe29a9d28961c4e385fea35
doc_id: 1017401
cord_uid: ag77vg4n

We consider the problem of modifying a network topology in such a way as to delay the propagation of a disease with minimal disruption of the network capacity to reroute goods/items/passengers. We find an approximate solution to the Susceptible-Infected-Susceptible (SIS) model, which constitutes a tight upper bound to its exact solution. This upper bound allows direct structure-epidemic dynamic relations via the total communicability function. Using this approach we propose a strategy to remove edges in a network that significantly delays the propagation of a disease across the network with minimal disruption of its capacity to deliver goods/items/passengers. We apply this strategy to the analysis of the U.K. airport transportation network weighted by the number of passengers transported in the year 2003. We find that the removal of all flights connecting four origin-destination pairs in the U.K. delays the propagation of a disease by more than 300%, with a minimal deterioration of the transportation capacity of this network. These time delays in the propagation of a disease represent an important non-pharmaceutical intervention to confront an epidemics, allowing for better preparations of the health systems, while keeping the economy moving with minimal disruptions.

Epidemics propagate through networks 21 . They include international transportation webs 8 , nationwide and urban commuting systems 1 , as well as face-to-face Fig. 1 : A toy network illustrating two communities (squares) connected by two paths of 2 and 4 edges, respectively. The toy model is used to illustrate the strategies of delaying disease propagation with minimum connectivity cost by cutting strategic edges in graphs.

The concepts stated before are clarified in the next sections of this paper, but they are used here to exemplify the lack of triviality of the problem in question. After the definition of all concepts and notation used in this work, we state and prove the main result, namely an approximate SIS model whose solution represents an upper bound to the exact solution of this model, which is always below the diverging solution of the linearized model. One of the main advantages of this upper bound, apart from representing a worse case scenario for the propagation of a SIS disease, is that it directly connects the structure of the network with the disease dynamics. That is, we show here that the upper bound found here for the SIS model can be expressed in terms of an exponential function of the adjacency matrix, which is known to capture the contributions of subgraphs of a network to a property, e.g., node infectivity, via the use of walks in graphs. These functions, known nowadays as communicability functions, have found many applications across the disciplines. Using our structural-transparent upper bound to the SIS model we study the propagation of a disease across the network of commercial airports in the U.K. We consider a network of airports with edges weighed by the number of passengers transported in year 2003. We devised here a strategy to remove edges in a network which delays the disease propagation with minimum disruption of the capacity of the network to reroute goods/items/passengers. For the U.K. airport network we found that by removing 4 edges, i.e, removing all flights connecting 4 pairs of origin-destination places, a disease can be delayed by more than 300% relative to the original network without disruption of the network efficiency to diffuse goods/items/passengers or to reroute them by shortest paths connections in the network. 

In this work we deal with the use of the SIS model, which is mathematically described in the next section. The reasons why we consider SIS instead of, for instance, the Susceptible-Infected-Recovered (SIR) model are presented in this section. In the Introduction we have mentioned our interest in modeling and understanding situations in which a pandemic, like the current SARS-CoV-2, is affecting the global population or a significant part of it. Like in most of complex systems we can model this situation from a multi-scale perspective. Let us simplify this setting and consider for instance the three scales illustrated in At the smallest of the three we have the physical contact between two individuals. At the intermediate one we have the potential contacts between a significant part of the population. At the largest scale we have the interconnection between regions of the world, e.g., airports, cities, countries, etc.

To model the transmission of a virus at the smallest of the three scales considered we need not only a simple epidemiological model, which considers whether one individual is infected and the other is susceptible or have being recovered from the disease. We also need to consider particle aerodynamics, the viral charge of the infected individual, the immunological situation of the susceptible one, etc. In the case of transmission of diseases like flu, SARS, or SARS-CoV-2, between individuals it is well-known that the most appropriate model is the SIR one. Pairwise approximations for SIR-type network epidemics are analysed, for instance, in Keeling and Eames 21 , in House and Keeling 20 and in Röst et al. 42 . An extension of the edge-based compartmental model to SIR epidemics with general but independent distributions for time to transmission and duration of the infectious period is proposed in Sherborne et al. 46 .

In modeling the intermediate situation, in case of viral diseases, it is customary to use modified SIR models, where the population is split into several compartments which include the classes of susceptible, infected and recovered. The reader is referred to the review 14 and references therein for details in the case of SARS-CoV-2. Now, in the case of the largest scale, we have some particularities which need to be considered. In this largest scale scenario the system is represented by a network in which the nodes are the countries, cities or airports. Let us consider the case of airports. Then, an airport is susceptible to the disease if none of the passengers in that airport at a given time is infected. This airport can become infected due to the fact that infected passenger(s) come from other nearest neighbor airports (see Fig.  3 (a)). It is clear that an airport cannot be considered "recovered" in the sense of creating immunity, at least in the absence of quarantines in this airport (which are not considered here). Therefore, an infected airport can become susceptible again if the infected passenger(s) that were located in that airport move away from it (see Fig. 3 (b)). This SIS strategy has been applied to similar situations for instance by Omić and Van Mieghem 36 who considered a city as a node which can have infection introduced over the air transportation network from other cities. In this scenario they considered the SIS model as the adequate modeling tool. In another work Matamalas et al. 29 used again SIS for the worldwide air transportation network, with the goal of identifying the most important connections between airports for the spreading of epidemics and evaluate the epidemic incidence after its deactivation. Sanders et al. 44 analyzed the spread of an infection disease through 23 subpopulations via (documented) air traffic data, and considering that the country is internationally quarantined. Similarly, Qu and Wang 40 , Scaman et al. 45 , Onoue et al. 37 , and Ruan et al., 43 , Meloni et al. 32 and Ye et al. 51 , among others, used SIS for modeling diseases propagating through airports in a network system.

We consider here (weighted) graphs Γ = (V, E, W, ϕ) where V is the set of vertices (nodes), E is the set of edges and W is a set of weights w ij ∈ W , such that w ij ∈ R + 13,34 . The weights are assigned to the edges by the surjective mapping ϕ : E → W . In the case of unweighted graphs we consider that w ij = 1 for (i, j) ∈ E. We always consider #V = n and #E = m. All graphs here are undirected, therefore their adjacency matrices A are symmetric. Let k i denotes the (weighted) degree of the node i. Then, k = [k 1 , . . . , k n ] T is the degree vector. The eigenvalues and eigenvectors of the adjacency matrix are designated, respectively, by λ i , i = 1, . . . , n, λ 1 > λ 2 ≥ · · · ≥ λ n and ψ i , i = 1, . . . , n. To complete the notation we use u = [1, . . . , 1] T as the all ones vector, U = uu T , 0 = [0, . . . , 0] T and I the identity matrix

In the implementation of compartmental epidemiological models we consider x i (t) to be the probability that node i is infected at time t 31 . For the whole network, we define the vector x(t) = [x 1 (t), . . . , x n (t)] T . We designate by p the initial probability of being infected, by q = 1 − p the initial probability of being healthy; β is the infection rate per link, γ the recovering rate, β e = β/γ the effective infectivity rate and τ the epidemic threshold, that is the critical effective rate above which the disease infects a non-zero fraction of the whole population.

We consider here a SIS epidemiological model on the graph Γ 22,31 . In this case an infected node can infect any of its nearest susceptible neighbors which then become infected with infection rate β > 0. The infected node can recover with recovery rate γ > 0 and become susceptible again (see Fig. 4 ). The evolution of the probability of getting infected for a node i is described by 31 :

where A ij are the entries of the adjacency matrix for the pair of nodes i and j, and N i is the set of nearest neighbors of i. In matrix-vector form, it becomes:

with initial condition x (0) = x 0 = pu. The following two results can be found in 31 and characterize the behavior of network SIS below and over the epidemic threshold, which we adapt here to the case of undirected networks only:

Theorem 3.1. If βλ 1 /γ < 1 we have the following results:

(ii) there exists a unique equilibrium point x ⋆ = 0 and it is exponentially stable; (iii) the linearization of the model around the point 0 is given bẏ

Theorem 3.2. If βλ 1 /γ > 1 we have the following results:

(ii) there exists an equilibrium point x ⋆ = 0, the epidemic outbreak, exponentially unstable;

(iii) there exists an equilibrium point x ⋆ = 0, the endemic state, exponentially stable such that:

Using similar notations as before, the Susceptible-Infected (SI) model is written as 31 :

which in matrix-vector form becomes:

with initial condition x (0) = x 0 . It is well-known that the linearization of the model around the point 0 is given by

which is exponentially unstable. Lee-Tenneti-Eun (LTE) 25 rewrote the SI equation as

which is equivalent to

They then considered the following linearized version of the previous nonlinear equation

They then proved the following result. 25

is the solution of the approximate model of LTE and

is the solution of the linearized model.

When t 0 = 0 and x i (0) = p, ∀i = 1, 2, . . . , N the previous equation is transformed toŷ

(3.14)

We start here by rewriting the SIS model in Eq. (3.1) with the use of the variables

. Then, we havė

which can be transformed tȯ

using Kronecker δ ij function.

Let us remark that f (y) = 1 − e −y is an increasing concave function. Then

Also g (y) = e y − 1 is an increasing convex function, such that

We can now apply these conditions to Eq. (4.2) to obtaiṅ

where we have called the upper boundŷ i . Using the notation settled for the initial conditions, this equation is written aṡ

or in matrix-vector form aṡ

It is straightforward to realize that (4.7) has the form: 

which can then be solved using the method of variation of parameters. Therefore we have our main result.

be, respectively, the solution of the exact, linearizedẋ (t) = (βA − γI)x (t), and approximate (4.7) SIS model, with the same initial conditions:

Then,

We will prove this result by two parts using the following Lemmas. We should remark that this result indicates that the solution of the approximate (4.7) SIS model represents an upper bound to the exact solution, which is always below the diverging solution of the linearized SIS model. Let us now prove the first part of this results using the following. 

which is equal to the solution for the SI Model by LTE in Eq. (3.14). Let us observe that for t → +∞,ŷ(t) → +∞ andx(t) → 1.

(iv) if β = 0 and γ = 0, the exponential term in equation (4.10) can be written as

where Λ is the diagonal matrix of the eigenvalues of A and M is the orthogonal matrix whose columns are the eigenvectors of A. As t grows to +∞, the diagonal exponential terms e (βqλi− γ q )t grows to +∞ if (βqλ i − γ q ) > 0. In particular, if (βqλ 1 − γ q ) < 0, no one of these terms grows to +∞ and the epidemic decays. Thus, we can identify a threshold given by the following condition:

such that τ = 1 q 2 λ1 is the threshold of this bound solution. Then, if β e < τ the epidemic decays; if β e > τ the epidemic grows. We should remark that as λ 1 increases (and so does the average degree in the network), condition above become stricter and the spread of epidemics is facilitated. Moreover, in general, τ is bigger than 1/λ 1 , which is the threshold in the exact solution of SIS Networked Model, and it approaches such a threshold as p decreases.

(4.17)

Proof. We focus on the above-the-threshold behavior, i.e., we assume

Then, because q < 1, we have that β e = β γ > 1 λ1 . Following Lemma A.1 by LTE (see Eq. (29) in 25 ), since the initial conditions are the same for the bound solution and the linearized process, i.e.,x (0) =x (0) = x 0 = pu, it is enough to prove that

for all t ≥ 0. Let us remind thatx (t) = 1 − e −ŷ ; then we have

Where to cut to delay a pandemic with minimum disruption? 13

for all t ≥ 0, where the inequality follows from e −ŷi < 1 for allŷ i ∈ [0, ∞]. By (4.10) we have

where B and b are given by Eq. (4.11) and Eq. (4.12), respectively. Since

we have

where the last inequality is justified by the fact that e (βqλi− γ q )t < e (βλi−γI)t and βA − γ q I u (βA − γI) u. This finally proves the result.

It is well-known that the linearized SIS model approaches the exact solution only when t → 0. This is the case particularly when β and γ are both small, and β > γ as can be seen in Fig. 5(a) , which refers to the toy network in Fig.  1 with parameters β = 0.004, γ = 0.001 and p = 1/12. Notice that we have used logarithmic scale in the time to specially highlight the short time behavior. In this case, it can be seen that the upper bound found here also coincides with the exact solution for short times. For longer times, the linearized solution quickly diverges, while our upper bound behaves appropriately and converges to the steady state almost as the same time as the exact solution. When, β < γ and both values are not so small, the situation is pretty different from the previous one for the linearized model. In this case, not even for very small times, the linearized solution coincides with the exact one as can be seen in Fig. 5(b) for β = 0.02, γ = 0.03 and p = 5/12. The upper bound found here coincides with the exact solution for a relatively long period of time and then converges to a steady state far from the 100% of contagion as expected for these given set of parameters. 

One of the main goals of network theory is to understand dynamical processes in terms of structural network properties. Here we use the upper bound found in this section for the SIS model to understand how the communicability between nodes in a network captures the propagation of a disease through the nodes and edges of the network. We start by setting B = qβA − γ q I = − γ q I − q 2 β e A =: − γ q D. Then we can rewrite the vector B −1 b − log q u in the following way:

In this way, solution (4.10) becomeŝ Let v = I − pD −1 u with elements v i = n j=1 I − pD −1 ij and let us set We then have the following result.

Lemma 4.3. The probability that a node i ∈ V in a graph is infected at a given time t is bounded by its total communicability R i 5 as

where R i (̺) = e ̺A u i and ̺ = qβt.

Proof. Based on the previous definitions we have that

For a given node i ∈ V we havē from which the solution immediately follows.

We should notice that, if γ → 0 then C → 1 andx i (t) → 1 − qe − p q (Ri−1) , which equals the LTE 25 solution of the SI model. We should also remark that, in this approximation, all the structural information determining the dynamics of the SIS process is stored in the variable R i . We can interpret structurally this index as follow. Let G (̺) = exp (̺A). Then, [15] [16] [17] . The important thing here is that A k ij counts the number of walks of length k between the nodes i and j. A walk of length k is any sequence of (not necessarily different) vertices v 1 , v 2 , . . . , v k , v k+1 such that for each i = 1, 2, . . . , k there is an edge from v i to v i+1 13 . When i = j the walk is known as closed. In the expression ofȳ i (t), R i (̺) describes every trajectory of the infective particle starting at the node i (and ending elsewhere) at a given time and under the fixed initial conditions. It is clear that with all the epidemiological parameters fixed,ȳ i (t) depends linearly on R i (̺) .

We consider that on the same graph Γ where the infective particle is diffusing, there are other desirable diffusive processes taking place, such as the diffusion of goods, items, and passengers, which move the economy. We consider that such goods are diffusing through the graph by means of all available walks connecting a pair of nodes i and j in exactly the same way as the infective particle is using them. Indeed, there are approaches to modeling the traffic on networks which use epidemiological models like SIS 3,26,35 .

Therefore, let us find which routes are more probable for the infective particle to travel through. They will be the same ones for the goods/items/passengers moving in the network. For that we start by defining the following difference:

which represents the difference between all those walks that start and end at the same vertex to those walks which go from one node to another 5 . The first two terms then represent the circulability of a diffusive particle around a given node, while the last represents the transmissibility between two nodes 2 . Before continuing we need a clarification here. In the definition of ξ ij (̺) we are considering the parameter ̺ used in SIS model of the disease propagation. However, we are expecting that this parameter ξ ij (̺) captures the mobility of goods/items/passengers in the network, not of the disease. In the particular cases we are studying here we do not have an estimation for the parameter ̺ for the mobility of goods/items/passengers. Additionally, we have the problem that the measure ξ ij (̺) is dependent on ̺. Therefore, to make comparable the results of the viral spreading and the mobility of goods/items/passengers we use in the calculations of the last the same parameter ̺ as for the first. The theoretical justification for this assumption is that we need ̺ ≪ 1 for the mobility of goods/items/passengers to avoid congestion problems at the nodes and the values used for the SIS dynamics fulfill this requirement. In 12 it was proved the following result.

Lemma 4.4. Let ξ ij (̺) for ̺ ∈ R be the difference between the circulabilities of a diffusive particle around the nodes i and j, and the transmissibility between both nodes. Then, ξ ij (̺) is a Euclidean distance between the corresponding nodes.

We should recall that both terms, circulability and transmissibility, contribute positively to the infection propagation through:

. Therefore, we aim here at the following task:

• How to decrease significantly R i (̺), and consequentlyx i (t), without increasing significantly ξ ij (̺), and consequently minimally affecting the network capacity to diffuse goods/items/passengers?

Although ξ ij (̺) could be a good proxy for the network capacity of transporting goods/items/passengers we should be aware that all the transport taking place in a network occurs through the paths connecting two nodes. That is, ξ ij (̺) does not necessarily indicate the route followed by an item from the node i to the node j. For finding such routes we need a geometrization of the graph. This is carried out by defining a length space on it 6,28 . Let us consider e = (i, j) as a compact 1-dimensional manifold with boundary ∂e = i ∪ j. Let the edge e = (i, j) be given the ξ ij (̺) metric such that

We now extend the metric on the edges of Γ via infima of lengths of curves in the geometrization of Γ . Then, the network becomes a metrically length space, which is locally compact, complete and geodetic 6 . Now define the "shortest diffusive path length" as:

where P is a path in Γ , i.e., a walk with repetition neither of vertices nor of edges, and the minimum is taken among all paths connecting the corresponding pairs of vertices. We can now define the capacity of a network to reroute goods/items/passengers after the removal of an edge e by:

whereC (Γ, ̺) is the mean shortest communicability path (SCP), that is the average of C ij (Γ, ̺) over all shortest diffusive paths connecting pairs of nodes in Γ , and Γ −e is the graph from which the edge e has been removed.

We are always interested in nontrivial edge removals here, i.e., those that do not disconnect the graph. Then, to respond to the main query formulated in the previous subsection we will consider edge-removal strategies that decrease significantly R i (̺), but do not increase significantly ∆C (Γ − e, ̺) . It is obvious that any strategy that increases the relative communicability between two vertices G ij (̺) will necessarily drops ξ ij (̺) . Unfortunately, it will also increase R i (̺) . The obvious strategy seems to drop G ii (̺) so that both R i (̺) and ∆C (Γ − e, ̺) diminish their values. However, very frequently dropping G ii (̺) also decreases G ij (̺) . Therefore, we cannot foresee at first hand a strategy that fulfill both requirements and we then implement a computational approach to investigate the problem. First, we start by defining the following term:

, (4.29) where ∆t ⋆ = (t ⋆ (Γ − e) − t ⋆ (Γ )) /t ⋆ (Γ ) and t ⋆ is the time at which every node in the network is infected, i.e., the steady state of the SIS process, where the maximum is obtained among all the edges of the graph. We must be aware of an important characteristic of this process. The term ∆C (Γ − e, ̺) depends on t, which means that O (e, t) is different for different times.

This means that the process of edge-removal is time-dependent, and we should go removing edges as the time of the evolution of the epidemic goes on. This is a very realistic scenario and reflect some of the difficulties found in the current COVID-19 pandemics, where the measures taken at a given time are not necessarily the optimal ones at another. In Algorithm 1 we provide the pseudo-code of the current implementation.

Input: The original network:

The downdating times: T k = k · a, k ∈ [0, m], a fixed time step;

The epidemic level ε. Output: The downdated network after m steps:

remove edge (i k , j k ) ∈ E k−1 from Γ k−1 and generate Γ k 13 return Γ m and X m (t)

It is time now to give some numbers and we will start by analyzing the toy model illustrated in Fig. 1 . The process evolves as follow. We consider the time evolution of the SIS model in which we observe the evolution of the ratio of infected nodes with time. At a given time, we make the following plot. For every potential edge-removal of interest, here made for every of the 16 edges of the graph, we plot ∆C (Γ − e, ̺) vs. ∆t ⋆ in a box as the one illustrated in Fig. 6(a) for t = 150. The points in the plot correspond to the effects produced by removing the corresponding edge. The radii and color of these points are proportional to the values of O (e, t = 150). It can be clearly seen that there are two groups of edges. In the upper-right corner we have all the edges whose removal change very much the capacity of the network to reroute goods/items/passengers. In the opposite corner we have all those edges whose removal increase the time for infecting the whole population with minimum disruption of network operational capacity. We can select here a given number of edges to be removed in dependence of other factors, of economic or logistical nature. We remove here one edge at a time. In this case we select the edge with the largest O (e, t = 150) which is the edge (2, 3) . This single removal increases the time at which the SIS dynamics infects the 90% of the whole population by 17.1% with a minimum change in the network capacity to operate, i.e., ∆C (Γ − e, ̺) ≈ 0.72%. This edge removal produces a change in the trajectory of the infection as observed in the plot Fig. 6(d) , which is marked by the point (2, 3) , which represents the edge removed.

We now continue observing the evolution of the epidemic until we decide the next intervention. In this case we decided to do it at t = 300 (we simply use similar periods of time here to make the interventions, in a real-life situation this can be done at irregular intervals). Notice that the value of ∆C (Γ − e, ̺) is dependent on the time at which we decide to make the plot. The new situation is observed in the plot Fig. 6(b) where the model informs us that the next best cut should be made at edge (2, 4) . The combined interventions of cutting edges (2, 3) and (2, 4) increases the time to reach 90% of infected population by 53.8%. If we translate this into days, for instance, it means to gain almost 54 days out of 100, which is very significant. Now the capacity of the network to operate has drop by 3.0%. The trajectory of the infection changes again at the point (2, 4) of the plot in Fig. 6(d) .

In Fig. 6 (c) we illustrate the result of the third intervention at t = 450, which indicates that the next cut should be made to the edge (3, 4) . The combined interventions which have removed three edges out of 16 in this toy network increases the time for infecting the 90% of the whole network by 160.4%(!). That is, by removing only 18.75% of edges, which does not disconnect the graph, we have more than duplicated the time that we now have to take actions during the epidemic, from 381 time units to 992 ones. All this by dropping only in 5.34% the total capacity of the network to operate in relation to normal conditions. The epidemic now follows the trajectory from the point (3, 4) in the plot in Fig. 6(d) . 

Here we consider the network of domestic flights between 44 commercial airports in the United Kingdom in the year 2003. This was the year in which the SARS epidemic was spreading across the world. The network consists of 220 weighted edges representing air internal routes between these 44 airports. The weights correspond to the number of passengers transported during that year between the corresponding airports. In Fig. 7 we show a representation of this network where the nodes are drawn with size and colors proportional to their weighted degrees-total number of passengers arriving/departing to/from that airport in 2003. The weighted degree w i and the "standard" degree k i , i.e., number of edges incident to the node i, are related to each other by means of a power-law relation: w ≈ e 10.46 k 1.419 with Pearson correlation coefficient r = 0.631. More importantly, rank correlation indicates that both indices rank the airports in very different ways. For instance, the Kendall τ coefficient between both indices is only τ ≈ 0.626. According to w the most "important" airport was Heathrow, which was visited this year by 6,176,092 passengers, representing 13.8% of all passengers traveling this year across the U.K. However, the degree of this node is only 9, possibly indicating its major role as an international hub and connecting only to those relevant national airports from which passengers can easily move to other places. On the other side of the coin we have the airports of Jersey and Aberdeen with degree 24 and 23, respectively. Each of them moved less than 3% of the total number of passengers in the U.K. this year. However, Jersey is a major touristic destination in the U.K. and Aberdeen has become an important work hub in the U.K. due to the oil industry. Thus, they receive flights from many different cities across the U.K., although the number of passengers is relatively low. Due to these differences between the weighted and unweighted degrees, we consider here the analysis of both versions of the U.K. airport transportation network for the propagation of a SIS disease and the implementation of edgeremoval strategies. We apply the edge-removal strategy described in this work for removals at t = 200, 400, 600, 800, 1000. In the case of the unweighted network, these removals correspond to the connections between the following pairs of airports (in order): Glasgow-Manchester; Belfast City-Manchester; Stansted-Edinburgh; Isle of Man-Manchester and Bristol-Guernsey. In total, the removal of these 5 connections increases the cumulative time for infecting the whole network -precisely to overcome the epidemic level of 90% of infected nodes -by 161.9% with a decrease of 0.25% in the capacity of the network to reroute goods/items/passengers. In contrast, the consideration of the number of passengers between the different airports produces a completely different picture. First, we need a normalization of the weighted adjacency matrix to make the edge weights comparable to those of the unweighted version. This is carried out by dividing the weighted adjacency matrix with the mean value of the edge weights in the network. In this way, both the unweighted and the normalized weighted adjacency matrices have the same mean. Using this strategy the order of removals is as follows: Heathrow-Edinburgh; Heathrow-Manchester; Heathrow-Glasgow and Heathrow-Belfast City. The fifth removal is not carried out as it is not necessary to drop to probability of infecting the whole network below 90%, which was the target of the experiment. The evolution of the mean probability that an airport gets infected at three different times is illustrated in Fig. 8 . By removing all the flights between Heathrow and Edinburgh we delay the time for infecting the whole network by 38.9%. The second removal increases this time to 88.9% and the third one increases it up to 194.4%. Finally, the cumulative removal of 4 connections increases the time to infect the whole network by 333.3%. How the capacity of the airport network to reroute goods/items/passengers has changed after these removals? The response is surprising! The remove of all flights between Heathrow and Edinburgh does not drop the capacity of the global network to diffuse goods/items/passengers and passengers through its nodes. In contrast, it increases this capacity by 9.9%. This is, of course, a consequence of considering that such goods/items/passengers move in the network in a completely diffusive way. If we consider that they move using the shortest paths, then we observe a drop in the capacity of the network equal to ∆l = 0.05%, i.e., the increase in the average shortest path length in the network after the removal. After the four removals previously described the network has increased its diffusive capacity by 3.6% with a drop in its capacity to deliver goods/items/passengers via shortest paths of 0.4%. In either way, the removal of these four inter-airport connections produces a remarkable delay on the propagation of the SIS disease in comparison with a very small affection of the network operative capacity.

We have also conducted experiments to show whether the previous results are dependent on the normalization scheme used for the weighted adjacency matrix. In Heathrow-Belfast C. 333.33 -3.60 0.407 Table 2 : Quantitative results of the edge-removal strategy using the passengersweighed version of the U.K. air transportation network with adjacency matrix normalized by the mean number of passengers in the network. this case we use two other normalization schemes, namely by dividing the weighted adjacency matrix by the maximum edge weight or by dividing it by the total sum of edge weights. In both cases the edges identified to be removed are the same as for the case of normalizing by the mean weight with the addition of a fifth edge to be removed, which corresponds to Belfast Int.-Liverpool. The time to infect the whole network increases by 286.4% and by 309.5% after the fifth removal using the two additional schemes of normalization, respectively. All in all, these experiments show that the results previously described using the mean-weight normalization of the adjacency matrix are not specific of this kind of normalization and stressed the importance of using passengers-weighted version of the airport networks.

Multiscale mobility networks and the spatial spreading of infectious diseases

Riskdependent centrality in economic and financial networks

A data-driven air transportation delay propagation model using epidemic process models

Matrix functions in network analysis

Total communicability as a centrality measure

Metric spaces of non-positive curvature

Tail risk of contagious diseases

The role of the airline transportation network in the prediction and predictability of global epidemics

The COVID-19 pandemic and the $16 trillion virus

Effects of non-pharmaceutical interventions on COVID-19 cases, deaths, and demand for hospital services in the UK: a modelling study

With COVID-19, modeling takes on life and death importance

The communicability distance in graphs

The structure of complex networks: theory and applications

COVID-19 and SARS-CoV-2. Modeling the present, looking at the future

Communicability in complex networks

Network properties revealed through matrix functions

An intracellular model of hepatitis B viral infection: An in silico platform for comparing therapeutic strategies

Estimating the effects of non-pharmaceutical interventions on COVID-19 in Europe

Insights from unifying modern approximations to infections on networks

Networks and epidemic models

Mathematics of epidemics on networks: from exact to approximate models

Edge removal in random contact networks and the basic reproduction number

Blocking simple and complex contagion by edge removal

Transient dynamics of epidemic spreading and its mitigation on large networks

Traffic flow prediction with big data: A learning approach based on SIS-complex networks

Sexual networks: implications for the transmission of sexually transmitted infections

Minimal webs in Riemannian manifolds

Effective approach to epidemic containment using link equations in complex networks

If the world fails to protect the economy, COVID-19 will damage health not just now but also in the future

On the dynamics of deterministic epidemic propagation over networks

Traffic-driven epidemic spreading in finitesize scale-free networks

Mathematical modeling of COVID-19 transmission dynamics with a case study of Wuhan

Networks: an introduction

Network-wide assessment of transportation systems using an epidemic spreading methodology

Pandemics and networks: the case of the Mexican flu

Event-triggered control for mitigating SIS spreading processes

A spatially heterogeneous network-based metapopulation software model applied to the simulation of a pulmonary tuberculosis infection

Initial economic damage from the COVID-19 pandemic in the United States is more widespread across ages and geographies than initial mortality impacts

SIS epidemic spreading with heterogeneous infection rates

Modeling COVID-19 scenarios for the United States

Pairwise approximation for SIR-type network epidemics with non-Markovian recovery

Integrated travel network model for studying epidemics: Interplay between journeys and epidemic

Perturbative solution to susceptible-infected-susceptible epidemics on networks

Dynamic treatment allocation for epidemic control in arbitrary networks

Blyuss and I. Z. Kiss, Mean-field models for non-Markovian epidemics on networks: from edge-based compartmental to pairwise models

Economic crisis as a consequence COVID-19 virus attack: risk REFERENCES 29

The effect of graph structure on epidemic spread in a class of modified cycle graphs

A new coronavirus associated with human respiratory disease in China

Suppressing traffic-driven epidemic spreading by edge-removal strategies

A network SIS meta-population model with transportation flow

Non pharmaceutical interventions for optimal control of COVID-19

A pneumonia outbreak associated with a new coronavirus of probable bat origin

The author thanks financial support from Ministerio de Ciencia, Innovacion y Universidades, Spain for the grant PID2019-107603GB-I00 "Hubs-repelling/ attracting Laplacian operators and related dynamics on graphs/networks".

Where to cut to delay a pandemic with minimum disruption? 25

We have developed an approximate solution to the SIS epidemiological model which represents an upper bound to the exact solution of that model. This upper bound has several important features: (i) it does not diverge as the linearized SIS model; (ii) it represents a worse-case scenario for the propagation of a SIS disease; (iii) its solution can be expressed in terms of the communicability function, allowing clear structure-dynamic relations. Using this model and its connection with the communicability function, we proposed here a general strategy for mitigating the effects of a disease propagation on a network with minimum disruption of network capacities to reroute goods/items/passengers. This strategy consists in removing some connections which are found to delay the propagation of a disease on the network but minimally altering the capacity of the network to diffuse items among its nodes or to reroute them by alternative shortest paths. As a proof of concept, we have studied the airport transportation network of U.K. in 2003, where the nodes represent airports and the edges represent the flight connections, weighed by the number of passengers transported this year, between them. We have shown that using the strategy proposed in this work, the removal of only 4 origin-destination pairs in a time-dependent way delays the propagation of an epidemic by more than 330% relative to the original network. This delay represent a very significant gain in time for preparations of health systems and non-pharmaceutical interventions to confront such epidemic. In addition, these removals alter minimally the capacity of the U.K. airport system to transport goods/items/passengers either in diffusive ways or via shortest-paths routing.Of course, the global spread of a virus, like SARS-Cov-2, is a multi-scale phenomenon and cannot be faced by any individual oversimplified strategy but it requires action at various different levels. 7, 18, 38 It is worth mentioning here the wider scopes of our intentions, not only related to epidemiology and virus propagation. The proposed methodology is flexible enough to adapt to very different contexts, like for instance dissemination of information, risk assessment in finance, and beyond.Indeed, the main emphasis of the current work has been on the mathematical, methodological side. We expect that the extension of this approach to other epidemiological models allow more realistic implementations to tackle this important kind of non-pharmaceutical interventions that mitigate the effects of epidemics in the future.