Det är vinter. Och som alla frekventa resenärer vet, vintern kan innebära förseningar på flygplatsväder. En snöstorm i Minneapolis, en stor flygplatsnav, kan snabbt leda till förseningar i ljumma Miami eller dimmiga London.

För att minimera störningar, flygledningsanalytiker arbetar med att prioritera återhämtningsinsatser. Men med så många variabler, det är svårt för dem att ge säkra rekommendationer. Men det här är precis den sortens datadrivna problem som en dator kan programmeras att lösa. Frågan är tid. Nuvarande metoder är inte tillräckligt snabba för att tillhandahålla lösningar i realtid.

Nu, ett forskarlag ledd av datavetare vid PNNL har utvecklat ett nytt grafverktyg, kallas Ripples, som kan lösa ett komplext grafanalysproblem som flygplatsstörningsanalys på mindre än en minut på en superdator. Det bästa jämförbara verktyget kan ta en hel dag på en vanlig dator för att lösa samma problem. En dag, beräkningsmilstolpen kan göra analys av nätverkseffekter som flygtrafikstörningar tillgänglig för beslutsfattare i realtid.

"Vårt tillvägagångssätt utnyttjar en rigorös analysmetod för sociala nätverk, formellt känt som problemet med inflytandemaximering, och skalar den för att köras på högeffektiva parallella datorplattformar, sa Arun Sathanur, en PNNL datavetare som ledde flygplatsmodelleringsarbetet. "Dessa modeller utmärker sig när det gäller att hitta inflytelserika enheter, analysera effekten av anslutning, och pekar ut var störningar har den största kaskadeffekten."

Forskargruppen, som också inkluderar forskare från Northeastern University och Department of Transportation's Volpe National Transportation Systems Center, presenterade sin flygplatsnätverksanalys vid IEEE International Symposium on Technologies for Homeland Security i november 2019.

Genom att använda allmänt tillgängliga data från Department of Transportations Federal Aviation Administration, de grupperade flygplatser i inflytandekluster och visade vilka flygplatser som är mest inflytelserika, samt hur den viktigaste "influencer"-listan förändras under hela kalenderåret.

Resultaten ger ett bevis på principen, som så småningom kan användas för att hantera störningar i flygplatsnätverket, Sathanur tillade.

"Ripples tillhandahåller ett kraftfullt verktyg för proaktiv strategisk planering och operationer, och har bred tillämpbarhet över nätverksanslutna transportinfrastruktursystem, " sa Sam Chatterjee, en operationsforskare vid PNNL och huvudforskare för flygplatsmodelleringsarbetet som leds av Sathanur.

Den ultimata logistiken

I en alltmer överbelastad värld, att snabbt kunna återställa tjänsten efter oavsiktliga systemfel eller cybersäkerhetsbrott skulle vara en stor fördel. Detta är området för nätverksanalys, som först utvecklades för att förstå hur människor i sociala nätverk är kopplade till varandra. Alltmer, nätverksanalys och visuell analys används för att göra saker som att upptäcka obehörig åtkomst till datornätverk, upptäcka samband mellan proteiner i cancertumörer, och lösa trafikstockningsdilemman som trafikstockningsproblemet på flygplatsnätverket.

Dock, för att analysresultaten ska vara tillförlitliga, en sekvens av beräkningar för att beräkna påverkansspridningen måste utföras. Detta visar sig vara ett beräkningsmässigt svårt problem, sa Mahantesh Halappanavar, senior forskare vid PNNL och huvudutredaren för ExaGraph, ett applikationssamdesigncenter finansierat av Department of Energys (DOEs) Exascale Computing Project.

"För många verkliga scenarier, det är inte alltid klart hur man tilldelar styrkan i anslutningarna mellan enskilda enheter i nätverket exakt vikt, " sa han. "Vi, därför, upprepa simuleringar med flera inställningar för att öka förtroendet för datoriserade lösningar." Även när vikterna är välkända, Metoden bygger fortfarande på att utföra ett stort antal simuleringar för att identifiera inflytelserika enheter.

De uppskattar de viktigaste påverkarna i någon grupp genom att köra dessa upprepade simuleringar av en påverkanskaskadmodell tills de kommer fram till en korrekt uppskattning. Detta tillvägagångssätt är det som gör det skrämmande att hitta ens en liten uppsättning viktiga influencers i ett måttligt stort nätverk, tar dagar att slutföra.

Det är därför Ripples dramatiska förbättring av hastighet till lösning är så betydande.

"Att nollställa de mest inflytelserika enheterna i stora nätverk kan snabbt bli tidskrävande, " sa Ananth Kalyanaraman, en medutvecklare av Ripples och Boeings hundraårsjubileumsstol i datavetenskap vid School of Electrical Engineering and Computer Science, Washington State University, i Pullman. "Ripplingar, och dess nyare variant av bågar, använder en strategi för att utnyttja enorma mängder datorkraft, inklusive de i moderna grafikbehandlingsenheter för att söka den "näst mest inflytelserika" enheten under dess sökning."

Pålitliga svar

Ytterligare, Ripples är baserad på lösningen som kommer med vad som kallas en "approximationsgaranti, " som tillåter användaren att byta ut kvaliteten på lösningen med tiden att beräkna en lösning, samtidigt som den har förmågan att bedöma kvaliteten på den beräknade lösningen. De PNNL- och WSU-baserade teamen arbetade nära tillsammans för att skala Ripples-verktyget effektivt på de snabbaste superdatorerna som hanteras av DOE.

Denna strategi tillåter Ripples att effektivt konvergera till en lösning av högre kvalitet, upp till 790 gånger snabbare än tidigare metoder som inte är designade för parallella system.

"Om vi ​​kunde konvergera om en lösning på under en minut, vi kan börja använda detta som ett interaktivt verktyg, " säger Marco Minutoli på PNNL, huvudutvecklaren av Ripples. "Vi kan ställa och svara på nya frågor i nästan realtid."

PNNL-forskare gör redan just det. De har börjat använda Ripples för att krossa enorma mängder data och hitta de viktigaste influencers i:

• Identifiera de viktigaste arterna inom en gemenskap av markmikroorganismer eftersom den reagerar på förändringar i fukt;
• Spåra spridningen av infektionssjukdomar och föreslå inneslutningsstrategier för att kontrollera spridningen av en epidemi; och
• Identifiera de viktigaste komponenterna i luftprover för inkludering i detaljerade klimatmodeller för att studera deras inverkan på luftföroreningar.

"Som vi förstår det, detta är det första försöket att parallellisera inflytandemaximeringsoperationen i skala, sa Minutoli.

Forskargruppen har gjort metoden tillgänglig för forskarsamhället på Github. De planerar nästa stora framsteg (curRipples), vilket kommer att vara att optimera metoden på Summit, världens snabbaste superdator.