# 免疫策略（Immunization Strategy）

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.

## 随机免疫策略

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]

## 目标免疫策略

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]

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].

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.

## 基于局域信息的免疫策略

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.

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].

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.

## 参考文献 References

1. 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.