Efficient network immunization under limited knowledge

ABSTRACT

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{infty}; for networks with arbitrary degree distributions P(k). In the limit of n [->] {infty} 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({infty}) - pc(n) | and n as |pc({infty}) - pc(n)| ~ n-1 exp(-n). For Scale-free (SF) networks, where P(k) ~ k-{gamma}, 2 <{gamma} < 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.