Finding a Better Immunization Strategy

The problem of finding the best strategy to immunize a population or a computer network with a minimal number of immunization doses is of current interest. It has been accepted that the targeted strategies on most central nodes are most efficient for model and real networks. We present a newly developed graph-partitioning strategy which requires 5% to 50% fewer immunization doses compared to the targeted strategy and achieves the same degree of immunization of the network. We explicitly demonstrate the effectiveness of our proposed strategy on several model networks and also on real networks.

Figure 1

Diagram showing one attempt of moving nodes in separator group. In (a) we try to move the top node in the separators to group 1 and the result is shown in (b), where the adjacent node of the moved node is dragged into separator group. The bottom node in the separators is dragged to group 1 because all its adjacent nodes are in group 1 and its existence in separators becomes meaningless. After this trial, the size of separator group is reduced from 2 to 1. Thus, this movement is permitted.

Figure 2

The fraction $F$ of the size of the largest cluster that can be infected versus the fraction $q$ of the immunized nodes for HD, HDA, HB, and EGP strategies for (a) random regular graph with $N={10}^4$ and $k=4$, (b) ER network with $N={10}^4$, $⟨k⟩=3.5$, (c) SF network with $N={10}^4$, $\lambda =2.5$,and $⟨k⟩=4.68$, (d) SF network with $N={10}^4$, $\lambda =3.5$, and $⟨k⟩=2.89$. We show also the error bars in $F$, which are derived from simulating realizations. The error bars for EGP are so small that they are barely seen.

Figure 3

The fraction $F$ of the size of the largest cluster that can be infected versus the fraction of immunized nodes $q$ for HD, HDA, and EGP strategies for (a) the workplace network, (b) the AS Internet network, (c) high energy physics HEP network, (d) metabolic network.

Figure 4

Infected network fraction $P_i$ and recovered fraction $P_r$ versus time for the SIR model [17]. Comparison between HD and EGP strategies for (a) immunizing a fraction $q=0.12$ of the nodes in a SF network with $N={10}^4$, $\lambda =2.5$, (b) immunizing a fraction $q=0.02$ in AS Internet network, (c) immunizing a fraction $q=0.065$ of the nodes in the workplace network, (d) immunizing a fraction $q=0.31$ of the nodes in the HEP network.

Figure 5

The threshold $q_c$ versus average mode degree $⟨k⟩$ for HD, HDA, and the EGP strategies for (a) ER networks with $N={10}^4$, (b) SF networks with $N={10}^4$ and $\lambda =2.5$, (c) random regular graph with $N={10}^4$, (d) the critical threshold $q_c$ versus system size $N$ for SF networks with $\lambda =2.5$ and ER networks with $⟨k⟩=3$.