Efficient network immunization under limited knowledge

Liu, Yangyang; Sanhedrai, Hillel; Dong, Gaogao; Shekhtman, Louis M.; Wang, Fan; Buldyrev, Sergey V.; Havlin, Shlomo

Targeted immunization or attacks of large-scale networks has attracted significant attention by the scientific community. However, in real-world scenarios, knowledge and observations of the network may be limited thereby precluding a full assessment of the optimal nodes to immunize (or remove) in order to avoid epidemic spreading such as that of current COVID-19 epidemic. Here, we study a novel immunization strategy where only n nodes are observed at a time and the most central between these n nodes is immunized (or attacked). This process is continued repeatedly until 1-p fraction of nodes are immunized (or attacked). We develop an analytical framework for this approach and determine the critical percolation threshold pc and the size of the giant component P∞ for networks with arbitrary degree distributions P(k). In the limit of n→∞ we recover prior work on targeted attack, whereas for n=1 we recover the known case of random failure. Between these two extremes, we observe that as n increases, pc increases quickly towards its optimal value under targeted immunization (attack) with complete information. In particular, we find a new scaling relationship between |pc(∞) -pc (n)| and n as |pc(∞) -pc (n)|~n-1exp(-α n). For Scale-free (SF) networks, where P(k)~k-γ,2<γ<3), we find that pc has a transition from zero to non-zero when n increases from n=1 to order of logN (N is the size of network). Thus, for SF networks, knowledge of order of logN nodes and immunizing them can reduce dramatically an epidemics.