science >> Wetenschap >  >> Elektronica

Efficiënt netwerken ontmantelen en virussen stoppen

Het eerst sluiten van middelgrote luchthavens (zie rode cirkels op de onderste rij) in plaats van eerst de grootste hubs (zie rode cirkels op de bovenste rij) zou vier keer minder kosten en zou ook de verspreiding van het virus stoppen. Credit:PNAS / Lectoraat Computational Social Science

virussen, misdrijf, en vele andere problemen verspreiden zich via netwerken. ETH-onderzoekers hebben nu een nieuwe methode ontwikkeld om ze kosteneffectief te beschermen. Als budget belangrijk is, netwerken kunnen het beste worden ontmanteld, te beginnen met enkele middenknooppunten.

In de slotscène van de kaskraker Rise of the Planet of the Apes uit 2011, een piloot draagt ​​onbewust een gevaarlijk griepvirus van San Francisco naar Parijs. Vanaf daar, talloze vliegtuigpassagiers verspreiden het over de hele wereld. In tegenstelling tot de apen, een groot deel van de mensheid overleeft de daaropvolgende pandemie niet.

Natuurlijk, dit was pure sciencefiction, maar de verspreiding van besmettelijke virussen via vliegreizen is een reëel risico. Onderzoekers van de ETH-hoogleraar Computational Social Science en een medewerker van de ETH-afdeling Computerwetenschappen hebben onderzocht hoe het ontmantelen van netwerken zou kunnen helpen om de wereldwijde verspreiding van virussen via luchtvervoer op een meer kosteneffectieve manier in te dammen.

Een beschermende maatregel, waarover wel eens wordt gesproken, is om bepaalde luchthavens te sluiten en in quarantaine te plaatsen. Vervolgens, een optie zou zijn om ons te concentreren op 's werelds grootste luchthavenknooppunten met de meeste vliegverbindingen - per slot van rekening een groot aantal passagiers landt daar of verandert van vliegtuig. Dit is misschien niet echt het beste idee.

De interventie zou massaal zijn vanwege het grote aantal betrokken passagiers. In het wetenschappelijke tijdschrift PNAS , ETH-onderzoekers Xiao-Long Ren, Niels Gleinig, Dirk Helbing en Nino Antulov-Fantulin hebben nu kunnen aantonen dat er misschien minder radicale en effectievere manieren zijn om hetzelfde niveau van bescherming te bereiken, met veel minder passagiers.

Begin met de middelgrote

"Bijvoorbeeld, als je eerst een paar middelgrote luchthavens zou sluiten in plaats van de grootste hubs, het zou vier keer minder kosten in het scenario dat we bestudeerden, maar het lijkt net zo effectief te zijn in het tegengaan van de verspreiding van een virus, " zegt Nino Antulov-Fantulin.

De ETH-onderzoekers hebben dit scenario voor Europa onderzocht, Noord-Amerika en Azië als onderdeel van het wereldwijde luchtverkeersnetwerk. Hun resultaten tonen aan dat de sluiting van middelgrote luchthavens slechts 6 procent van de wereldwijde vliegtuigpassagiers zou treffen. terwijl het sluiten van de grootste hubs 25 procent zou beïnvloeden.

Om erachter te komen welke luchthavens moeten worden gesloten om het virus goedkoop en effectief te stoppen, de onderzoekers onderzochten een vraag die in netwerkonderzoek bekend staat als het "ontmantelingsprobleem", dat is een van de fundamentele problemen op het gebied van netwerkwetenschap. Het onderzoekt welke nodes moeten worden gedeactiveerd of uit een netwerk moeten worden verwijderd om de storing van een systeem te verstoren.

De ETH-onderzoekers probeerden verschillende defecte netwerken op te splitsen in geïsoleerde subnetwerken tegen de laagst mogelijke totale kosten, om de verspreiding van problemen in te dammen en de functionaliteit van het totale netwerk te behouden. Afhankelijk van of het een sociale, biologisch of technisch netwerk, de problemen kunnen de vorm aannemen van computervirussen, de griep, of criminelen.

misdaad bevatten

Ook in andere casestudies de ETH-onderzoekers konden aantonen dat het goedkoper en effectiever is om een ​​netwerk te ontmantelen door eerst enkele middenknooppunten te verwijderen, in plaats van de grootste; bijvoorbeeld, in criminele netwerken.

Als je aan de top van een crimineel netwerk begint, u maakt zeer hoge kosten. Niet alleen vanwege de speciale bescherming voor de bazen, maar ook omdat meestal iemand anders snel het leiderschap op zich neemt en het netwerk blijft runnen. Als u eerst de middenposities verwijdert, u kunt het netwerk effectiever opbreken tegen aanzienlijk lagere kosten, stellen de onderzoekers.

"Vergeleken met een state-of-the-art methode, de kosten van netwerkfragmentatie zijn in onze aanpak 2,5 keer lager, bij het ontmantelen van een crimineel netwerk tot 10 procent van zijn oorspronkelijke omvang, " zegt Xiao-Long Ren, promovendus en eerste auteur van de studie. De criminele netwerkzaak illustreert een ander speciaal kenmerk van de ETH-aanpak:in tegenstelling tot andere methoden, het behandelt niet alle knooppunten gelijk.

"We gaan er niet langer vanuit dat alle nodes in een netwerk dezelfde verwijderingskosten maken, " legt Ren uit. "Integendeel, de kosten om de grote nodes te verwijderen zijn hoger omdat ze veel meer verbonden zijn met andere nodes."

Grote uitdaging in theorie en toepassing

De ETH-wetenschappers hebben ook vooruitgang geboekt met het ontmantelen van bijzonder grote netwerken met miljoenen nodes. Het oplossen van het "demontageprobleem" behoort tot de categorie van bijzonder moeilijke computerproblemen die bekend staan ​​als NP-harde problemen - een grote uitdaging in wiskunde en informatica.

Hoewel deze theoretische methode is aangetoond met empirische gegevens, de toepassing op real-life scenario's kan verdere studies vereisen. De methode moet worden aangepast aan en getest in het betreffende toepassingsdomein. Het zijn niet alleen de netwerkstructuur en de kosten voor het verwijderen van knooppunten die ertoe doen, maar er kunnen ook andere factoren zijn.

Tenslotte, "legitieme toepassingen van onze methode moeten rekening houden met ethische kwesties, adequaat en transparant, benadrukken de onderzoekers.