1 Convergence of Bi-Virus Epidemic Models with Non-Linear Rates on Networks - A Monotone

2025-04-28 0 0 2.12MB 17 页 10玖币

侵权投诉

Convergence of Bi-Virus Epidemic Models with

Non-Linear Rates on Networks - A Monotone

Dynamical Systems Approach

Vishwaraj Doshi, Shailaja Mallick, and Do Young Eun

Abstract—We study convergence properties of competing epi-

demic models of the Susceptible-Infected-Susceptible (SIS) type.

The SIS epidemic model has seen widespread popularity in

modelling the spreading dynamics of contagions such as viruses,

infectious diseases, or even rumors/opinions over contact net-

works (graphs). We analyze the case of two such viruses spreading

on overlaid graphs, with non-linear rates of infection spread

and recovery. We call this the non-linear bi-virus model and,

building upon recent results, obtain precise conditions for global

convergence of the solutions to a trichotomy of possible outcomes:

a virus-free state, a single-virus state, and to a coexistence state.

Our techniques are based on the theory of monotone dynam-

ical systems (MDS), in contrast to Lyapunov based techniques

that have only seen partial success in determining convergence

properties in the setting of competing epidemics. We demonstrate

how the existing works have been unsuccessful in characterizing a

large subset of the model parameter space for bi-virus epidemics,

including all scenarios leading to coexistence of the epidemics. To

the best of our knowledge, our results are the ﬁrst in providing

complete convergence analysis for the bi-virus system with non-

linear infection and recovery rates on general graphs.

Index Terms—Epidemics on networks, bi-virus models, multi-

layer graphs, monotone dynamical systems.

I. INTRODUCTION AND OVERVIEW

Graph-based epidemic models are widely employed to

analyze the spread of real world phenomena such as com-

municable diseases [2], [3], computer viruses, malware [4]–

[6], product adoption [7]–[9], opinions, and rumors [10]–[13].

The propagation of such phenomenon (which we cumulatively

refer to as epidemics or viruses) usually takes place via

processes such as human contact, word-of-mouth, exchange

of emails or even in social media platforms. Graph based

techniques, with edge based mechanisms to model information

spread, have therefore proven to be effective in capturing such

epidemic dynamics, and have been a research focus over the

past few decades [14]–[17]. In recent years, the development

of models which capture the competition of two or more of

such epidemics has seen a surge of interest. In particular,

models capturing the behavior of two competing epidemics of

Accepted for publication at IEEE/ACM Transactions on Networking, in

September 2022. A subset of the material in this paper appears in [1].

Vishwaraj Doshi is with the Operations Research Graduate Program,

Shailaja Mallick is with the Department of Computer Science, and Do

Young Eun is with the Department of Electrical and Computer Engineering,

North Carolina State University, Raleigh, NC. Email: {vdoshi, smallic,

dyeun}@ncsu.edu. This work was supported in part by National Science

Foundation under Grant Nos. CNS-2007423 and CNS-1824518.

the Susceptible-Infected-Susceptible (SIS) types, also known

as the bi-virus or bi-SIS models, have garnered signiﬁcant

attention over the years [8], [18]–[21].

Epidemic models take the form of ordinary differential

equations (ODEs) and their analysis involves the identiﬁcation

of ﬁxed points of the system, their uniqueness properties, and

ultimately showing the convergence of the solution trajectories

to those ﬁxed points. The technique via Lyapunov functions

has historically been a popular method to prove convergence

to ﬁxed points and was also used in epidemiology literature to

derive the convergence properties of the SIS epidemic model.

The SIS model was originally introduced in [2] to capture

the spread of Gonorrhea due to contact between individuals

in a population, and was further developed in [22]–[29].

The central result for SIS epidemics, originally proved using

Lyapunov functions in [2], is a dichotomy arising from the

relation between model parameter (τ > 0) representing the

effective infection rate or strength of the virus,1and a threshold

value (τ∗>0). When τ≤τ∗, the virus spread is not strong

enough and the system converges to a ‘virus-free’ state. When

τ > τ∗, it converges to a state where the virus infects a

non-zero portion of the population. Attempts have also been

made to perform similar convergence analysis for the bi-virus

epidemic model [8], [19]–[21]. The key questions posed in

such literature are: Can both competing epidemics coexist over

the network? If not, which one prevails? Or do both die out?

This trichotomy of possible results is what the recent literature

has been trying to characterize.

When the propagation of the two epidemics occurs over

the same network [8], [30], it has been established that

coexistence of two viruses is impossible except in the rare

cases where their effective strengths (τ1, τ2>0for viruses

1, 2, respectively) are equal [8], [18]–[21]; the virus with

the larger effective strength otherwise wiping out the other,

a phenomenon sometimes referred to as winner takes all

[8]. The situation is much more complicated when the two

viruses spread over two distinct networks overlaid on the same

set of nodes. This modeling approach is more representative

of the real world, where competing rumors/products/memes

may not use the same platforms to propagate, though they

target the same individuals. Recent works [18]–[21], [31]–[34]

therefore consider this more general setting, but unfortunately,

a complete characterization of the trichotomy of outcomes has

still proven to be elusive and remains open as of now.

1τ=β/δ, where β > 0stands for the infection rate of the virus and δ > 0

the recovery rate from the virus. Section II provides a detailed explanation.

arXiv:2210.05083v1 [eess.SY] 11 Oct 2022

While the original SIS model introduced in [2] had the

aggregate infection and recovery rates of a node as linear

functions of the number of infected neighbors, there has been a

push towards studying more generalized models where these

rates are made heterogeneous (across nodes) and non-linear

[35]–[39]. Realistic assumptions such as infection rates tend-

ing to saturation with continual increase in neighborhood in-

fection [40]–[43] have become more commonplace, implying

that the models employing strictly linear spreading dynamics

often provide overestimates to the real world infection rates

[20], [24]. This paper does not concern itself with answering

which non-linear infection rate best captures the exact dynam-

ics, but we direct the readers to [20] which provides simula-

tion results comparing non-linear rate functions to the exact

Markovian dynamics for some special randomly generated

graph topologies. In some special cases, non-linear recovery

rates also have an interpretation linking them to reliability

theory in the form infection duration with increasing failure

rates (failure here being the recovery of an infected node).

Allowing for non-linear infection and recovery rates leads to a

more general version of the bi-virus model on overlaid graphs,

albeit much more complicated, and the complete convergence

criterion is yet to be fully established [19], [20]. It should

be noted that while we extensively refer to the infection and

recovery rates being either linear or non-linear in this paper,

the bi-virus epidemic model itself will always be a system of

non-linear ODEs.

Limitations of existing works:Of all the recent works

concerning the spread of SIS type bi-virus epidemics on

overlaid networks, [20] and [19] provide conditions under

which the system globally converges to the state where one

virus survives while the other dies out. [20] approaches the

problem of showing global convergence by employing the

classic technique via Lyapunov functions. However, ﬁnding

appropriate Lyapunov functions is a highly non-trivial task,

and as mentioned in [19], is even more difﬁcult due to the

coupled nature of the bi-virus ODE system. This can be seen in

the condition they derive in [20] for the case where, say, Virus

1 dies out and Virus 2 survives. When τ1and τ2represent

the effective strengths of Virus 1 and Virus 2, respectively,

their condition translates to τ1≤τ∗

1where τ∗

1is the threshold

corresponding to the single-virus case, meaning that Virus 1

would not have survived even if it was the only epidemic

present on the network. More importantly, [20] is unable to

characterize convergence properties for τ1>τ∗

1and τ2>τ∗

The authors in [19] take a different approach and tackle

this problem by applying their ‘qualitative analysis’ technique,

which uses results from other dynamical systems that bound

the solutions of the bi-virus ODE; and provide conditions

under which the system globally converges to single-virus

equilibria. As we show later in Section V-B, however, their

conditions not only characterize just a subset of the actual

space of parameters that lead to global convergence to the

single-virus equilibria (which they themselves pointed out),

but the size of this subset is highly sensitive to the graph

topology, often much smaller than what it should be in general.

In other words, a complete characterization of the entire space

of model parameters, on which the system globally converges

to one of the trichotomic states, has still been recognized as

an open problem in the bi-virus literature [19]–[21].

Our contributions:In this paper, we analyze the bi-virus

model with non-linear infection and recovery rates (or the

non-linear bi-virus model in short) and provide the complete

characterization of the trichotomy of the outcomes with neces-

sary and sufﬁcient conditions under which the system globally

converges to one of the three possible points: (i) a ‘virus-free’

state, (ii) a ‘single-virus’ equilibrium, or (iii) an equilibrium

where both viruses coexist over the network. While the result

for convergence to the virus-free state of the bi-SIS model

is not new for non-linear infection and linear recovery rates,

our proof for the same is the most general form known to

date, covering the case with both infection and recovery rates

being non-linear. The proof of convergence to the virus-free

state of the bi-virus model is straightforward, and directly

follows from the convergence criterion for the single-virus SIS

model with non-linear rates. However, the convergence results

for ﬁxed points where only one of the two viruses survives,

or to the equilibrium where both viruses coexist, are not as

straightforward to establish, rendering the typical Lyapunov

based approach largely inapplicable.

In proving these results, we ﬁrst show, using a specially

constructed cone based partial ordering, that the bi-virus epi-

demic model possesses some inherent monotonicity properties.

We then use novel techniques from the theory of monotone

dynamical systems (MDS) [44] to prove our main results. In re-

cent control systems literature [45]–[49], techniques based on

the construction of cone based partial orderings that leverage

the monotonicity properties of dynamical systems have indeed

been studied. Dynamical systems exhibiting such monotonicity

properties are also sometimes called deferentially positive

systems [50] and cooperative systems [51] in the ODE set-

ting, with interesting applications in consensus problems for

distributed systems [52] and even neural networks [53]. In this

paper, we utilize these MDS techniques in the setting of com-

peting epidemics, and as a result demonstrate an alternative to

Lyapunov based approaches to analyze convergence properties

of epidemic models. The novelty of using the MDS approach

for analysis also lies with [54], which uses similar techniques

to analyze the bi-virus system for the special case of linear

infection and recovery rates, and was developed concurrently

and independently with the initial version of this work [1].

This further highlights the utility of MDS techniques for the

analysis of epidemic models on graphs.

This paper is an extension of our previous work [1], which

gives necessary and sufﬁcient conditions for convergence to

the three types of equilibria only for the special case of the

bi-virus model with linear infection and recovery rates (or

the linear bi-virus model in short). Our conditions therein

take a more precise form in terms of the model parameters

τ1and τ2and one can visualize an exact partition of the

model parameter space into regions corresponding to various

convergence outcomes. We note that this partition of the model

parameter space coincides with that in [18], wherein they

employed only local stability results via bifurcation analysis

– concerning only solution trajectories that originate from a

small neighborhood of those ﬁxed points. In contrast, our

results in this paper concern global stability of the system with

any combination of linear as well as more general, non-linear

infection and recovery rates.

Structure of the paper:In Section II, we ﬁrst introduce

the basic notation used throughout the paper, along with the

classical (single-virus) SIS model and the bi-virus model.

We then provide the generalization to non-linear infection

and recovery rates in Section III with some key assumptions

on the infection and recovery rate functions, complimented

by a discussion in Appendix C regarding a special class of

recovery rates. In Section IV, we provide a primer to the

MDS theory, and establish monotonicity results for the single-

virus SIS model, proving the convergence result for the single-

virus model with non-linear infection and recovery rates whose

proofs are deferred to Appendix E. We then go on to show

in Section V-A that the non-linear bi-virus model is also

a monotone dynamical system with respect to a specially

constructed cone-based partial ordering, and include the main

convergence results in Section V-B. In Section VI we take the

opportunity to provide a more intuitive version of our results

by considering the special case of linear infection and recovery

rates, along with brief comparisons with the existing literature.

In Section VII, we provide numerical results which conﬁrm

our theoretical ﬁndings. We then conclude in Section VIII.

For better readability of the paper, all technical proofs of

the main results are deferred to Appendix F. The appendices

also include some selected deﬁnitions and results from matrix

theory (Appendix A), ODE theory (Appendix B), and from

MDS theory (Appendix D), which we use as part of our proofs

of the Theorems in Section V-B.

II. PRELIMINARIES

A. Basic Notations

We standardize the notations of vectors and matrices by

using lower case, bold-faced letters to denote vectors (v∈

RN), and upper case, bold-faced letters to denote matrices

(M∈RN×N). We denote by λ(M)the largest real part2of

all eigenvalues of a square matrix M. We use diag(v)or Dv

to denote the N×Ndiagonal matrix with entries of vector

v∈RNon the diagonal. Also, we denote 1,[1,· · ·,1]T

and 0,[0,· · ·,0]T, the N-dimensional vector of all ones and

zeros, respectively. For vectors, we write x≤yto indicate that

xi≤yifor all i;x<yif x≤yand x6=y;xywhen all

entries satisfy xi<yi. We use G(N,E)to represent a general,

undirected, connected graph with N,{1,2,· · · , N }being

the set of nodes and Ebeing the set of edges. When we refer

to a matrix A= [aij ]as the adjacency matrix of some graph

G(N,E), it satisﬁes aij ,1{(i,j)∈E} for any i, j ∈ N ; we use

dmin(A)and dmax(A)to denote the minimum and maximum

degrees of the nodes of the corresponding graph. Since we

only consider connected graphs, all the adjacency matrices in

2We use the λnotation instead of something like λRe, since it will mostly

be used in cases where the largest eigenvalue is real, for which λitself is the

largest real eigenvalue. For example, λ(A)becomes the spectral radius for

any non-negative matrix A[55], [56].

this paper are automatically considered to be irreducible (see

Deﬁnition A.1 in Appendix A).

B. SIS Model with Linear rates

Consider the graph G(N,E), and assume that at any given

time t≥0, each node i∈ N of the graph is either in an

infected (I), or in a susceptible (S) state. An infected node can

infect each of its susceptible neighbors with rate β > 0.3It can

also, with rate δ > 0, be cured from its infection and revert to

being susceptible again. We write x(t)=[xi(t)] ∈RN, where

xi(t)represents the probability that node i∈ N is infected at

any given time t≥0. Then, the dynamics of the SIS model

can be captured via the system of ODEs given by

dxi(t)

dt ,β(1 −xi(t)) X

j∈N

aij xj(t)−δxi(t)(1)

for all i∈ N and t≥0. In a matrix-vector form, this can be

written as

dt ,βdiag(1−x)Ax −δx(2)

where we suppress the (t)notation for brevity. The system (2)

is positively invariant in the set [0,1]N, and has 0as a ﬁxed

point (the virus-free equilibrium). The following result is well

known from [2], which we will generalize in Section IV-B.

Theorem 2.1 (Theorem 3.1 in [2]): Let τ,β/δ. Then,

(i) either τ≤1/λ(A), and x∗=0is a globally asymptot-

ically stable ﬁxed point of (2);

(ii) or τ > 1/λ(A), and there exists a unique, strictly

positive ﬁxed point x∗∈(0,1)Nsuch that x∗is globally

asymptotically stable in [0,1]N\ {0}.

C. Bi-Virus Model with Linear rates

Consider two graphs G1(N,E1)and G2(N,E2), on the same

set of nodes Nbut with different edge sets E1and E2. At

any given time t≥0, a node i∈ N is either infected by

Virus 1,infected by Virus 2, or is susceptible. A node infected

by Virus 1 infects each of its susceptible neighbors with rate

β1>0, just like in the SIS model, but does so only to nodes

which are its neighbors with respect to the graph G1(N,E1).

Nodes infected by Virus 1 also recover with rate δ1>0,

after which they enter the susceptible state. Similarly, nodes

infected by Virus 2 infect their susceptible neighbors, this time

with respect to the graph G2(N,E2), with rate β2>0, while

recovering with rate δ2>0. This competing bi-virus model

of epidemic spread, also referred to as the SI1I2Smodel, can

be represented by the following ODE system:

dxi

dt ,β1(1 −xi−yi)X

j∈N

aij xj−δ1xi

dyi

dt ,β2(1 −xi−yi)X

j∈N

bij yj−δ2yi

(3)

3We say an event occurs with some rate α > 0if it occurs after a random

amount of time, exponentially distributed with parameter α > 0.

for all i∈ N and t≥0. In matrix-vector form, (3) becomes:

dt ,β1diag (1−x−y)Ax −δ1x

dt ,β2diag (1−x−y)By −δ2y,

(4)

where A= [aij ]and B= [bij ]are the adjacency matrices of

graphs G1(N,E1)and G2(N,E2), respectively.

III. EPIDEMIC MODELS WITH NON-LINEAR INFECTION

AND RECOVERY RATES

In this section, we introduce the single-virus and bi-virus

SIS models with non-linear infection and recovery rates. Non-

linearities can be attributed to the spread and recovery from

the virus being related to the susceptibility of the disease

(or its prevalence in the population) in a more complicated

manner. This is more general than simply exponential random

variables with constant rates used to model the spreading and

recovery processes, which in aggregate scale linearly with

the infection probabilities.4This is shown to be limiting in

accurately modelling the trajectories of an infection spread;

the linear scaling of the infection and recovery rates shown to

being an overestimate to what is observed in reality [20], [37].

Many works thus argue for the modelling of these spreading

processes with non-linear functions [35], [36], [38], [40]. We

ﬁrst present the more general single-virus SIS model with a set

of intuitive assumptions (A1)–(A5) for the non-linear infection

and recovery rates.

A. SIS Model with Non-linear rates

In (1) the term Pj∈N aij xj(t)denotes the overall rate at

which a susceptible node i∈ N gets infected by its neighbors.

In what follows, we replace this by a generic function fi(x(t)),

thereby allowing the overall infection rate for each node to

be any non-linear function of xj(t)for all neighbors jof i.

Similarly, we replace the term δxi(t), denoting the overall

recovery rate for any node i∈ N , by a non-linear function

qi(x(t)). This generic version of the SIS model, allowing for

non-linear infection and recovery rates, is given by the ODE

dxi(t)

dt =¯

fi(x(t)) ,(1 −xi(t))fi(x(t)) −qi(x(t)) (5)

for all i∈ N and t≥0. In a matrix-vector form, this can be

written as

dt =¯

F(x),diag(1−x)F(x)−Q(x)(6)

where F(x) = [fi(x)] ∈RN, and Q(x) = [qi(x)] ∈RNare

the vectors of non-linear infection and recovery rate functions,

respectively. We assume that they are continuous and twice

differentiable in [0,1]N, with JF(x)and JQ(x)denoting the

Jacobians of Fand Qrespectively, evaluated at any point

x∈[0,1]N. We now make the following key assumptions:

4‘Aggregate’ here refers to the mean ﬁeld approximation which is one way

to derive SIS-type ODEs. Another way is the large population mean ﬁeld

limit of a stochastic process, where the connection to the corresponding ODE

system is formed via the Kurtz’s theorem [16]. In this case, linearity is induced

by the uniform or homogeneous mixing assumption which is also a subject

of criticism in epidemiology literature [35]–[38].

(A1) F(0) = 0and Q(0) = 0;

(A2) [JF(x)]ij =∂fi(x)

∂xj>0∀i6=jwith aij >0, otherwise

[JF(x)]ij = 0;

(A3) [JQ(x)]ii =∂qi(x)

∂xi>0, and [JQ(x)]ij =∂qi(x)

∂xj≤0for all

i6=j,x∈[0,1]N. Moreover, P

j6=i

[JQ(x)]ij <[JQ(x)]ii;

(A4) fi(x)is concave in [0,1]N

, that is, ∂2fi

∂xj∂xk≤0for all

i,j,k ∈N ;

(A5) qi(x)is convex function of xi∈[0,1]N, and a concave

function of xjfor all j6=i. That is, ∂2qi

∂2xi≥0and

∂2qi

∂xj∂xk≤0for all i∈N , and j, k ∈N \{i}.

Assumption (A1) ensures that the virus-free state is a ﬁxed

point of (6), while (A2) is a proximity assumption that models

infection spread only through edges of the underlying graph.

Assumption (A3) concerns with the recovery rate, allowing

it to be reduced by infected neighbors while still being no-

negative. (A4) and (A5) assume concavity properties of the

functions fi(x)and qi(x)in xjfor any neighbor jof i. This

allows the effect of neighborhood infection xjto saturate5

as xjincreases. Assumption (A5) also assumes convexity of

qi(x)in local infection xi, which means that increase in

recovery rate caused by xican be larger as xiincreases.

Examples for non-linear infection rates satisfying

(A1)–(A5) include logarithmic functions fi(x) =

Pjaij ln (1 + xj), similar to those in [20]. Examples

of non-linear recovery rates include polynomial functions

such as qi(x) = (1 + xi)k−1for any k≥1. A special

class of the permissible non-linear recovery rates, where the

infection duration is dependent solely on local infection xi,

is related to processes that have decreasing failure rates

(DFR)6. This special class of recovery processes that are

DFR also includes the case of linear recovery rates. Note that

our assumptions allow fi(x)and qi(x)to be heterogeneous

across all nodes i∈ N , and the case with linear rates in (2)

readily satisﬁes (A1)–(A5). This also extends to the linear

bi-virus model (4) being a special case of the non-linear

bi-virus model introduced in the next subsection, with

infection and recovery rate functions therein satisfying the

same assumptions (A1)–(A5).

B. Bi-Virus Model with Non-linear rates

The Bi-Virus model with non-linear infection and recovery

rates is given by the following coupled system of ODEs:

dxi

dt = ¯gi(x,y),(1 −xi−yi)gi(x(t)) −ri(x)

dyi

dt =¯

hi(x,y),(1 −xi−yi)hi(y(t)) −si(y)

(7)

5As xjincreases for any neighbor jof node i, the magnitude of the

resulting change in both infection rate fi(x)and recovery rate qi(x)

decreases. This is similar to the case of diminishing returns.

6Failure rate for a non-negative random variable is deﬁned as the ratio be-

tween its probability density function (PDF) and its complimentary cumulative

distribution function (CCDF). In the context of infection duration, decreasing

failure rate means that nodes recover at a decreased rate the longer they stay

continuously infected. A more detailed discussion regarding the connection

to SIS recovery rates can be found in Appendix C.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

1ConvergenceofBi-VirusEpidemicModelswithNon-LinearRatesonNetworks-AMonotoneDynamicalSystemsApproachVishwarajDoshi,ShailajaMallick,andDoYoungEunAbstractWestudyconvergencepropertiesofcompetingepi-demicmodelsoftheSusceptible-Infected-Susceptible(SIS)type.TheSISepidemicmodelhasseenwidespreadpopularityi...

展开>> 收起<<

1 Convergence of Bi-Virus Epidemic Models with Non-Linear Rates on Networks - A Monotone.pdf

共17页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

1 Convergence of Bi-Virus Epidemic Models with Non-Linear Rates on Networks - A Monotone

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: