Författarna testade SpringRank-metoden på syntetiska datamängder, där sanningsrankningar är kända, och jämförde resultaten med andra rankningsmetoder. Kredit:Caterina De Bacco, Daniel B. Larremore, och Cristopher Moore
Ibland, att veta vem som vinner och vem som förlorar är viktigare än hur spelet spelas.
I en tidning som publicerades denna vecka i Vetenskapens framsteg , forskare från Santa Fe Institute beskriver en ny algoritm som heter SpringRank som använder vinster och förluster för att snabbt hitta rankningar som lurar i stora nätverk. När den testades på ett brett utbud av syntetiska och verkliga datauppsättningar, allt från lag i en NCAA college basketturnering till djurens sociala beteende, SpringRank överträffade andra rankningsalgoritmer när det gäller att förutsäga resultat och i effektivitet.
Fysikern Caterina De Bacco, en tidigare postdoktor vid Santa Fe Institute, nu vid Columbia University, säger SpringRank använder information som redan är inbyggd i nätverket. Den analyserar resultaten av en-mot-en, eller parvis, interaktioner mellan individer. För att ranka NCAA basketlag, till exempel, Algoritmen skulle behandla varje lag som en individuell nod, och representerar varje spel som en kant som leder från vinnaren till förloraren. SpringRank analyserar dessa kanter, och vilken riktning de reser, att bestämma en hierarki. Men det är mer komplicerat än att bara tilldela den högsta rankingen till det lag som vann flest matcher; trots allt, ett lag som uteslutande spelar lågt rankade lag kanske inte förtjänar att vara i toppen.
Jämförelse av SpringRank och Regularized Bradley-Terry-Luce (BTL) rankningsmetoder för att förutsäga en mängd olika datamängder. Kredit:Caterina De Bacco, Daniel B. Larremore, och Cristopher Moore
"Det är inte bara en fråga om vinster och förluster, men vilka lag du slog och vilka du förlorade mot, " säger matematiker Dan Larremore, en tidigare postdoktor vid Santa Fe Institute, nu vid University of Colorado Boulder. Larremore och De Bacco samarbetade med datavetaren Cris Moore, även på Santa Fe Institute, på pappret.
Som namnet antyder, SpringRank behandlar kopplingarna mellan noder som fysiska fjädrar som kan dra ihop sig och expandera. Eftersom fysiker länge har känt till ekvationerna som beskriver fjädrarnas rörelser, säger De Bacco, Algoritmen är lätt att implementera. Och till skillnad från andra rankningsalgoritmer som tilldelar noder ordningstal — först, andra, tredje, etc., —SpringRank tilldelar varje nod ett verkligt värde. Som ett resultat, noder kan vara nära varandra, utspridda, eller arrangerade i mer komplicerade och avslöjande mönster, som kluster av liknande rankade noder.
"Idéer från fysiken ger oss ofta eleganta och effektiva algoritmer, " säger Moore. "Detta är ännu en vinst för det tillvägagångssättet."
NCAA basketrankningar är bara ett område där den nya SpringRank-algoritmen överträffar konkurrenterna. I diagrammet ovan, poängen över linjen visar försök där SpringRank mer exakt förutspådde spel. Kredit:Caterina De Bacco, Dan Larremore, och Cris Moore
I tidningen, forskarna testade SpringRanks prediktiva kraft på en mängd olika datauppsättningar och situationer, inklusive sportturneringar, djurdominansbeteenden bland fångna parakiter och frigående asiatiska elefanter, och praxis för anställning av fakulteter bland universitet.
Forskarna laddade upp koden för SpringRank till GitHub, ett kodlager online, och säger att de hoppas att andra forskare, särskilt inom samhällsvetenskap, kommer att använda den. "Det kan appliceras på vilken datauppsättning som helst, säger De Bacco.
Nästa datauppsättning som hon och hennes medförfattare planerar att analysera med SpringRank är till skillnad från någon av dem som visas i Vetenskapens framsteg papper. De kommer att arbeta med Elizabeth Bruch, en extern professor vid Santa Fe Institute, att analysera meddelandemönster på onlinedejtingmarknader.
