1 导引
在上一篇博客《图数据挖掘:网络中的级联行为》中介绍了用基于决策的模型来对级联行为进行建模,该模型是基于效用(Utility)的且是是确定性的,主要关注于单个节点如何根据其邻居的情况来做决策,需要大量和数据相关的先验信息。这篇博客就让我们来介绍基于概率的模型,这种模型更关注系统整体,不过缺少对个体行为动机的刻画。
2 基于树的流行病模型
接下来我们介绍一种基于随机树的传染病模型,它是分支过程(branching processes)的一种变种。在这种模型中,一个病人可能接触\(d\)个其他人,对他们中的每一个都有概率\(q>0\)将其传染,如下图所示:
![迁移学习和多任务学习之间的区别](https://images.cnblogs.com/cnblogs_com/blogs/538207/galleries/2075236/o_221104021254_随机树模型.png)
接下来我们来看当\(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\),如下图所示:
![迁移学习和多任务学习之间的区别](https://images.cnblogs.com/cnblogs_com/blogs/538207/galleries/2075236/o_221104023117_f(x)不动点.png)
这里\(x\)是在深度\(h-1\)处存在感染节点的概率,\(f(x)\)是在深度为\(h\)处存在感染节点的概率,\(q\)为感染概率,\(d\)为节点的度。
如果我们想要传染病最终消失,那么迭代\(f(x)\)的结果必须要趋向于\(0\),也即不动点需要为0。而这也就意味着\(f(x)\)必须要在\(y=x\)下方,如下所示:
![迁移学习和多任务学习之间的区别](https://images.cnblogs.com/cnblogs_com/blogs/538207/galleries/2075236/o_221104032850_不动点多久为0?.png)
如何控制\(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)=q\cdot d<1 \]综上所述,我们有结论:
\[\lim _{h \rightarrow \infty} p_h=0 \text { when } q \cdot d<\mathbf{1} \]这里\(R_0=q\cdot d\)表示每个被感染的个体在期望意义上所产生的新的病体数,我们将其称为基本再生数(reproductive number),它决定了传染病病是否会流行:
- 若\(R_0\geq 1\): 流行病永远不会消失且感染人数会以指数速度上升。
- 若\(R_0\leq 1\): 流行病会以指数速度快速消失。
3 SIR与SIS流行病模型
3.1 模型范式
在病毒的传播中,有两个最基本的参数:
- 出生率\(\beta\) 被已感染邻居攻击的概率
- 死亡率\(\delta\) 已感染节点治愈的概率
![迁移学习和多任务学习之间的区别](https://images.cnblogs.com/cnblogs_com/blogs/538207/galleries/2075236/o_221103153958_病毒出生率和死亡率.png)
网络中的节点可以在以下四个状态(S+E+I+R)之间做转移:
- 易感期(susceptible): 节点患病之前,处于容易被邻居传染的时期,也称敏感期。
- 潜伏期(exposed):节点已被感染,但是还没具备能力去传染别人。
- 传染期(infectious):节点已被感染,且能够以一定的概率把疾病传染给那些处于易感期的邻居,也称感染期。
- 移除期(removed):当一个节点经历了完整的传染期,就不再被考虑了,因为它不会再受感染,也不会对其它节点构成威胁,也称隔离期。
状态转移图如下图所示(图中的\(Z\)表示人工免疫):
![迁移学习和多任务学习之间的区别](https://images.cnblogs.com/cnblogs_com/blogs/538207/galleries/2075236/o_221103155501_SEIR状态转移.png)
其中状态转移的概率由我们前面提到的模型参数\(\beta\)和\(\delta\)控制。
3.2 SIR模型
在SIR模型中,节点经历S-I-R三个阶段:
事实上,该模型可用于对水痘和鼠疫的建模,也即一旦我治愈了,那我就永远不会再被感染了。
假设模型满足完美混合(即网络是完全图),则模型的动力方程为:
\[\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\)状态的节点数量随着时间变化曲线如下图所示:
3.3 SIS模型
SIS模型中节点只有S-I两个阶段,它假设已经治愈的节点会立即变为易感节点。节点的状态转移图如下:
![迁移学习和多任务学习之间的区别](https://images.cnblogs.com/cnblogs_com/blogs/538207/galleries/2075236/o_221103161214_sis状态转移图.png)
这里我们把\(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\)状态的节点数量随着时间变化曲线如下图所示:
3.4 传染阈值
接下来我们考虑SIS模型中的传染阈值(epidemic threshold)\(\tau\)。对于\(SIS\)模型而言,流行阈值可以是任意的。
我们设图\(G\)的传染阈值为\(\tau\)。如果病毒的“力量”\(s=\frac{\beta}{\delta} < \tau\)(这里\(\beta\)指病毒的死亡率,\(\delta\)指病毒的出生率),则疾病的流行就不会发生(它最终会消失)。事实上,图\(G\)的传染阈值\(\tau\)可以表示为
\[\tau=\frac{1}{\lambda_{1, A}} \]这里\(\lambda_{1, A}\)为图\(G\)的邻接矩阵最大的特征值。这个定理看起来非常神奇,因为我们只用\(\lambda_{1,A}\)就捕捉到了整个图的属性!
以下是在AS图上,当\(s\)大于、小于或等于传染阈值\(\tau\)时的感染节点数量随时间变化图:
![迁移学习和多任务学习之间的区别](https://images.cnblogs.com/cnblogs_com/blogs/538207/galleries/2075236/o_221104015219_不同的s.png)
如果我们再考虑不同的初始感染人数,则会得到以下的感染人数变化图像:
![迁移学习和多任务学习之间的区别](https://images.cnblogs.com/cnblogs_com/blogs/538207/galleries/2075236/o_221104015557_调节初始值.png)
3.5 一个埃博拉的例子
在一个埃博拉的例子[1]中,设置如下的转换状态:
当设置\(R_0=1.5\text{-}2.0\)时,总死亡人数随时间变化如下:
![迁移学习和多任务学习之间的区别](https://images.cnblogs.com/cnblogs_com/blogs/538207/galleries/2075236/o_221104020617_ebola死亡人数变化.png)
参考
[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.