图数据挖掘:基于概率的流行病模型

1 导引

在上一篇博客《图数据挖掘:网络中的级联行为》中介绍了用基于决策的模型来对级联行为进行建模,该模型是基于效用(Utility)的且是是确定性的,主要关注于单个节点如何根据其邻居的情况来做决策,需要大量和数据相关的先验信息。这篇博客就让我们来介绍基于概率的传播模型,这种模型基于对数据的观测来构建,不过不能对因果性进行建模。

2 基于随机树的流行病模型

接下来我们介绍一种基于随机树的传染病模型,它是分支过程(branching processes)的一种变种。在这种模型中,一个病人可能接触(d)个其他人,对他们中的每一个都有概率(q>0)将其传染,如下图所示:
图数据挖掘:基于概率的流行病模型插图1
接下来我们来看当(d)(q)取何值时,流行病最终会消失(die out),也即满足

[lim _{h rightarrow infty} p_h=0
]

这里(p_h)为在深度(h)处存在感染节点的概率(是关于(q)(d)的函数)。如果流行病会永远流行下去,则上述极限应该(>0)

(p_h)满足递归式:

[p_h=1-left(1-q cdot p_{h-1}right)^d
]

这里(left(1-q cdot p_{h-1}right)^d)表示在距离根节点(h)深度处没有感染节点的概率。

接下来我们通过对函数

[f(x)=1-(1-q cdot x)^d
]

进行迭代来得到(lim _{h rightarrow infty} p_h)。我们从根节点(x=1)(因为(p_1=1))开始,依次迭代得到(x_1=f(1), x_2=f(x_1),x_3=f(x_2))。事实上,该迭代最终会收敛到不动点(f(x)=x),如下图所示:
图数据挖掘:基于概率的流行病模型插图2
这里(x)是在深度(h-1)处存在感染节点的概率,(f(x))是在深度为(h)处存在感染节点的概率,(q)为感染概率,(d)为节点的度。
如果我们想要传染病最终消失,那么迭代(f(x))的结果必须要趋向于(0),也即不动点需要为0。而这也就意味着(f(x))必须要在(y=x)下方,如下所示:
图数据挖掘:基于概率的流行病模型插图3
如何控制(f(x))必须要在(y=x)下方呢?我们先来分析下(f(x))的图像形状,我们有以下结论:

(f(x))是单调的:对(0 leq x, q leq 1, d>1)(f'(x)=q cdot d(1-q x)^{d-1}>0),故(f(x))是单调的。

(f'(x))是非增的(f'(x)=q cdot d(1-q x)^{d-1})会着(x)减小而减小。

(f(x))低于(y=x),则需要满足

[f'(0)=qcdot d

综上所述,我们有结论:

[lim _{h rightarrow infty} p_h=0 text { when } q cdot d

这里(R_0=qcdot d)表示每个被感染的个体在期望意义上所产生的新的病体数,我们将其称为基本再生数(reproductive number),它决定了传染病病是否会流行:

  • (R_0geq 1): 流行病永远不会消失且感染人数会以指数速度上升。
  • (R_0leq 1): 流行病会以指数速度快速消失。

3 SIR与SIS流行病模型

3.1 模型范式

在病毒的传播中,有两个最基本的参数:

  • 出生率(beta) 被已感染邻居攻击的概率
  • 死亡率(delta) 已感染节点治愈的概率

图数据挖掘:基于概率的流行病模型插图4
网络中的节点可以在以下四个状态(S+E+I+R)之间做转移:

  • 易感期(susceptible): 节点患病之前,处于容易被邻居传染的时期,也称敏感期。
  • 潜伏期(exposed):节点已被感染,但是还没具备能力去传染别人。
  • 传染期(infectious):节点已被感染,且能够以一定的概率把疾病传染给那些处于易感期的邻居,也称感染期。
  • 移除期(removed):当一个节点经历了完整的传染期,就不再被考虑了,因为它不会再受感染,也不会对其它节点构成威胁,也称隔离期。

状态转移图如下图所示(图中的(Z)表示人工免疫):
图数据挖掘:基于概率的流行病模型插图5
其中状态转移的概率由我们前面提到的模型参数(beta)(delta)控制。

3.2 SIR模型

在SIR模型中,节点经历S-I-R三个阶段:
图数据挖掘:基于概率的流行病模型插图6
事实上,该模型可用于对水痘和鼠疫的建模,也即一旦我治愈了,那我就永远不会再被感染了。

假设模型满足完美混合(即网络是完全图),则模型的动力方程为:

[begin{aligned}
&frac{d S}{d t}=-beta S I \
&frac{d R}{d t}=delta I \
&frac{d I}{d t}=beta S I-delta I
end{aligned}
]

处于(S)(I)(R)状态的节点数量随着时间变化曲线如下图所示:
图数据挖掘:基于概率的流行病模型插图7

3.3 SIS模型

SIS模型中节点只有S-I两个阶段,它假设已经治愈的节点会立即变为易感节点。节点的状态转移图如下:
图数据挖掘:基于概率的流行病模型插图8
这里我们把(s=frac{beta}{delta})定义为病毒的“力量”(strength)。

该模型可用于对流感的建模,也即已被感染的节点经过治愈后会重新回到易感状态。

同样我们假设模型满足完美混合(即网络是完全图),则模型的动力方程为:

[begin{aligned}
&frac{d S}{d t}=-beta S I+delta I \
&frac{d I}{d t}=beta S I-delta I
end{aligned}
]

处于(S)(I)状态的节点数量随着时间变化曲线如下图所示:
图数据挖掘:基于概率的流行病模型插图9

3.4 传染阈值

接下来我们考虑SIS模型中的传染阈值(epidemic threshold)(tau)。对于(SIS)模型而言,流行阈值可以是任意的。

我们设图(G)的传染阈值为(tau)。如果病毒的“力量”(s=frac{beta}{delta} (这里(beta)指病毒的死亡率,(delta)指病毒的出生率),则疾病的流行就不会发生(它最终会消失)。事实上,图(G)的传染阈值(tau)可以表示为

[tau=frac{1}{lambda_{1, A}}
]

这里(lambda_{1, A})为图(G)的邻接矩阵最大的特征值。这个定理看起来非常神奇,因为我们只用(lambda_{1,A})就捕捉到了整个图的属性!

以下是在AS图上,当(s)大于、小于或等于传染阈值(tau)时的感染节点数量随时间变化图:
图数据挖掘:基于概率的流行病模型插图10
如果我们再考虑不同的初始感染人数,则会得到以下的感染人数变化图像:
图数据挖掘:基于概率的流行病模型插图11

3.5 一个埃博拉的例子

在一个埃博拉的例子[1]中,设置如下的转换状态:
图数据挖掘:基于概率的流行病模型插图12

当设置(R_0=1.5text{-}2.0)时,总死亡人数随时间变化如下:
图数据挖掘:基于概率的流行病模型插图13

参考

[1] Gomes M F C, y Piontti A P, Rossi L, et al. Assessing the international spreading risk associated with the 2014 West African Ebola outbreak[J]. PLoS currents, 2014, 6.
[2] http://web.stanford.edu/class/cs224w/
[3] Easley D, Kleinberg J. Networks, crowds, and markets: Reasoning about a highly connected world[M]. Cambridge university press, 2010.
[4] Barabási A L. Network science[J]. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2013, 371(1987): 20120375.

posted @
2022-11-04 22:32 
orion-orion 
阅读(22
评论(0
编辑 
收藏 
举报

文章来源于互联网:图数据挖掘:基于概率的流行病模型

THE END
分享
二维码