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 $p_c$ and the size of the giant component $P_{\infty }$ for networks with arbitrary degree distributions $P(k)$. In the limit of $n\to \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, $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(\infty )-p_c(n)|$ and $n$ as $|p_c(\infty )-p_c(n)|\sim n^{-1}\exp (-\alpha n)$. For Scale-free (SF) networks, where $P(k)\sim k^{-\gamma },2<\gamma <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.

References in corpus (20)

• Statistical mechanics of complex networks
• Error and attack tolerance of complex networks
• Epidemic spreading in scale-free networks
• Catastrophic cascade of failures in interdependent networks
• The diameter of the world wide web
• Random graphs with arbitrary degree distributions and their applications
• Network robustness and fragility: Percolation on random graphs
• Resilience of the Internet to random breakdowns
• Breakdown of the Internet under intentional attack
• Influence maximization in complex networks through optimal percolation
• Efficient Immunization Strategies for Computer Networks and Populations
• Robustness of interdependent networks under targeted attack
• Stability and topology of scale-free networks under attack and defense strategies
• Spectrum of Controlling and Observing Complex Networks
• Resilience of networks with community structure behaves as if under an external field
• Core percolation on complex networks
• Network Observability Transitions
• Totally Homogeneous Networks
• Predictability of real temporal networks
• History-dependent percolation on multiplex networks

Cited by in corpus (4)

• Beyond network centrality: Individual-level behavioral traits for predicting information superspreaders in social media
• Epidemics with containment measures
• A sampling-guided unsupervised learning method to capture percolation in complex networks
• Nonequilibrium phase transitions in a racism-spreading model with interaction-driven dynamics