Efficient network immunization under limited knowledge

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 p _c 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, p _c increases quickly towards its optimal value under targeted immunization (attack) with complete information. In particular, we find a new scaling relationship between | p _c (∞) − p _c ( n ) | and n as | p _c (∞) − p _c ( n )| ~ n ⁻¹ exp(− αn ). For Scale-free (SF) networks, where P ( k ) ~ k ^{− γ} , 2 < γ < 3, we find that p _c has a transition from zero to non-zero when n increases from n = 1 to order of log N ( N is the size of network). Thus, for SF networks, knowledge of order of log N nodes and immunizing them can reduce dramatically an epidemics.