Nätverk kan representera föränderliga system, som spridningen av en epidemi eller tillväxten av grupper i en befolkning av människor. Men strukturen på dessa nätverk kan också förändras, eftersom länkar dyker upp eller försvinner med tiden. För att bättre förstå dessa förändringar studerar forskare ofta en serie statiska "snapshots" som fångar nätverkets struktur under en kort tid.
Nätverksteoretiker har sökt sätt att kombinera dessa ögonblicksbilder. I en ny artikel i Physical Review Letters , beskriver en trio av SFI-anslutna forskare ett nytt sätt att aggregera statiska ögonblicksbilder till mindre kluster av nätverk samtidigt som systemets dynamiska natur bevaras. Deras metod, inspirerad av en idé från kvantmekaniken, går ut på att testa på varandra följande par av ögonblicksbilder av nätverk för att hitta de för vilka en kombination skulle resultera i minsta effekt på systemets dynamik – och sedan kombinera dem.
Viktigt är att det kan avgöra hur historien om nätverkets struktur ska förenklas så mycket som möjligt med bibehållen noggrannhet. Matematiken bakom metoden är ganska enkel, säger huvudförfattaren Andrea Allen, nu dataforskare vid Children's Hospital of Philadelphia.
"Vi är verkligen glada över att kunna dela det, och det är ett under att ingen annan har publicerat denna exakta idé under det senaste decenniet", säger Allen. Hon samarbetade med SFI-professor Cris Moore, en fysiker och matematiker, och Laurent Hébert-Dufresne, en komplexitetsforskare vid University of Vermont och en tidigare SFI James S. McDonnell Foundation Fellow.
I den publicerade artikeln verkar metoden inte komplicerad; i verkligheten har det utvecklats över år både på och bortom SFI. Samarbetet inleddes 2015 när Allen, då grundämne i matematik, besökte SFI en månad på vintern och sedan, sommaren 2016, återvände för att delta i programmet Research Experiences for Bachelor (nu kallat Undergraduate Complexity Research-programmet) .
Hébert-Dufresne hade skaffat en stor datamängd, hämtad från satellittelefondata, som använde mobiltelefonens "pings" för att visa hur människor rörde sig. Han var intresserad av att hitta gemenskaper, men han ville också kunna mäta om olika gemenskaper krävde olika dataupplösning.
"Bör till exempel epidemiövervakningssystem vara enhetliga i samhällen när vi vet att olika samhällen har olika beteenden?"
Den frågan ledde till ännu mer:"På vilken nivå kan vi aggregera detta samtidigt som vi behåller skillnaderna? Och hur vet vi det?" frågar Allen. "Vi vill inte förlora integriteten hos nätverket vi försöker studera."
De tog in Moore för att brainstorma idéer för hur man vet vilka skillnader som var viktiga för den övergripande strukturen, och vilka som var mindre viktiga. Sedan lade de ner projektet efter ett tag.
Allen lämnade akademin för att bli mjukvaruutvecklare och Hébert-Dufresne startade sin egen forskargrupp i Vermont. Men det skulle bli ett kort uppehåll. Två år senare gick Allen med i Hébert-Dufresnes grupp i Vermont som doktorand och de fortsatte där de slutade.
"Vi sa alltid, 'låt oss avsluta det här nu'", säger Allen. "Det här blev ett skämt i åtta år."
I den sista pushen identifierade forskarna ett enkelt sätt att uppskatta fel - och att använda det i successiva kombinationer av par av nätverk. I uppsatsen använder forskarna spridningen av sjukdomar som en mätstav för att bedöma och validera metoden.
"Anta att det finns en pandemi", säger Moore. Om två personer – Alice och Bob – träffas och sedan två andra personer – säg Bob och Charlene – träffas, kan sjukdomen spridas från Alice till Charlene men inte tvärtom. Ordningen på dessa länkar spelar roll, vilket betyder att det är missvisande att kombinera dem till en ögonblicksbild (och behandla dem som om de är samtidiga).
Den nya metoden lånar en idé från kvantmekaniken för att identifiera den här typen av fel. I det fältet kan "kommutatorn" avslöja hur mycket ordning som spelar roll i beräkningar som involverar saker som energi och momentum. I den nya applikationen använde forskarna en kommutator för att bestämma hur mycket ordning som spelar roll och när det är korrekt att kombinera ögonblicksbilder.
"Detta låter oss förenkla historien om nätverkets struktur så mycket som möjligt samtidigt som vi behåller noggrannheten", säger Moore. Det pekar också på ett sätt att tämja en enorm, otymplig datauppsättning till en mindre, hanterbar uppsättning nätverk.
Allen säger att det skulle kunna utvidgas till andra dynamiska system som spridning av information över ett socialt medianätverk.
Mer information: Andrea J. Allen et al, Compressing the Chronology of a Temporal Network with Graph Commutators, Physical Review Letters (2024). DOI:10.1103/PhysRevLett.132.077402
Tillhandahålls av Santa Fe Institute
