Att förebygga spridning i nätverk är ett viktigt problem på folkhälsoområdet och andra områden. Rikta noder att immunisera baserat på deras nätverksinteraktioner har visat sig vara mycket effektivare på att hejda infektion spridning än immunisering slumpmässiga undergrupper av noder. Antagandet att utvalda noder kan göras helt immuna håller dock inte för infektioner för vilka det inte finns någon vaccination eller effektiv behandling. Istället kan man ge fraktionerad immunitet till vissa noder genom att tilldela variabla mängder infektionsförebyggande resurser till dem. Vi formulerar problemet att distribuera en fast mängd resurser över noder i ett nätverk så att infektionsfrekvensen minimeras, bevisa att det är NP-komplett och härleda en mycket effektiv linjär-tid algoritm. Vi demonstrerar effektiviteten och noggrannheten av vår algoritm jämfört med flera andra metoder med hjälp av simulering på realworld nätverk dataset inklusive US-MEDICARE och state-level interhospital patientöverföring data. Vi finner att koncentration av resurser till en liten delmängd av noder med hjälp av vår algoritm är upp till 6 gånger effektivare än att fördela dem jämnt (som nu är praxis) eller använda nätverksbaserade heuristik. Såvitt vi vet är vi de första som formulerar problemet, använder verkligt nationella nätverksdata och föreslår effektiva algoritmer.
Förhindra smitta i nätverk är ett annat attribut för motståndskraft, och metoder som REF föreslår algoritmer som immuniserar en delmängd av noder som en förebyggande åtgärd.
Fractional Immunization in Networks
{'venue': 'SDM', 'journal': None, 'mag_field_of_study': ['Computer Science']}