Sådan sporer du vigtige ændringer i et dynamisk netværk

Netværk kan repræsentere skiftende systemer, såsom spredningen af ​​en epidemi eller væksten af ​​grupper i en befolkning af mennesker. Men strukturen af ​​disse netværk kan også ændre sig, efterhånden som links opstår eller forsvinder over tid. For bedre at forstå disse ændringer studerer forskere ofte en række statiske "snapshots", der fanger netværkets struktur i løbet af en kort varighed.

Netværksteoretikere har søgt måder at kombinere disse øjebliksbilleder på. I et nyt papir i Physical Review Letters , beskriver en trio af SFI-tilknyttede forskere en ny måde at aggregere statiske snapshots i mindre klynger af netværk, samtidig med at systemets dynamiske natur bevares. Deres metode, inspireret af en idé fra kvantemekanikken, indebærer at teste på hinanden følgende netværkssnapshots for at finde dem, for hvilke en kombination ville resultere i den mindste effekt på systemets dynamik – og derefter kombinere dem.

Det er vigtigt, at det kan bestemme, hvordan historien om netværkets struktur kan forenkles så meget som muligt, samtidig med at nøjagtigheden bevares. Matematikken bag metoden er ret enkel, siger hovedforfatter Andrea Allen, nu dataforsker ved Children's Hospital of Philadelphia.

"Vi er virkelig begejstrede for at kunne dele det, og det er et under, at ingen andre har offentliggjort denne præcise idé i det sidste årti," siger Allen. Hun samarbejdede med SFI-professor Cris Moore, en fysiker og matematiker, og Laurent Hébert-Dufresne, en kompleksitetsforsker ved University of Vermont og en tidligere SFI James S. McDonnell Foundation Fellow.

I det publicerede papir fremstår metoden ikke kompliceret; i virkeligheden udviklede det sig over år både på og uden for SFI. Samarbejdet begyndte i 2015, da Allen, der dengang var bachelor i matematik, besøgte SFI i en måned om vinteren og derefter, i sommeren 2016, vendte tilbage for at deltage i Research Experiences for Bachelor-programmet (nu kaldet Undergraduate Complexity Research-programmet) .

Hébert-Dufresne havde fået et stort datasæt, erhvervet fra satellittelefondata, der brugte mobiltelefon-"pings" til at vise, hvordan folk bevægede sig rundt. Han var interesseret i at finde fællesskaber, men han ønskede også at kunne måle, om forskellige fællesskaber krævede forskellig dataopløsning.

"Skal epidemiovervågningssystemer for eksempel være ensartede på tværs af samfund, når vi ved, at forskellige samfund har forskellig adfærd?"

Det spørgsmål førte til endnu mere:"På hvilket niveau kan vi aggregere dette, mens vi stadig opretholder forskellene? Og hvordan ved vi det?" spørger Allen. "Vi ønsker ikke at miste integriteten af ​​det netværk, vi forsøger at studere."

De bragte Moore ind for at brainstorme ideer til, hvordan man ved, hvilke forskelle der var vigtige for den overordnede struktur, og hvilke der var mindre vigtige. Så skrinlagde de projektet efter et stykke tid.

Allen forlod den akademiske verden for at blive softwareudvikler, og Hébert-Dufresne startede sin egen forskningsgruppe i Vermont. Men det ville blive en kort pause. To år senere sluttede Allen sig til Hébert-Dufresnes gruppe i Vermont som kandidatstuderende, og de fortsatte, hvor de slap.

"Vi sagde altid, 'lad os afslutte det her nu'," siger Allen. "Denne slags blev en joke i otte år."

I det sidste skub identificerede forskerne en ligetil måde at tilnærme fejl - og bruge den i successive kombinationer af netværkspar. I papiret bruger forskerne spredning af sygdom som en målestok til at vurdere og validere metoden.

"Antag, at der er en pandemi," siger Moore. Hvis to mennesker - Alice og Bob - mødes, og så to andre mennesker - siger Bob og Charlene - mødes, så kan sygdommen spredes fra Alice til Charlene, men ikke omvendt. Rækkefølgen af ​​disse links har betydning, hvilket betyder, at det er vildledende at kombinere dem til ét øjebliksbillede (og behandle dem, som om de er samtidige).

Den nye metode låner en idé fra kvantemekanikken til at identificere denne slags fejl. I det felt kan "kommutatoren" afsløre, hvor meget orden betyder noget i beregninger, der involverer ting som energi og momentum. I den nye applikation brugte forskerne en kommutator til at bestemme, hvor meget rækkefølgen betyder noget, og hvornår det er nøjagtigt at kombinere snapshots.

"Dette lader os forenkle historien om netværkets struktur så meget som muligt og samtidig bevare nøjagtigheden," siger Moore. Det peger også på en måde at tæmme et enormt, uhåndterligt datasæt til et mindre, håndterbart sæt netværk.

Allen siger, at det kunne udvides til andre dynamiske systemer som spredning af information over et socialt medie-netværk.

Flere oplysninger: 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

Leveret af Santa Fe Institute