免疫策略(Immunization Strategy)

来自集智百科 - 伊辛模型
跳到导航 跳到搜索

此词条暂由Potatozh初译,未经审校,带来阅读不便,请见谅。


The fact that epidemic processes in heavy-tailed networks have a vanishing threshold in the thermodynamic limit, or a very small one in large but finite networks, prompted the study of immunization strategies leveraging on the network structure in order to protect the population from the spread of a disease. Immunization strategies are defined by specific rules for the identification of the individuals that shall be made immune, taking into account (local or nonlocal) information on the network connectivity pattern. Immunized nodes are in practice removed from the network, together with all the links incident to them, and each strategy is assessed by the effects of immunizing a variable fraction g of nodes in the network. The application of immunization does not only protect directly immunized individuals, but can also lead, for a sufficiently large fraction g, to an increase of the epidemic threshold up to an effective value $\lambda_c(g)>\lambda_c(g=0)$, precluding the global propagation of the disease. This effect is called herd immunity. The main objective in this context is to determine the new epidemic threshold as a function of the fraction of immunized individuals. Indeed, for a sufficiently large value of $g$, any strategy for selecting immunized nodes will lead to an increased threshold. We define the immunization threshold $g_c(\lambda)$, for a fixed value of $\lambda$ such that, for values of $g>g_c(\lambda)$ the average prevalence is zero, while for $g<=g_c(\lambda)$ the average prevalence is finite.


在度分布具有重尾的网络上,流行病的传播阈值在热力学极限下趋于零,而在有限却大尺度的网络中,传播阈值也只有很小的阈值。因此,这一事实促使人们通过结合网络结构来研究不同的免疫策略的作用,以便保护人们免受疾病流行性传播的影响。 免疫策略指的是在考虑到了网络的局域或全局的结构信息后,由特定规则定义的用于识别网络中应被免疫的个体的策略。免疫的节点实际上就相当于从网络上移除掉该节点和其相关联的连边。每种策略都可以通过免疫一定的$g$比例的网络中的节点的效果来评估。免疫的作用不仅可以保护被直接免疫的个体,而且对于足够大的$g$值来说,还可以增大传播阈值到$\lambda_c(g)>\lambda_c(g=0)$,从而防止了全局范围的疾病传播。这种效果称作群体免疫。在这种情况下的主要目标是确定新的传播阈值与免疫个体比例$g$之间的函数关系。实际上,对于足够大的g值,任何免疫策略都会使传播阈值增大。这里定义免疫阈值$g_c(\lambda)$,那么对于固定的$\lambda$值,当$g>g_c(\lambda)$,平均传播范围为零,反之则不为零。

随机免疫策略

The simplest immunization protocol, using essentially no information at all, is the random immunization, in which a number $gN$ of nodes is randomly chosen and made immune. While random immunization in the SIS model (under the DBMF approximation) can depress the prevalence of the infection, it does so too slowly to increase the epidemic threshold substantially. Indeed, from Eq. (20), an epidemics in a randomly immunized network is equivalent to a standard SIS process in which the spreading rate is rescaled as $\lambda\to\lambda(1-g)$, i.e., multiplied by the probability that a given node is not immunized, so that the immunization threshold becomes [1]

最简单的免疫策略是随机免疫,即不依赖任何信息,在网络中随机选择$gN$个节点使其免疫。虽然在SIS疾病传播模型中,由基于度的平均场理论近似可以得出这种策略可以降低感染的发生率,但该策略的效果太慢而无法大幅度提高传播阈值。在随即免疫策略中,疾病的传播等效于将经典的SIS的传播速率重新调整为$\lambda\to\lambda(1-g)$,即乘以网络中节点未被免疫的概率。因此免疫阈值就变为(Pastor-Satorras和Vespignani,2002b) \begin{equation} g_c(\lambda)=1-\frac{\left<k\right>}{\lambda\left<k^2\right>} \end{equation} For heterogeneous networks, for which $\left<k^2\right>$ diverges and any value of $\lambda$, $g_c(\lambda)$ tends to 1 in the limit $N\to\infty$, indicating that almost the whole network must be immunized to suppress the disease.

对于$\left<k^2\right>$发散的异质网络来说,对于任意的$\lambda$,$g_c(\lambda)$在$N\to\infty$时趋于1,这表明必须对整个网络进行免疫才能抑制该疾病的传播。

目标免疫策略

This example shows that an effective level of protection in heavy-tailed networks must be achieved by means of optimized immunization strategies [2], taking into account the network heterogeneity. Large degree nodes (the hubs leading to the large degree distribution variance) are potentially the largest spreaders. Intuitively, an optimized strategy should be targeting those hubs rather than small degree vertices. Inspired by this observation, the targeted immunization protocol proposed by Pastor-Satorras and Vespignani (2002b)[1] considers the immunization of the gN nodes with largest degree. A simple DBMF analysis leads to an immunization threshold given, for the SIS model, by the implicit equation [1]

随机免疫的这个例子表明,在度分布有重尾特征的网络中,考虑到网络的异质结构,免疫时必须使用优化过后的免疫策略才能实现有效的保护水平(Anderson和May,1992)。因为异质网络中大度节点是潜在的最大影响范围的传播者,因此,直观上来说可以采用将这些大度节点而不是小度节点免疫的一种优化的策略。受此启发,Pastor-Satorras和Vespignani(2002b)提出了将网络中$gN$比例的大度节点免疫的一种目标免疫策略。对于SIS模型,基于度的简单的平均场理论分析得出对应的免疫阈值由如下隐式方程给出(Pastor-Satorras和Vespignani,2002b) \begin{equation} \frac{\left<k^2\right>_{g_c}}{\left<k\right>_{g_c}}=\frac{1}{\lambda} \end{equation} where $\left<k^n\right>_{g}$ is the $n$th moment of the degree distribution $P_g(k)$ of the network resulting after the deletion of the $gN$ nodes of highest degree, which takes the form [3]

其中$\left<k^n\right>_{g}$是网络的度分布$P_g(k)$的第n阶矩,它是在删除度值最高的$gN$个节点后得到的,$P_g(k)$的形式为(Cohen et al。,2001) \begin{equation} P_g(k)=\sum_{k'\ge k}^{k_c}P(k')\dbinom{k'}{k}(1-g)^kg^{k'-k} \end{equation} Equation (64) can be readily solved in the case of scale-free networks. For a degree exponent $\gamma=3$, the immunization threshold reads 值$g_c(\lambda)\simeq exp[-2/(m\lambda)]$, where $m$ is the minimum degree in the network. This result highlights the convenience of targeted immunization, with an immunization threshold that is exponentially small over a large range of the spreading rate $\lambda$. A similar effect can be obtained with a proportional immunization strategy [1] [see also Dezsö and Barabási (2002)[4] for a similar approach involving the cure of infected individuals with a rate proportional to their degree], in which nodes of degree $k$ are immunized with probability $g_k$, which is some increasing function of $k$. In this case, the infection is eradicated when $g_k\ge1-1/(\lambda k)$, leading to an immunization threshold [1]

在无标度网络的情况下,上述免疫阈值的隐式方程很容易求解。当网络度分布指数$\gamma=3$时,免疫阈值$g_c(\lambda)\simeq exp[-2/(m\lambda)]$,其中$m$是网络中最小的度值。该结果突显出了目标免疫的便利性,其免疫阈值在传播速率$\lambda$的较大范围内呈指数减小。此外,采用比例免疫的策略也可以获得类似的效果(Pastor-Satorras和Vespignani,2002b)[另见Dezsö和Barabási(2002年)的相似方法,即以感染者的度值为偏好来治愈感染者的方案], 其中度值为$k$的节点以概率$g_k$被免疫,$g_k$是$k$的某种递增函数。在这种情况下,当$g_k\ge1-1/(\lambda k)$时,感染被完全消除,从而达到了免疫阈值(Pastor-Satorras and Vespignani,2002b) \begin{equation} g_c(\lambda)=\sum_{k>\lambda^{-1}}(1-\frac{1}{k\lambda})P(k) \end{equation} which takes the form $g_c(\lambda)\simeq(m\lambda)^2/3$ for scale-free networks with $\gamma=3$.

对于$\gamma=3$的无标度网络来说,其形式为$g_c(\lambda)\simeq(m\lambda)^2/3$。

Other approaches to immunization stress that not only the behavior close to the critical point should be taken into account, but also the entire prevalence curve (the so-called viral conductance) [5][6][7]. Additionally, strategies involving possible different interventions on different nodes have been analyzed within a game-theoretic formalism [8][9][10].

其他关于免疫策略的研究指出,不仅接近临界点附近的行为应该被考虑到,整个传播曲线也应该被考虑进去(所谓的病毒传导)(Kooij等,2009;Youssef,Kooij和Scoglio,2011; Van Mieghem,2012b)。此外,涉及对不同节点可能采取的不同干预措施的策略,也有研究者通过博弈理论进行相关的分析(Van Mieghem和Omic,2008; Omic,Orda和Van Mieghem,2009; Gourdin,Omic和Mieghem,2011)。

The previously discussed immunization protocols are based on a global knowledge of the network properties (the whole degree sequence must be known to selectively target the nodes to be immunized). Actually, the more a global knowledge of the network is available, the more effective is the immunization strategy. For instance, one of the most effective targeted immunization strategies is based on the betweenness centrality (see Sec. III.B.5), which combines the bias toward high degree nodes and the inhibition of the most probable paths for infection transmission [11]. This approach can even be improved by taking into account the order in which nodes are immunized in a sequential scheme in which the betweenness centrality is recomputed after the removal of every single node, and swapping the order of immunization in different immunization sequences, seeking to minimize a properly defined size for the connected component of susceptible individuals. This approach has been proven to be highly efficient in the case of the SIR model [12]. Improved immunization performance in the SIR model has been found with an “equal graph partitioning” strategy [13] which seeks to fragment the network into connected components of approximately the same size, a task that can be achieved by a much smaller number of immunized nodes, compared with a targeted immunization scheme.

刚刚讨论的免疫策略是基于已知网络的全局结构信息(必须知道整个网络的度序列从而选择性地选中要免疫的目标节点)。实际上,当网络的全局信息掌握得越多,目标免疫策略就越有效。例如,最有效的目标免疫策略之一是基于介数中心性(参见中间性B.5),其结合考虑了对大度节点的倾向性和对最可能的传播路径的抑制(Holme等 等人,2002)。该策略甚至可以通过考虑以下方式进行更好地改进:首先节点是按顺序被免疫的,在该方案中,每删除单个节点后就要重新计算剩下节点的介数中心性,然后在不同的免疫顺序中交换免疫顺序,以尽量减少连通的易感个体群体的大小。在SIR模型的情况下,这种方法已被证明是高效的(Schneider等,2011)。通过“等图分割”策略(Chen等,2008)研究者发现了SIR模型中的免疫性能提高了(Chen等,2008),该策略试图将网络分割成大小几乎相同的连通部分。该方案与目标免疫相比来书,可以免疫少得多的节点达到相同的效果。

基于局域信息的免疫策略

The information that makes targeted strategies very effective also makes them hardly feasible in real-world situations, where the network structure is only partially known. In order to overcome this drawback, several local immunization strategies have been considered. A most ingenious one is the acquaintance strategy proposed by Cohen, Havlin, and ben-Avraham (2003)[14], and applied to the SIR model. In this protocol, a number gN of individuals is chosen at random and each one is asked to point to one of his or her nearest neighbors. Those nearest neighbors, instead of the nodes, are selected for immunization. Given that a randomly chosen edge points with high probability to a large degree node, this protocol realizes in practice a preferential immunization of the hubs that results in being effective in hampering epidemics. An analogous result can be obtained by means of a random walk immunization strategy [15][16], in which a random walker diffuses in the network and immunizes every node that it visits, until a given degree of immunization is reached. Given that a random walk visits a node of degree ki with probability proportional to ki [17], this protocol leads to the same effectiveness as the acquaintance immunization.

由于真实网络的结构通常是只能知道局部信息而非全局信息,这使得目标免疫策略在真实网络的情况下的效果大大减弱。为了克服该缺陷,研究者考虑了几种局部免疫策略。 其中最巧妙的方法是Cohen,Havlin和ben-Avraham(2003)提出的熟人免疫策略,该策略已应用于SIR模型。此策略会在网络种随机选择$gN$个个体,并要求每个个体都指出他或她最近的邻居之一。然后,选择那些最近的邻居而不是那$gN$个个体来进行免疫。考虑到随机选择的边有很大的概率会指向大度的节点,该策略在实际操作中实现了对大度节点的优先免疫,从而可以有效地抑制流行病的传播。类似的,也可以通过随机游走免疫策略获得类似的结果(Holme,2004; Ke和Yi,2006),其中随机游走者在网络中扩散并对其访问的每个节点进行免疫,直到达到给定的免疫比例。鉴于随机游走是以与$k_i$成正比的概率访问度为$k_i$的节点(Noh and Rieger,2004),该方案产生的效果与熟人免疫策略相同。

The acquaintance immunization protocol can be improved by allowing for the consideration of additional information, always at the local level. For example, allowing for each node to have knowledge of the number of connections of its nearest neighbors, a large efficiency is attained by immunizing the neighboring nodes with the largest degree [18]. As more information is available, one can consider the immunization of the nodes with highest degree found within short paths of length l starting from a randomly selected node [19]. The random walk immunization strategy, on the other hand, can be improved by allowing a bias favoring the exploration of high degree nodes during the random walk process [20]. Variations of the acquaintance immunization scheme have also been used for weighted networks.The acquaintance immunization for weighted networks is outperformed by a strategy in which the immunized neighbors are selected among those with large edge weights [21].

当然,也可以通过考虑其他网络结构上的局域信息来进一步改进并优化熟人免疫策略。例如,允许每个节点了解其最近邻邻居的度值,则可以通过对其最大度的邻居节点进行免疫来获得很好的免疫效果(Holme,2004)。当能获取到更多有用的信息时,人们可以考虑对从随机选择的节点开始的长度为$l$的最短路径中,采用将发现的最大度的节点进行免疫的接种策略(Gomez-Gardenes,Echenique和Moreno,2006)。另一方面,随机游走免疫策略则可以通过在随机游走过程中允许偏向于度大的节点来进行改善和优化(Stauffer and Barbosa,2006)。熟人免疫策略可以通过适当的改变后用于有权重的网络。权重网络的熟人免疫在策略上表现出色,该策略是从边权重较大的邻居中选择要被免疫的邻居(Deijfen,2011)。

A different approach to immunization, the high-risk immunization strategy, applied by Nian and Wang (2010)[22] to the SIRS model, considers a dynamical formulation, in which nodes in contact with one or more infected individuals are immunized with a given probability. Again, by immunizing only a small fraction of the network, a notable reduction of prevalence and increase of the epidemic threshold can be achieved.

Nian和Wang(2010)将高风险免疫策略应用于SIRS模型,这是一种不同的免疫方法,它考虑了一种动态方案,即接触大等于一个感染个体的节点被以给定的概率进行免疫。同样的,这种策略只需要对网络中一小部分节点进行免疫接种,就可以显著降低患病率并提高传播阈值。

Finally, for the SIR model, the mapping to percolation suggests which nodes to target in a vaccination campaign, depending on whether the probability of an outbreak or its size are to be minimized [23]. A targeted vaccination of nodes in the GSCC (giant strongly connected component) implies a reduction of both the probability of a major epidemics and its size.

最后,对于SIR模型来说,由于其可以被转变为渗流问题,因此免疫哪些节点的问题就变为如何使爆发或传播规模最小化的问题(Kenah和Miller,2011)。 巨型强连通图中对节点的目标免疫意味着要使爆发或传播规模大的概率减小。


参考文献 References

  1. 1.0 1.1 1.2 1.3 1.4 Pastor-Satorras R, Vespignani A. Immunization of complex networks[J]. Physical review E, 2002, 65(3): 036104.
  2. Anderson R M, Anderson B, May R M. Infectious diseases of humans: dynamics and control[M]. Oxford university press, 1992.
  3. Cohen R, Erez K, Ben-Avraham D, et al. Breakdown of the internet under intentional attack[J]. Physical review letters, 2001, 86(16): 3682.
  4. Dezső Z, Barabási A L. Halting viruses in scale-free networks[J]. Physical Review E, 2002, 65(5): 055103.
  5. Kooij R E, Schumm P, Scoglio C, et al. A new metric for robustness with respect to virus spread[C]//International Conference on Research in Networking. Springer, Berlin, Heidelberg, 2009: 562-572.
  6. Youssef M, Kooij R, Scoglio C. Viral conductance: Quantifying the robustness of networks with respect to spread of epidemics[J]. Journal of Computational Science, 2011, 2(3): 286-298.
  7. Van Mieghem P. The viral conductance of a network[J]. Computer Communications, 2012, 35(12): 1494-1506.
  8. Van Mieghem, P., and J. Omic, 2008, arXiv:1306.2588.
  9. Omic J, Orda A, Van Mieghem P. Protecting against network infections: A game theoretic perspective[C]//IEEE INFOCOM 2009. IEEE, 2009: 1485-1493.
  10. Moradi A, Shah-Mansouri V. Opportunistic content dissemination in mobile social networks via adjustment of user selfishness[J]. IET Networks, 2018, 8(2): 126-137.
  11. Holme, P., B. J. Kim, C. N. Yoon, and S. K. Han, 2002, Phys. Rev. E 65, 056109.
  12. Schneider, C. M., T. Mihaljev, S. Havlin, and H. J. Herrmann, 2011, Phys. Rev. E 84, 061911.
  13. Chen, Y., G. Paul, S. Havlin, F. Liljeros, and H. E. Stanley, 2008, Phys. Rev. Lett. 101, 058701.
  14. Cohen R, Havlin S, Ben-Avraham D. Efficient immunization strategies for computer networks and populations[J]. Physical review letters, 2003, 91(24): 247901.
  15. Holme P. Efficient local strategies for vaccination and network attack[J]. EPL (Europhysics Letters), 2004, 68(6): 908.
  16. Ke H, Yi T. Immunization for scale-free networks by random walker[J]. Chinese Physics, 2006, 15(12): 2782.
  17. Noh J D, Rieger H. Random walks on complex networks[J]. Physical review letters, 2004, 92(11): 118701.
  18. Holme P. Efficient local strategies for vaccination and network attack[J]. EPL (Europhysics Letters), 2004, 68(6): 908.
  19. Gómez-Gardenes J, Echenique P, Moreno Y. Immunization of real complex communication networks[J]. The European Physical Journal B-Condensed Matter and Complex Systems, 2006, 49(2): 259-264.
  20. Stauffer A O, Barbosa V C. Dissemination strategy for immunizing scale-free networks[J]. Physical Review E, 2006, 74(5): 056105.
  21. Deijfen M. Epidemics and vaccination on weighted graphs[J]. Mathematical biosciences, 2011, 232(1): 57-65.
  22. Nian F, Wang X. Efficient immunization strategies on complex networks[J]. Journal of theoretical biology, 2010, 264(1): 77-83.
  23. Kenah E, Miller J C. Interdiscip. Perspect[J]. Infect. Dis, 2011, 543520.




此页参考来源: Pastor-Satorras R, Castellano C, Van Mieghem P, et al. Epidemic processes in complex networks[J]. Reviews of modern physics, 2015, 87(3): 925.