Virus, brottslighet, och många andra problem sprids genom nätverk. ETH-forskare har nu utvecklat en ny metod för att skydda dem kostnadseffektivt. När budgeten är viktig, nätverk är bäst att demontera från och med några mellannoder.

I den sista scenen i storfilmen Rise of the Planet of the Apes 2011, en pilot bär omedvetet ett farligt influensavirus från San Francisco till Paris. Därifrån, otaliga flygpassagerare sprider det runt om i världen. Till skillnad från aporna, en stor andel av mänskligheten överlever inte den efterföljande pandemin.

Självklart, detta var ren science fiction, men spridningen av smittsamma virus via flygresor är en verklig risk. Forskare från ETH Professorship of Computational Social Science och en samarbetspartner från ETH Institutionen för datavetenskap har undersökt hur demontering av nätverk kan hjälpa till att begränsa den globala spridningen av virus genom lufttransport mer kostnadseffektivt.

En skyddsåtgärd, som ibland diskuteras, är att stänga vissa flygplatser och sätta dem i karantän. Sedan, ett alternativ skulle vara att fokusera på världens största flygplatshubbar med flest flygförbindelser - trots allt, ett stort antal passagerare landar där eller byter flygplan. Det här kan faktiskt inte vara den bästa idén.

Interventionen skulle bli massiv på grund av det stora antalet passagerare som var inblandade. I den vetenskapliga tidskriften PNAS , ETH-forskare Xiao-Long Ren, Niels Gleinig, Dirk Helbing och Nino Antulov-Fantulin har nu kunnat visa att det kan finnas mindre radikala och effektivare sätt att uppnå samma skyddsnivå, påverkar mycket färre passagerare.

Börja med de medelstora

"Till exempel, om du först stänger några medelstora flygplatser istället för de största naven, det skulle kosta fyra gånger mindre i det scenario vi studerade, men det verkar vara lika effektivt för att begränsa spridningen av ett virus, säger Nino Antulov-Fantulin.

ETH -forskarna utforskade detta scenario för Europa, Nordamerika och Asien som delar av det globala flygtrafiknätverket. Deras resultat visar att stängning av medelstora flygplatser bara skulle påverka 6 procent av de globala flygpassagerarna, medan stängning av de största naven skulle påverka 25 procent.

För att ta reda på vilka flygplatser som ska stängas för att stoppa viruset billigt och effektivt, forskarna undersökte en fråga som i nätverksforskning kallas "demonteringsproblemet", vilket är ett av de grundläggande problemen inom nätverksvetenskap. Den undersöker vilka noder som måste inaktiveras eller tas bort från ett nätverk för att störa funktionsfel i ett system.

ETH -forskarna försökte bryta ner olika felaktiga nätverk till isolerade delnät till lägsta möjliga totalkostnad, för att begränsa spridningen av problem och behålla funktionaliteten i det övergripande nätverket. Beroende på om det är en social, biologiskt eller tekniskt nätverk, besväret kan ta form av datavirus, influensan, eller kriminella.

Innehåller brott

Även i andra fallstudier, ETH -forskarna kunde visa att det är billigare och mer effektivt att demontera ett nätverk genom att först ta bort några mellannoder, snarare än de största; till exempel, i kriminella nätverk.

Om du börjar högst upp i ett kriminellt nätverk, du får mycket höga kostnader. Inte bara på grund av det speciella skyddet för cheferna, men också för att vanligtvis någon annan tar ledarskap snabbt och fortsätter att köra nätverket. Om du tar bort mittlägena först, du kan bryta upp nätverket mer effektivt till avsevärt reducerade kostnader, konstaterar forskarna.

"Jämfört med en toppmodern metod, kostnaderna för nätverksfragmentering är 2,5 gånger lägre i vårt tillvägagångssätt, vid demontering av ett kriminellt nätverk till 10 procent av dess ursprungliga storlek, "säger Xiao-Long Ren, doktorand och första författare till studien. Det kriminella nätverksfallet illustrerar ett annat särdrag hos ETH -metoden:till skillnad från andra metoder, det behandlar inte alla noder lika.

"Vi antar inte längre att alla noder i ett nätverk medför samma borttagningskostnader, "förklarar Ren." Snarare, kostnaderna för att ta bort de stora noder är högre eftersom de är mycket mer anslutna till andra noder. "

Stor utmaning i teori och tillämpning

ETH -forskarna har också gjort framsteg med demonteringen av särskilt stora nätverk med miljontals noder. Att lösa "demonteringsproblemet" tillhör kategorin särskilt svåra datorproblem som kallas NP-hårda problem-en stor utmaning inom matematik och datavetenskap.

Även om denna teoretiska metod har visats med empiriska data, tillämpningen på verkliga scenarier kan behöva ytterligare studier. Metoden bör anpassas till och testas i respektive applikationsdomän. Det är inte bara nätverksstrukturen och kostnader för borttagning av noder som spelar roll, men det kan också finnas andra faktorer.

Sist men inte minst, "legitima tillämpningar av vår metod måste ta hänsyn till etiska frågor, på ett lämpligt och öppet sätt, "betonar forskarna.