In December 2019, a novel coronavirus (COVID- 19) was detected in Wuhan, China. This virus quickly spread throughout China, and before long, cases were reported across Asia. In March 2020, the World Health Organization (WHO) officially declared COVID-19 a pandemic [1]. While the economic ramifications of COVID-19 have been significant [2], the biggest cause of concern remains the growing number of fatalities worldwide, with over 35, 000 deaths being reported [3] as of March 30, 2020, and more fatalities daily. One of the factors that contributed to COVID-19 becoming a pandemic was the ability of individuals who were asymptomatic, or only slightly sick, to travel easily and great distances while being contagious. In this work we propose a model that allows for time-varying graph structure as well as mutating virus parameters. While COVID-19 does not appear to be a susceptible-infected-susceptible (SIS) virus, since infected individuals do not appear to become susceptible once they recover, other viruses and diseases such as the common cold, influenza, gonorrhea, and chlamydia, are of an SIS-type. Similar to influenza, it is possible that the novel coronavirus will mutate and therefore become more of an SIS virus. Consequently, we focus on mutating SIS models in this paper.
Network-dependent SIS models with static graphs have been studied extensively in the literature in continuoustime [4]- [6] and discrete-time [7]- [10]. These models have been extended to include time-varying graph structure for continuous-time models [11]- [14] and discrete-time models [15]- [17]. The work that most closely relates to the present paper is [17], wherein discrete-time periodic SIS models have been considered. Unlike [17], here we do not impose any periodicity assumptions. However, for heterogeneous virus spread over directed graphs, we assume that the variations in the topology are not too fast, whereas in [17] no such restrictions are imposed.
With respect to mitigating virus spread, there are a number of works in the literature [17]- [25]. The main goal of these works is to drive the system to the healthy state, the diseasefree equilibrium (DFE), or the origin; note, we use these terms interchangeably throughout the paper. Many of the previous techniques devise strategies for adjusting the healing rate in order to eradicate the virus, which can be interpreted as treatment efforts and/or antidote administration. We follow in the same vein and propose a technique that is inspired by [17]; however that technique required knowledge of the infection parameter, which we relax here. The strategies proposed in this paper depend on local network structure, the sampling parameter, and the state of the system (global knowledge for one algorithm and only local for the second), and are therefore driven by the virus spread data.
The overarching goal of the paper is to develop a datadriven control strategy which ensures that a mutating epidemic spreading over a time-varying network is eradicated. Towards this end, we first establish sufficient conditions for global -i.e., with respect to the physical meaning of the model considered -exponential stability (GES) of the DFE, and subsequently exploit the conditions to devise control algorithms. Consequently, the main contributions of the present paper are as follows:
i) We establish sufficient conditions for GES of the healthy state, that is, the origin or where the virus dies out; see Theorems 1 and 2. ii) We also provide two data-driven mitigation strategies for adjusting the healing rates, one that requires centralized state information and one distributed technique, that ensure the virus is eradicated asymptotically; see Theorems 3 and 4.
The paper is organized as follows. We conclude this section by listing the notation that is used in the paper. The problems being investigated are formally presented in Section II. The main findings of this paper are spread out over Sections III and IV: Section III establishes sufficient conditions for GES of the DFE, whereas Section IV presents the control algorithms -both centralized and distributedfor ensuring that the disease dies out. The theoretical findings are illustrated via simulations in Section V. Finally, we summarize our main contributions and shed light on some problems of possible interest for the automatic control and mathematical epidemiology communities in Section VI.
Let R and Z ≥0 denote the set of real numbers and nonnegative integers, respectively. For any positive integer n, we have [n] = {1, . . . , n}. Given a matrix A ∈ R n×n , the spectral radius is ρ(A). A diagonal matrix is denoted as diag(•). Given a vector x ∈ R n , its transpose is denoted as x . The Euclidean norm is denoted by • , whereas the infinity norm is indicated by • ∞ . The notation {A(k)} b a denotes a sequence of matrices A(k), where k ∈ {a, a + 1, . . . , b -1, b}.
Consider a time-varying network of n agents, where the set of agents remains the same at all times, while the interconnection among the agents are possibly time-dependent. Each agent has its own infection rate, denoted by β i , and healing rate, denoted by δ i . It is possible that the infection and healing rates are also time-dependent. At time t ∈ R, let x i (t) denote the infection level of agent i, and let a ij (t) denote the intensity of interconnection between agents i and j. The evolution of the infection level of an agent i can, then, be represented as follows:
For every t ∈ R, β i (t) > 0, δ i (t) ≥ 0 and a ij (t) ≥ 0. Note that for the SIS model considered above, the state x i (t) may correspond to an approximation of the probability of infection of i th agent [26], or the infected proportion of group i [27].
While the spread of an epidemic is a continuous process, the data relating to the epidemic is often collected periodically. For instance, during the recent outbreak of the novel coronavirus, Italy compiles its reports once every 24 hours. Such a sampling of the system behavior prompts us to look at discrete-time time-varying SIS models. The model is obtained by applying Euler's method [28] to (1):
where h > 0 is the sampling parameter.
Observe that, particularized for the time-invariant case, the continuous-time dynamics (as in ( 1)) is developed by using mean-field approximation of a Markov chain model; see [10], [26]. Since the discrete-time version of (1), is obtained by applying Euler discretization, ( 2) is an approximation of an approximation [10, Remark 1]. The approximation accuracy of (2) has been addressed, via simulations, in [29, Section 2.2.2].
In matrix form, we can rewrite (2) as:
where
for every i = 1, 2, . . . , n and for every j = 1, 2, . . . , n. Let us define B(k) := B(k)A(k), with its entries being denoted as βij (k).
With this notation in place, (3) can be rewritten as:
The spread of a virus over a network can be captured using graphs, where the nodes represent the agents, and the edges denote the interaction among the agents. More precisely, let G k = (V, E k ) represent this network, where V = 1, 2, . . . , n, and
Note that the subscript k indicates that we allow for different edges at each time step k, that is, time-varying graphs, which provides a more realistic model. We define the healthy state as the state where x i (k) = 0 for all i, which, from (4), implies that, for all i, x i (k 1 ) = 0 for all k 1 > k. Given that a population is infected with a virus, our main interest lies in ensuring that each agent i, regardless of whether it is initially healthy or sick, converges to the healthy state. Towards this end, we adopt a twopronged approach. First, we seek to establish conditions that ensure GES of the DFE. Second, we exploit these conditions to develop control strategies that eradicate the epidemic asymptotically. More formally, we can summarize our objectives as follows:
(i) For the system with dynamics as given in (4), under what conditions is the healthy state GES? (ii) Given the knowledge of the conditions that ensure GES of the healthy state, devise a data-driven approach that employs state information to set the healing rates and ensures that epidemic is eradicated asymptotically. We make the following assumptions. Assumption 1: For every i ∈ [n], hδ i (k) ≥ 0 and for all j ∈ [n], βij (k) ≥ 0, for every k ∈ Z ≥0 . Assumption 1 ensures that the healing (resp. infection) rate of each agent is non-negative.
Assumption 2:
Assumption 2 is essential for the model to be well-defined.
Note that x i is an approximation of the probability of agent i being sick, or can be interpreted as the percentage of subpopulation i that is infected. Therefore, for the model to be well-defined we need the following lemma. Lemma 1:
. For (4), under the conditions of Assumptions 1 and 2,
Proof: The proof is quite similar to that of [10, Lemma 1], and is, in the interest of space, omitted. Lemma 1 ensures that, with respect to system (4), the set [0, 1] n is positively invariant, i.e., once a trajectory of (4) enters the set [0, 1] n , it never leaves the set. Therefore for the rest of the paper we assume that the condition in Lemma 1 is satisfied, that is,
In this subsection, we will briefly recall some stability notions and results that are essential for understanding the findings in this paper.
Consider a system, described as follows:
where f :
Lipschitz. An equilibrium of ( 5) is said to be (uniformly) asymptotically stable if it is (uniformly) stable and (uniformly) attractive. Furthermore, an equilibrium of ( 5) is endowed with the property of GAS (resp. globally uniformly asymptotically stable (GUAS)) if, besides being asymptotically stable (resp. uniformly asymptotically stable), the system converges to that equilibrium for any initial state.
A stronger property is that of GES, which is defined as follows:
Definition 1: An equilibrium point of ( 5) is GES if there exist positive constants α and ω, with 0 ≤ ω < 1, such that
We recall a sufficient condition for GES of an equilibrium of (5) in the following Lemma 2: [30, Theorem 28, Section 5.9] Suppose there exists a function V : Z + × R n → R, and constants a, b, c > 0 and p > 1 such that a
and ∀x ∈ R n , then x = 0 is an exponentially stable equilibrium of (5).
The initial values are in the domain [0, 1] n , since otherwise they lack physical meaning; see Lemma 1. Therefore, it follows that the DFE of system (4) is GES if the condition in Definition 1 (resp. Lemma 2) is satisfied for all x k0 ∈ [0, 1] n .
This section addresses Objective (i) stated in Section II. That is, we establish sufficient conditions for GES of the DFE. Towards this end, we first consider undirected graphs with homogeneous virus spread, and subsequently the more general case, which accounts for directed graphs and heterogeneous virus spread.
We begin by defining the following:
Observe that M (k) is the state matrix obtained by linearizing (4) around the DFE, and will play a crucial role in our main results.
In this subsection, under the assumption that the infection rate is the same for every agent, and that the underlying graph is undirected, we provide a sufficient condition for exponential convergence to the healthy state.
Theorem 1: Let Assumptions 1 and 2 hold. Suppose that, for all k ∈ Z ≥0 , β i (k) = β(k) for every i ∈ [n], and that, for all k ∈ Z ≥0 , A(k) is symmetric. If sup k∈Z ≥0 ρ(M (k)) < 1, then the healthy state of (4) is GES. In words, Theorem 1 says that for a virus with homogeneous infection parameters spreading over undirected graphs, under Assumptions 1 and 2, if each pointwise eigenvalue of M (k) lies strictly within the unit disk, then the healthy state is GES. Proof: Consider the following Lyapunov function, V (k, x) = 1 2 x x. For x = 0 and for each k ∈ Z ≥0 , we obtain the following:
By assumption, β i = β for all i ∈ [n], and A(k) is symmetric. This implies that B(k) is symmetric, and hence M (k) is symmetric. Hence the matrix M (k) M (k)-I is symmetric. Therefore, by applying the Rayleigh-Ritz Quotient (RRQ) Theorem [31], we obtain
By assumption sup k∈Z ≥0 ρ(M (k)) < 1, which implies, by the definition of the supremum, that for every k ∈ Z ≥0 , ρ(M (k)) < 1 and hence (ρ(M (k))) 2 < 1, thereby implying ρ(M (k) M (k)) < 1.
Applying Weyl's inequalities [31,Corollary 4.3.15] to
and for each k ∈ Z ≥0 . Therefore, from (6), it follows that
where ( 9) is due to Assumptions 1 and 2, and (10) comes from Assumption 1 and Lemma 1. Thus, from Lemma 2 the DFE is GES, thereby concluding the proof. Note that Theorem 1 is the discrete-time counterpart of [14, Theorem 1].
In practice, it is not necessarily the case that each agent in a population has the same infection rate at each time step, since, for instance, different agents could have different immunity levels. Moreover, the underlying graphs could also be directed. That is, node i being connected to node j does not necessarily imply that the converse is true, or that the edge weightings are equal. Hence, in the next section we focus on finding conditions that also factor in heterogeneous virus spread over directed graphs.
In this section, we establish a sufficient condition for exponential convergence to the healthy state without the assumptions of homogeneous infection rates and symmetric interaction weights. Towards this end, we make the following assumption: the variation in the virus spread parameters and the topology is slow. A practical motivation for imposing such an assumption stems from the observation that one of the accelerating factors in the spread of an epidemic is the mobility of agents across large distances in a short amount of time, as shown during the recent COVID-19 pandemic [32]. That is, if these slow time-varying measures had been put into place, the pandemic possibly could have been prevented.
Theorem 2: Let Assumptions 1 and 2 hold. Suppose that i) for some α 1 > 0, sup k∈Z ≥0 ρ(M (k)) ≤ α 1 < 1;
ii) there exists L ∈ R + such that, for all k ∈ Z ≥0 , ||M (k)||≤ L; and iii) there exists κ ∈ R + such that sup k∈Z ≥0 ||M (k + 1) -M (k)||≤ κ. If κ is sufficiently small, then the healthy state of ( 4) is GES. In words, Theorem 2 says that under Assumptions 1 and 2, if the topology of G k is not changing too quickly, each pointwise eigenvalue of M (k) strictly lies within the unit disk, and the sequence of matrices {M (k)} ∞ 0 is bounded, then the healthy state is GES.
The proof of Theorem 2 follows almost immediately from that of the linear work in [33] and also, to a lesser extent, that of [34,Theorem 24.8]). In the interest of space, we omit the details; please see [35] for the complete proof.
Theorem 2 is the discrete-time counterpart of [14, Theorem 2], and differs from [17,Theorem 1] since no periodicity assumptions are imposed.
In this section we address Objective (ii) stated in Section II by proposing several control algorithms that eradicate the virus, using both centralized and distributed techniques. Notice that the eradication strategies developed in this section only account for homogeneous spread over undirected graphs. For the control inputs, we set the healing rates locally, δi (k). This approach can be interpreted as administering antidote and/or other treatment methods. The control inputs are designed, for all k ∈ Z 0 , i ∈ [n], as
where
and γ i (k) is a data-driven parameter, because it is updated using state information, and
The problem becomes the following: (11). Find f , where γ i (k) = f (γ i (k -1), x(k)), that drives the system to the healthy state.
From here on, we use δi (k) as shorthand notation for δi (k,
The first proposed solution to Problem 1 is a centralized scheme that updates γ(k) = γ i (k), for all i ∈ [n], as
with γ(0) = 0. This algorithm, combined with (11), implies that a central operator knows the sickness level of every node in the network and broadcasts γ(k) to each node at every time step. Each node then incorporates that into their healing efforts. Theorem 3: Consider the system in (2) and assume that,
Then the algorithm in ( 11)-( 12), with ψ i (k) = ψ(k) for all i ∈ [n], and (13) guarantees GAS of the healthy state. Proof: If there exists i ∈ [n] such that x i (0) > 0, by (13), γ(k) will increase and, as a consequence of ( 11)-( 12) and the assumption that
Hence, either the virus dies out asymptotically, or by ( 11) and ( 13), since η i > 0 for each i ∈ [n], each δi (k) will equal 1/h. Thus, at some finite time T ≥ 0, M (T ) = hBA(T ).
Therefore, for all k ∈ Z ≥T ,
where (14) holds by [31,Theorem 5.6.9] and (15) holds by the definition of the infinity norm and the assumption that hβ j a ij (k) < 1, for every k ∈ Z ≥0 . Thus by Theorem 1, the healthy state is GES for k ∈ Z ≥T . Therefore, since T is finite, the healthy state is GAS. Note that the proof does not tell us anything about the stability of the system for k < T . In fact, it is very probable that there are many k < T where ρ(M (k)) > 1. That is to say, in the time it takes to reach T , anything can happen, but after time T we have exponential stability. Therefore, exponential stability coupled with asymptotic time results in asymptotic stability. Next, we present another solution to Problem 1 that updates γ i (k) in a local, distributed fashion:
where γ i (0) = 0 and N i (k) denotes the set of neighbors of node i at time k, that is, N i (k) = {j | a ij (k) = 0}. This algorithm, combined with (11), implies that each node only includes information of their own sickness level and that of their neighbors, in their healing efforts. In practice, these are people that do not take outbreaks seriously until they become sick or someone they know becomes sick. Theorem 4: Consider the system in (2) and assume that
, and iii) A(k) is symmetric, irreducible for every k ∈ Z ≥0 .
Then the algorithm in ( 11)-( 12) and ( 16) guarantees GAS of the healthy state.
Proof: Consider an arbitrary node i. There are three possibilities: 1) node i and none of its neighbors ever become infected 2) node i or one of its neighbors is infected initially, or 3) one of node i's neighbors becomes infected at some time T 1 > 0. Note that the irreducibility assumption on every A(k) ensures that the underlying graphs, G k , are strongly connected for all k ∈ Z ≥0 . Therefore, in the first case, the virus has died out. In the second and third cases, for each i, at some point in time T 2 ≥ 0, an infected agent will be in the neighborhood of agent i and therefore γ i (k) will increase and, as a consequence of ( 11)-( 12) and the irreducibility assumption of A(k) for all k ∈ Z ≥0 , δi (k) will increase, for each i ∈ [n], unless ψ(k) = 1/h. Hence, since the virus does not die out asymptotically, by ( 11)-( 12) and ( 16), since η i > 0 for each i ∈ [n], δi will equal 1/h, for each i ∈ [n] at some finite time T ≥ 0. The rest of the proof is analogous to that of Theorem 3. Note that the main data-driven aspect of the approaches appears in the update of γ i (k) (and γ(k)). However, the control input is also determined by the time-varying graphs. Therefore, the algorithm is shifting resources, as needed, to the most congested areas, captured by the a ij (k) term in (11), as well as to the more sickly areas as captured by the local updates in (16).
In order to illustrate the results, we simulate a virus spreading over a time-varying graph. The positions of the agents are determined by piece-wise constant drifts and the graph structure is determined by the relative locations, similar to that used in [14] except with a discrete time framework. Namely, this approach confines the agents to a square of edge length l in R 2 , centered at some point z c .
where φ i (k) is updated as
for each dimension j ∈ [2]. That is, if an agent hits a boundary, the velocity of the agent in the dimension corresponding to that boundary flips sign. The initial positions are chosen uniformly at random inside the square, each initial φ i is chosen uniformly at random, and the initially infected agents are completely infected (x i = 1) and are chosen uniformally at random. We set n = 1000 and β = 1 for all i ∈ [n]. For the simulation without control, we set each δ i by sampling a uniform distribution between zero and one.
Using the aforementioned simulation parameters, we simulate three cases: 1) no control, 2) centralized control, as in (13), and 3) distributed control, using (16). The average infection level for each case and ρ(M (k)) are plotted in Figures 1 and 2, respectively. Consistent with Theorems 3 and 4, the control techniques eradicate the virus. As expected, the centralized technique outperforms the distributed technique, however, not significantly.
In this paper, we considered the problem of eradicating a mutating epidemic in a time-varying network. We first established sufficient conditions for GES of the DFE: simpler conditions for viruses with homogeneous infection rates over symmetric graphs, and more involved conditions for heterogeneous virus spread over directed graphs. Subsequently, by leveraging the first stability result, namely Theorem 1, we devised two data-driven approaches, one centralised and another distributed, which ensure that the epidemic is eradicated asymptotically. Finally, we illustrated our theoretical findings via simulations.
For future work, we would like to extend the ideas herein to SIR (susceptible-infected-recovered) and SEIRS (susceptible-exposed-infected-recovered-susceptible) models so as to possibly better capture the behavior of COVID-19. Another possible extension is to derive data-driven mitigation techniques that in addition to eradicating the virus simultaneously learn the infection parameter(s) of the system. It would also be interesting to devise control techniques, similar to those presented in Theorems 3 and 4, that also eradicate heterogeneous viruses over directed graphs.
Authorized licensed use limited to: IEEE Xplore. Downloaded on April 01,2022 at 15:16:25 UTC from IEEE Xplore. Restrictions apply.