Het is winter. En zoals elke frequente reiziger weet, winter kan vertragingen in het weer op de luchthaven betekenen. Een sneeuwstorm in Minneapolis, een belangrijk luchthavenknooppunt, kan snel leiden tot vertragingen in het zwoele Miami of het mistige Londen.

Om overlast tot een minimum te beperken, luchtverkeersleidingsanalisten werken om prioriteit te geven aan herstelinspanningen. Maar met zoveel variabelen, het is moeilijk voor hen om zelfverzekerde aanbevelingen te doen. Maar dit is precies het soort datagedreven probleem waarvoor een computer kan worden geprogrammeerd om het op te lossen. Het probleem is tijd. De huidige methoden zijn niet snel genoeg om realtime oplossingen te bieden.

Nutsvoorzieningen, een onderzoeksteam onder leiding van computerwetenschappers van PNNL heeft een nieuwe Graph-tool ontwikkeld, Rimpelingen genoemd, die een complex grafiekanalyseprobleem zoals analyse van luchthavenverstoringen in minder dan een minuut op een supercomputer kan oplossen. De best vergelijkbare tool kan op een gewone computer een hele dag nodig hebben om hetzelfde probleem op te lossen. Op een dag, de computermijlpaal kan analyse van netwerkeffecten, zoals verstoringen van het luchtverkeer, beschikbaar maken voor realtime besluitvormers.

"Onze aanpak maakt gebruik van een rigoureuze methodologie voor sociale netwerkanalyse, formeel bekend als het invloedsmaximalisatieprobleem, en schaalt het om te draaien op zeer efficiënte parallelle computerplatforms, " zei Arun Sathanur, een computerwetenschapper van PNNL die het modelleringswerk op de luchthaven leidde. "Deze modellen blinken uit in het vinden van invloedrijke entiteiten, het analyseren van de impact van connectiviteit, en te wijzen op waar verstoringen het grootste trapsgewijze rimpeleffect hebben."

Het onderzoeksteam, die ook onderzoekers van de Northeastern University en het Volpe National Transportation Systems Center van het Department of Transportation omvat, presenteerden hun luchthavennetwerkanalyse op het IEEE International Symposium on Technologies for Homeland Security in november 2019.

Met behulp van openbaar beschikbare gegevens die zijn verstrekt door de Federal Aviation Administration van het Department of Transportation, ze groepeerden luchthavens in clusters van invloed en lieten zien welke luchthavens het meest invloedrijk zijn, evenals hoe de belangrijkste "influencer"-lijst gedurende het kalenderjaar verandert.

De bevindingen bieden een proof-of-principle, die uiteindelijk kunnen worden gebruikt om verstoringen van het luchthavennetwerk te beheren, Sathanur toegevoegd.

"Ripples biedt een krachtig hulpmiddel voor proactieve strategische planning en operaties, en heeft een brede toepasbaarheid op genetwerkte transportinfrastructuursystemen, " zei Sam Chatterjee, een operationeel onderzoeker bij PNNL en hoofdonderzoeker voor het luchthavenmodelleringswerk onder leiding van Sathanur.

De ultieme logistiek

In een steeds drukker wordende wereld, de mogelijkheid om de service snel te herstellen na onopzettelijke systeemstoringen of cybersecurity-inbreuken zou een enorm voordeel zijn. Dit is het domein van netwerkanalyse, die voor het eerst werd ontwikkeld om te begrijpen hoe mensen in sociale netwerken met elkaar verbonden zijn. Meer en meer, netwerkanalyse en visuele analyse worden gebruikt om dingen te doen zoals het opsporen van ongeautoriseerde toegang tot computernetwerken, relaties tussen eiwitten in kankertumoren detecteren, en het oplossen van transportcongestiedilemma's zoals het congestieprobleem van het luchthavennetwerk.

Echter, om de analyseresultaten betrouwbaar te maken, er moet een reeks berekeningen worden uitgevoerd om de invloedsspreiding te berekenen. Dit blijkt een rekenkundig moeilijk probleem te zijn, zei Mahantesh Halappanavar, senior wetenschapper bij PNNL en de hoofdonderzoeker van ExaGraph, een co-designcentrum voor toepassingen gefinancierd door het Exascale Computing Project van het Department of Energy (DOE).

"Voor veel real-world scenario's, het is niet altijd duidelijk hoe nauwkeurig gewicht moet worden toegekend aan de sterkte van verbindingen tussen individuele entiteiten in het netwerk, "zei hij. "Wij, daarom, herhaal simulaties met meerdere instellingen om het vertrouwen van berekende oplossingen te vergroten." Zelfs als de gewichten goed bekend zijn, de methode steunt nog steeds op het uitvoeren van een groot aantal simulaties om invloedrijke entiteiten te identificeren.

Ze schatten de belangrijkste beïnvloeders in elke groep door deze herhaalde simulaties van een invloedscascademodel uit te voeren totdat ze tot een nauwkeurige schatting komen. Deze benadering maakt het ontmoedigend om zelfs maar een klein aantal belangrijke influencers te vinden in een redelijk groot netwerk, dagen in beslag nemen.

Daarom is de dramatische verbetering van Ripples in snelheid tot oplossing zo belangrijk.

"Zeroeg in op de meest invloedrijke entiteiten in grote netwerken kan snel tijdrovend worden, " zei Ananth Kalyanaraman, een mede-ontwikkelaar van Ripples en Boeing honderdjarige leerstoel in computerwetenschappen aan de School of Electrical Engineering and Computer Science, de staatsuniversiteit van Washington, in Pullman. "rimpelingen, en zijn nieuwere variant cuRipples, gebruikt een strategie om enorme hoeveelheden rekenkracht te exploiteren, inclusief die in moderne grafische verwerkingseenheden om de 'volgende meest invloedrijke' entiteit te zoeken tijdens zijn zoektocht."

Betrouwbare antwoorden

Verder, Ripples is gebaseerd op de oplossing die wordt geleverd met een zogenaamde "benaderingsgarantie, " waarmee de gebruiker de kwaliteit van de oplossing kan afruilen met de tijd om een ​​oplossing te berekenen, terwijl ze ook de mogelijkheid hebben om de kwaliteit van de berekende oplossing te beoordelen. De op PNNL en WSU gebaseerde teams werkten nauw samen om de Ripples-tool efficiënt te schalen op de snelste supercomputers die door DOE worden beheerd.

Met deze strategie kan Ripples efficiënt convergeren naar een oplossing van hogere kwaliteit, tot 790 keer sneller dan eerdere methoden die niet zijn ontworpen voor parallelle systemen.

"Als we binnen een minuut tot een oplossing zouden kunnen komen, we kunnen dit gaan gebruiken als een interactief hulpmiddel, " zegt Marco Minutoli van PNNL, de hoofdontwikkelaar van Ripples. "We kunnen nieuwe vragen bijna in realtime stellen en beantwoorden."

Wetenschappers van PNNL doen dat al. Ze zijn Ripples gaan gebruiken om enorme hoeveelheden gegevens te verwerken en de belangrijkste influencers te vinden in:

• Identificatie van de belangrijkste soorten binnen een gemeenschap van bodemmicro-organismen als deze reageert op veranderingen in vocht;
• De verspreiding van infectieziekten volgen en inperkingsstrategieën voorstellen om de verspreiding van een epidemie onder controle te houden; en
• Het identificeren van de belangrijkste componenten in luchtmonsters voor opname in gedetailleerde klimaatmodellen om hun invloed op luchtvervuiling te bestuderen.

"Voor zover wij weten, dit is de eerste poging om de invloedsmaximalisatie-operatie op schaal te parallelliseren, ' zei Minutoli.

Het onderzoeksteam heeft de methode op Github beschikbaar gesteld voor de onderzoeksgemeenschap. Ze plannen de volgende grote vooruitgang (cuRipples), die zal zijn om de methode op Summit te optimaliseren, 's werelds snelste supercomputer.