Effektiv demontering af netværk og stop vira

Virus, forbrydelse, og mange andre problemer spredt gennem netværk. ETH-forskere har nu udviklet en ny metode til at beskytte dem omkostningseffektivt. Når budgettet betyder noget, netværk er bedst afmonteret startende med nogle midterste noder.

I den sidste scene af storfilmen Rise of the Planet of the Apes fra 2011, en pilot bærer uforvarende en farlig influenzavirus fra San Francisco til Paris. Derfra, utallige flypassagerer spredte det rundt i verden. I modsætning til aberne, en stor del af menneskeheden overlever ikke den efterfølgende pandemi.

Selvfølgelig, dette var ren science fiction, men spredningen af ​​smitsomme vira via flyrejser er en reel risiko. Forskere fra ETH Professoratet i Computational Social Science og en samarbejdspartner fra ETH Institut for Datalogi har undersøgt, hvordan netværksafbrydelse kan hjælpe med at begrænse den globale spredning af vira gennem lufttransport mere omkostningseffektivt.

En beskyttelsesforanstaltning, som nogle gange diskuteres, er at lukke visse lufthavne og sætte dem i karantæne. Derefter, en mulighed ville være at fokusere på verdens største lufthavnshubs med flest flyforbindelser – trods alt, et stort antal passagerer lander der eller skifter fly. Dette er måske faktisk ikke den bedste idé.

Indgrebet ville være massivt på grund af det store antal passagerer involveret. I det videnskabelige tidsskrift PNAS , ETH-forskere Xiao-Long Ren, Niels Gleinig, Dirk Helbing og Nino Antulov-Fantulin har nu været i stand til at vise, at der måske er mindre radikale og mere effektive måder at opnå det samme beskyttelsesniveau på, påvirker langt færre passagerer.

Start med de mellemstore

"For eksempel, hvis du ville lukke et par mellemstore lufthavne først i stedet for de største knudepunkter, det ville koste fire gange mindre i det scenarie, vi undersøgte, men det ser ud til at være lige så effektivt til at begrænse spredningen af ​​en virus, " siger Nino Antulov-Fantulin.

ETH-forskerne udforskede dette scenarie for Europa, Nordamerika og Asien som dele af det verdensomspændende lufttrafiknetværk. Deres resultater viser, at lukningen af ​​mellemstore lufthavne kun vil påvirke 6 procent af globale flypassagerer, mens en lukning af de største hubs ville påvirke 25 pct.

For at finde ud af, hvilke lufthavne der skal lukkes for at stoppe virussen billigt og effektivt, forskerne undersøgte et spørgsmål kendt i netværksforskningen som "demonteringsproblemet", hvilket er et af de grundlæggende problemer inden for netværksvidenskab. Den undersøger, hvilke noder der skal deaktiveres eller fjernes fra et netværk for at afbryde funktionsfejl i et system.

ETH-forskerne forsøgte at nedbryde forskellige defekte netværk i isolerede undernetværk til lavest mulige samlede omkostninger, for at begrænse spredningen af ​​problemer og opretholde funktionaliteten af ​​det overordnede netværk. Alt efter om det er en social biologiske eller tekniske netværk, problemerne kan tage form af computervirus, influenza, eller kriminelle.

Indeholder kriminalitet

Også i andre casestudier, ETH-forskerne var i stand til at vise, at det er billigere og mere effektivt at afmontere et netværk ved først at fjerne nogle mellemknuder, snarere end de største; for eksempel, i kriminelle netværk.

Hvis du starter på toppen af ​​et kriminelt netværk, du pådrager dig meget høje omkostninger. Ikke kun på grund af den særlige beskyttelse, der ydes til cheferne, men også fordi en anden typisk hurtigt overtager ledelsen og fortsætter med at drive netværket. Hvis du først fjerner midterpositionerne, du kan bryde netværket op mere effektivt til betydeligt reducerede omkostninger, fastslår forskerne.

"Sammenlignet med en state-of-the-art metode, omkostningerne ved netværksfragmentering er 2,5 gange lavere i vores tilgang, når man afmonterer et kriminelt netværk til 10 procent af dets oprindelige størrelse, " siger Xiao-Long Ren, ph.d.-studerende og førsteforfatter til undersøgelsen. Den kriminelle netværkssag illustrerer et andet særligt træk ved ETH-tilgangen:i modsætning til andre metoder, den behandler ikke alle noder ens.

"Vi antager ikke længere, at alle noder i et netværk har de samme omkostninger til fjernelse, " forklarer Ren. "Snarere, omkostningerne til at fjerne de store noder er højere, fordi de er meget mere forbundet med andre noder."

Stor udfordring i teori og anvendelse

ETH-forskerne har også gjort fremskridt med afviklingen af ​​særligt store netværk med millioner af noder. At løse "demonteringsproblemet" hører til kategorien af ​​særligt vanskelige computerproblemer kendt som NP-hårde problemer – en stor udfordring inden for matematik og datalogi.

Selvom denne teoretiske metode er blevet demonstreret med empiriske data, anvendelsen til virkelige scenarier kan have behov for yderligere undersøgelser. Metoden bør tilpasses og testes i det respektive applikationsdomæne. Det er ikke kun netværksstrukturen og omkostningerne til fjernelse af knudepunkter, der betyder noget, men der kan også være andre faktorer.

Sidst men ikke mindst, "legitime anvendelser af vores metode skal tage hensyn til etiske spørgsmål, passende og gennemsigtigt, " understreger forskerne.