ON THE EPIDEMIC THRESHOLD OF A NETWORK V. Cherniavskyi1G. Dennis2S. R. Kingan3 Abstract. The graph invariant examined in this paper is the largest eigenvalue of

2025-05-02 0 0 3.29MB 13 页 10玖币

侵权投诉

ON THE EPIDEMIC THRESHOLD OF A NETWORK

V. Cherniavskyi,1G. Dennis,2S. R. Kingan 3

Abstract. The graph invariant examined in this paper is the largest eigenvalue of

the adjacency matrix of a graph. Previous work demonstrates the tight relationship

between this invariant, the birth and death rate of a contagion spreading on the

graph, and the trajectory of the contagion over time. We begin by conducting a

simulation conﬁrming this and explore bounds on the birth and death rate in terms

of well-known graph invariants. As a result, the change in the largest eigenvalue

resulting from removal of a vertex in the network is the best measure of eﬀectiveness

of interventions that slow the spread of a contagion. We deﬁne the spread centrality

of a vertex vin a graph Gas the diﬀerence between the largest eigenvalues of G

and G−v. While the spread centrality is a distinct centrality measure and serves

as another graph invariant for distinguishing graphs, we found experimental evi-

dence that vertices ranked by the spread centrality and those ranked by eigenvector

centrality are strongly correlated. Since eigenvector centrality is easier to compute

than the spread centrality, this justiﬁes using eigenvector centrality as a measure of

spread, especially in large networks with unknown portions. We also examine two

strategies for selecting members of a population to vaccinate.

Keywords: centrality measures, epidemics threshold, eigenvalues

1. Introduction

The well known Vertex Reconstruction Conjecture asks whether or not a graph G

with nvertices v1, v2, . . . , vncan be reconstructed from its deck of vertex-deleted

subgraphs G−v1, G −v2, . . . , G −vn. This suggests a vertex centrality measure. The

impact of vertex vcan be measured by removing it and considering the subgraph

G−v. Then various graph invariants can be calculated for Gand compared with the

corresponding parameters for G−v, thereby giving a ranking of the vertices. Not

every invariant has a practical application, but when it does, this approach gives a

meaningful centrality measure.

The parameter examined in this paper is the largest eigenvalue of the adjacency

matrix of the graph. The inverse of the largest eigenvalue is the epidemic threshold

in a non-linear dynamical system model of an epidemic spreading on a network of

people or animals and removing a vertex corresponds to vaccinating the vertex. See

for example [2], [6], [13], [16], and [17].

1Department of Mathematics, Brooklyn College, 2900 Bedford Avenue, Brooklyn, NY 11210.

2Department of Mathematics, Brooklyn College, 2900 Bedford Avenue, Brooklyn, NY 11210.

3Department of Mathematics, Brooklyn College, 2900 Bedford Avenue, Brooklyn, NY 11210, and

CUNY Graduate Center, 365 Fifth Avenue, New York, NY 10016.

arXiv:2210.14679v1 [cs.SI] 26 Oct 2022

2 ON THE EPIDEMIC THRESHOLD OF A NETWORK

The largest eigenvalue, also called the index or the spectral radius, is important for

several dynamic processes in addition to pandemics. For example, it is a key pa-

rameter in a virus spreading on a computer network, an idea spreading on a social

network, channel capacity in Shannon information theory, energy levels of electrons in

molecules, synchronization of coupled oscillators, stability of couplings in the brain,

etc. Hundreds of papers and multiple books have been written about the eigenvalues

of a graph and their applications. See for example [5] and [15].

In Section 2, we describe the epidemic threshold in detail and present the results of

our simulation of a disease spreading on a network with various parameters designed

to produce an outbreak that either grows to become an epidemic or dissipates. What

does an epidemic that lingers in a population look like as vertices get infected, recover,

and get infected again? What does an outbreak that dies out without becoming an

epidemic look like? We present a way of visualizing these very diﬀerent outcomes in

the same ﬁgure. The theoretical results in this section establish relationships between

graph parameters and epidemic parameters.

In Section 3 we deﬁne the spread centrality of a vertex in a graph Gas the diﬀerence

between the largest eigenvalues of Gand G−vand compare it to other centrality

measures. Although this idea has apeared informally in [2], [16], and [17], this is the

ﬁrst time it has been formally deﬁned as a centrality measure. It is the canonical

centrality measure quantifying spread in the network. We compared it to other cen-

trality measures with a surprising outcome. It is distinct from all known centrality

measures, and thereby of theoretical importance in distinguising graphs. However,

it does correlate with eigenvector centrality, thereby adding a previously unknown

supporting argument to the premise in [1] that eigenvector centrality is a good mea-

sure of spread. Finally, we also present two vaccination strategies and compare them

for eﬀectiveness. Through out the paper we focus on presenting rigourous results

whereever possible and identiﬁed avenues for further mathematical research.

2. Epidemic Threshold

There are two fundamental ways of modeling the spread of a disease, the SIS model

and the SIR model. In the SIS model, vertices have two states, susceptible (S) or

infected (I). A susceptible vertex becomes infected through an adjacent infected vertex

with probability pbcalled the birth rate of the virus. An infected vertex recovers with

probability pdcalled the death rate of the virus. In the SIS model a recovered vertex

can become infected again. It is assumed that a vertex is infectious as soon as it

becomes infected and becomes susceptible as soon as it recovers. In the SIR model,

vertices have three states: susceptible (S), infected (I), and removed (R). A susceptible

vertex becomes infected through an adjacent infected vertex and recovers (or dies)

and is removed from the network. For example, a disease like the ﬂu follows the

SIS model, whereas a disease like mumps where the patient becomes permanently

immune after recovery follows the SIR model.

These models when combined with information about the underlying network simu-

late the spread of diseases. Let Gbe a connected graph with n≥2 vertices and m

edges. Suppose a virus is spreading on G, where pbis the probability that the virus

spreads from one vertex to a vertex adjacent to it (the virus is born), and pdis the

ON THE EPIDEMIC THRESHOLD OF A NETWORK 3

probability that an infected vertex recovers (the virus dies). From epidemiological

studies, these numbers are very small, usually less than 0.1. An epidemic threshold is

a number τ(G) such that if pb

pd> τ(G),then the virus causes an epidemic, otherwise

it dies out without causing an epidemic [6].

Let A(G) be the adjacency matrix of graph Gand let the neigenvalues of A(G) in

descending order be λ1(G)≥λ2(G)≥ ··· ≥ λn−1(G)≥λn(G).Since A(G) is a real

symmetric matrix, the Perron-Frobenius Theorem implies that the largest eigenvalue

λ1(G) is a real number and it has the highest absolute value of all the eigenvalues.

If Ghas no edges, then the adjacency matrix is the zero matrix, and the eigenvalues

are 0. If Ghas at least one edge, then λ1(G)>0. If Gis connected, then λ1(G)>1

is an eigenvalue of multiplicity 1 and all the entries of its eigenvector have the same

sign. So we may consider the eigenvector to have all positive entries.

In [2], the authors developed a non-linear dynamical system (NLDS) model for virus

propagation on a network based on the SIS model. A system is considered unstable

if the ﬁrst eigenvalue of a certain matrix Massociated with the system is large and

stable otherwise. A small perturbation in a stable system will eventually die out. The

authors showed that for a graph Gand a contagion with birth and death probabilities

pband pd, respectively, spreading on the graph, the contagion will inevitably die out

if and only if pb

pd≤1

λ1(G). Let ptbe a vector of length nwhere the ith entry is the

probability that vertex iis infected at time t. If pt=0for some t, then pt+k=0

for all k≥0. They showed that the sequence p0,p1, . . . converges to 0if and only if

pd≤1

λ1(G), using a non-linear dynamical system relating pb,pd,Gand pt. Otherwise,

if pb

pd>1

λ1(G)the epidemic does not die out.

Theorem 2.1. Let Gbe a graph and let λ1(G)be the largest eigenvalue of its adja-

cency matrix. In NLDS, the epidemic threshold τ(G) = 1

λ1(G).

Consequently, the epidemic will die out over time irrespective of the size of the initial

outbreak of infection, if pd> λ1(G)pb.For example, the graph on the left in Figure

2, with 50 vertices and 250 edges, has largest eigenvalue 10.73 and therefore, if pd>

10.73pb, an epidemic spreading on the graph will die out over time. The graph on

the right, with 50 vertices and 1185 edges, has largest eigenvalue 47.42, and requires

pd>47.42pbfor an epidemic to die out.

3. Simulating an Epidemic

Three items are key to the simulation: the birth rate pbof the virus, the death rate

pdof the virus, and the underlying network G. The network gives λ1(G). The birth

rate of the virus, pb, is the probability that a vertex with one infected neighbor will

become infected over a unit of time. If vertex vhas iinfected neighbors, then perform

irandom draws with probability pb. In other words, draw a random number uniformly

between 0 and 1 and treat success as the event that the random number is less than

pb. Repeat this itimes because vertex vhas iinfected neighbors. Each random draw

is an independent event. If a positive result occurs in any draw, then vis infected.

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

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

10 玖币 0人已下载

立即下载

摘要：

ONTHEEPIDEMICTHRESHOLDOFANETWORKV.Cherniavskyi,1G.Dennis,2S.R.Kingan3Abstract.Thegraphinvariantexaminedinthispaperisthelargesteigenvalueoftheadjacencymatrixofagraph.Previousworkdemonstratesthetightrelationshipbetweenthisinvariant,thebirthanddeathrateofacontagionspreadingonthegraph,andthetrajectoryof...

展开>> 收起<<

ON THE EPIDEMIC THRESHOLD OF A NETWORK V. Cherniavskyi1G. Dennis2S. R. Kingan3 Abstract. The graph invariant examined in this paper is the largest eigenvalue of.pdf

共13页,预览3页

还剩页未读，继续阅读

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

ON THE EPIDEMIC THRESHOLD OF A NETWORK V. Cherniavskyi1G. Dennis2S. R. Kingan3 Abstract. The graph invariant examined in this paper is the largest eigenvalue of

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: