I (a) visar vi ett slumpmässigt växande nätverk med Poisson out-grade. I (b) visar vi de bakre marginalerna för fyra representativa noder, färgade för att matcha (a), och jämför de som erhålls med vår metod med de exakta resultaten av uttömmande uppräkning. Trots förekomsten av korta cykler, närmar vår trospridningsmetod marginalerna ganska nära, och matchar inte bara medlen utan formerna för dessa fördelningar. Kredit:Physical Review E (2022). DOI:10.1103/PhysRevE.105.L052303
Världen är full av rankningar och beställningar. De dyker upp i tennis — som i French Open, som slutar med en slutlig ranking av mästarspelare. De dyker upp i pandemier – som när folkhälsotjänstemän kan registrera nya infektioner och använda kontaktspårning för att skissa nätverk av spridning av covid-19. System av konkurrens, konflikter och spridning kan alla ge upphov till hierarkier.
Dessa hierarkier observeras dock i efterhand. Det gör det svårt att veta den verkliga rankingen av systemet:Vem var egentligen den bästa spelaren? Vem smittade vem? "Du kan inte gå tillbaka i tiden och lära dig exakt hur det här hände", säger SFI-postdoktor George Cantwell. Man skulle kunna bygga en modell av nätverket och jämföra alla möjliga resultat, men en sådan brute-force-strategi blir snabbt ohållbar. Om du till exempel försökte ranka en grupp med bara 60 deltagare, når antalet möjliga permutationer antalet partiklar i det kända universum.
För en nyligen publicerad artikel publicerad i Physical Review E Cantwell samarbetade med SFI-professor Cris Moore, en datavetare och matematiker, för att beskriva ett nytt sätt att utvärdera rankningar. Deras mål var inte att hitta en sann hierarki, utan att beräkna spridningen av alla möjliga hierarkier, med var och en viktad efter sin sannolikhet.
"Vi var villiga att inte vara helt rätt, men vi ville få bra svar med viss känsla för hur bra de är," säger Cantwell. Den nya algoritmen är inspirerad av fysiken:Ranks modelleras som interagerande enheter som kan röra sig uppåt eller nedåt. Genom den linsen beter sig systemet sedan som ett fysiskt system som kan analyseras med metoder från spinglasteorin.
Strax efter starten av covid-19-pandemin började Cantwell och Moore fundera på modeller för hur sjukdomar sprids genom ett nätverk. De insåg snabbt situationen som ett ordningsproblem som uppstår med tiden, inte olikt spridningen av ett meme på sociala medier eller uppkomsten av mästerskapsrankningar inom professionell idrott. "Hur beställer man saker när man har ofullständig information?" frågar Cantwell.
De började med att föreställa sig en funktion som kunde få en rankning på noggrannhet. Till exempel:En bra ranking skulle vara en som överensstämmer med resultaten av matchningar 98 % av gångerna. En rankning som bara stämmer överens med resultaten 10 % av gångerna skulle vara usel – värre än en myntvändning utan några förkunskaper.
Ett problem med rankningar är att de vanligtvis är diskreta, vilket innebär att de följer hela talen:1, 2, 3 och så vidare. Denna ordning antyder att "avståndet" mellan de första och andra rankade medlemmarna är detsamma som mellan andra och tredje. Men så är det inte, säger Cantwell. Toppspelarna i ett spel, över hela världen, kommer att ligga nära varandra när det gäller skicklighet, så skillnaden mellan topprankade spelare kan vara närmare än det verkar.
"Man ser ganska ofta att lägre rankade spelare kan slå högre rankade spelare, och det enda sättet som modellen kan vara vettig och passa data är genom att klämma ihop alla led", säger Cantwell.
Cantwell och Moore beskrev ett system som utvärderar rankningar baserat på ett kontinuerligt numreringssystem. En rankning kan tilldela vilket reellt tal som helst – heltal, bråktal, oändligt upprepade decimaler – till en spelare i nätverket. "Kontinuerliga siffror är lättare att arbeta med," säger Cantwell, och dessa kontinuerliga siffror kan fortfarande översättas tillbaka till diskreta rankningar.
Dessutom kan detta nya tillvägagångssätt användas för att förutsäga något om framtiden, som resultatet av en tennisturnering, och även för att sluta sig till något om det förflutna, till exempel hur en sjukdom har spridit sig. "De här rankningarna kan berätta för oss ordningen på idrottslag från bäst till sämst. Men de kan också berätta för oss i vilken ordning människor i ett samhälle blev smittade av en sjukdom", säger Moore. "Även före sin postdoc arbetade George med det här problemet som ett sätt att förbättra kontaktspårningen i en epidemi. Precis som vi kan förutsäga vilket lag som kommer att vinna en match, kan vi sluta oss till vilken av två personer som infekterade den andra när de kom i kontakt med varandra."
I framtida arbete säger forskarna att de planerar att undersöka några av de djupare frågor som har dykt upp. Fler än en rankning kan instämma med data men är radikalt oense med andra rankningar, till exempel. Eller en rangordning som verkar felaktig kan ha hög osäkerhet men inte vara felaktig. Cantwell säger att han också vill jämföra modellens förutsägelser med resultat från verkliga tävlingar. I slutändan, säger han, kan modellen användas för att förbättra förutsägelser i ett brett utbud av system som leder till rankningar, från modeller för infektionssjukdomar till sportspel.
Cantwell säger att han kommer att hålla fast vid sina pengar - tills vidare. "Jag är inte riktigt redo att börja satsa på det", säger han. + Utforska vidare
