Efficient network immunization under limited knowledge

• 来源期刊: 国家科学评论（英文版）
• 年，卷（期）: 2021,（1）
• 所属期刊栏目: RESEARCH ARTICLES
• 页码范围: 122-129
• 页数: 8页
• 语种: 英文
• DOI: 10.1093/nsr/nwaa229

摘要

Targeted immunization of centralized nodes in large-scale networks has attracted significant attention.However,in real-world scenarios,knowledge and observations of the network may be limited,thereby precluding a fall assessment of the optimal nodes to immunize(or quarantine)in order to avoid epidemic spreading such as that of the current coronavirus disease(COVID-19)epidemic.Here,we study a novel immunization strategy where only n nodes are observed at a time and the most central among these n nodes is immunized.This process can globally immunize a network.We find that even for small n(≈10)there is significant improvement in the immunization(quarantine),which is very close to the levels of immunization with full knowledge.We develop an analytical framework for our method and determine the critical perco-lation 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 immunization,whereas for n = 1 we recover the known case of random immunization.Between these two extremes,we observe that,as n increases,pc increases quickly towards its optimal value under targeted immunization with complete information.In particular,we find a new general scaling relationship between |pc(∞)-pc(n)| andnas |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 nonzero when n increases from n = 1 to O(log N)(where N is the size of the network).Thus,for SF networks,having knowledge of ≈log N nodes and immunizing the most optimal among them can dra-matically reduce epidemic spreading.We also demonstrate our limited knowledge immunization strategy on several real-world networks and confirm that in these real networks,pc increases significantly even for small n.