Parakit-hakkeordrer og basketball-match-ups – Analyse af vindere og tabere kan afsløre rang inden for netværk

Sommetider, at vide hvem der vinder og hvem der taber er vigtigere end hvordan spillet spilles.

I et papir, der blev offentliggjort i denne uge i Videnskabens fremskridt , forskere fra Santa Fe Institute beskriver en ny algoritme kaldet SpringRank, der bruger sejre og tab til hurtigt at finde placeringer, der lurer i store netværk. Når testet på en bred vifte af syntetiske og virkelige datasæt, lige fra hold i en NCAA college basketball turnering til dyrs sociale adfærd, SpringRank klarede sig bedre end andre rangeringsalgoritmer med hensyn til at forudsige resultater og effektivitet.

Fysiker Caterina De Bacco, en tidligere postdoc ved Santa Fe Institute, nu på Columbia University, siger SpringRank bruger information, der allerede er indbygget i netværket. Den analyserer resultaterne af en-til-en, eller parvis, interaktioner mellem individer. For at rangere NCAA basketballhold, for eksempel, algoritmen vil behandle hvert hold som en individuel node, og repræsentere hvert spil som en kant, der fører fra vinderen til taberen. SpringRank analyserer disse kanter, og hvilken retning de bevæger sig i at bestemme et hierarki. Men det er mere kompliceret end blot at tildele den højeste placering til det hold, der vandt flest kampe; trods alt, et hold, der udelukkende spiller lavt rangerede hold, fortjener måske ikke at være i toppen.

"Det er ikke kun et spørgsmål om sejre og tab, men hvilke hold du slog, og hvilke du tabte til, " siger matematiker Dan Larremore, en tidligere postdoc ved Santa Fe Institute, nu ved University of Colorado Boulder. Larremore og De Bacco samarbejdede med datalog Cris Moore, også på Santa Fe Institute, på papiret.

Som navnet antyder, SpringRank behandler forbindelserne mellem noder som fysiske fjedre, der kan trække sig sammen og udvide sig. Fordi fysikere længe har kendt de ligninger, der beskriver fjedres bevægelser, siger De Bacco, Algoritmen er nem at implementere. Og i modsætning til andre rangeringsalgoritmer, der tildeler ordenstal til noder – først, sekund, tredje, etc., —SpringRank tildeler hver node et reelt værdiansat nummer. Som resultat, noder kan være tæt på hinanden, spredt fra hinanden, eller arrangeret i mere komplicerede og afslørende mønstre, som klynger af tilsvarende rangerede noder.

"Idéer fra fysikken giver os ofte elegante og effektive algoritmer, " siger Moore. "Dette er endnu en sejr for den tilgang."

I avisen, forskerne testede SpringRanks forudsigelsesevne på en række datasæt og situationer, herunder sportsturneringer, dyredominansadfærd blandt parakitter i fangenskab og fritgående asiatiske elefanter, og fakultetets ansættelsespraksis blandt universiteter.

Forskerne uploadede koden til SpringRank til GitHub, et online kodelager, og siger, at de håber, at andre forskere, især inden for samfundsvidenskab, vil bruge det. "Det kan anvendes på ethvert datasæt, " siger De Bacco.

Det næste datasæt, hun og hendes medforfattere planlægger at analysere med SpringRank, er ulig nogen af ​​dem, der er vist i Videnskabens fremskridt papir. De skal arbejde sammen med Elizabeth Bruch, en ekstern professor ved Santa Fe Institute, at analysere mønstre for meddelelser på online datingmarkeder.