Soms, weten wie er wint en wie verliest is belangrijker dan hoe het spel wordt gespeeld.

In een artikel dat deze week is gepubliceerd in wetenschappelijke vooruitgang , onderzoekers van het Santa Fe Institute beschrijven een nieuw algoritme genaamd SpringRank dat winsten en verliezen gebruikt om snel rankings te vinden die op de loer liggen in grote netwerken. Wanneer getest op een breed scala aan synthetische en real-world datasets, variërend van teams in een NCAA college basketbaltoernooi tot het sociale gedrag van dieren, SpringRank presteerde beter dan andere ranking-algoritmen in het voorspellen van resultaten en in efficiëntie.

Natuurkundige Caterina De Bacco, een voormalig postdoctoraal onderzoeker aan het Santa Fe Institute, nu aan de Columbia University, zegt dat SpringRank informatie gebruikt die al in het netwerk is ingebouwd. Het analyseert de resultaten van een-op-een, of paarsgewijs, interacties tussen individuen. Om NCAA-basketbalteams te rangschikken, bijvoorbeeld, het algoritme zou elk team als een individueel knooppunt behandelen, en vertegenwoordig elk spel als een voorsprong die van de winnaar naar de verliezer leidt. SpringRank analyseert die randen, en in welke richting ze reizen, om een ​​hiërarchie te bepalen. Maar het is ingewikkelder dan simpelweg de hoogste ranking toe te kennen aan het team dat de meeste games heeft gewonnen; ten slotte, een team dat uitsluitend laaggeklasseerde teams speelt, verdient het misschien niet om aan de top te staan.

"Het is niet alleen een kwestie van winnen en verliezen, maar welke teams je hebt verslagen en van welke je hebt verloren, " zegt wiskundige Dan Larremore, een voormalig postdoctoraal onderzoeker aan het Santa Fe Institute, nu aan de Universiteit van Colorado Boulder. Larremore en De Bacco werkten samen met computerwetenschapper Cris Moore, ook aan het Santa Fe Instituut, op het papier.

Zoals de naam al doet vermoeden, SpringRank behandelt de verbindingen tussen knooppunten als fysieke veren die kunnen samentrekken en uitzetten. Omdat natuurkundigen al lang de vergelijkingen kennen die de bewegingen van veren beschrijven, zegt De Bacco, het algoritme is eenvoudig te implementeren. En in tegenstelling tot andere rangschikkingsalgoritmen die rangtelwoorden toewijzen aan knooppunten—eerst, tweede, derde, enzovoort., —SpringRank kent aan elk knooppunt een getal met reële waarde toe. Als resultaat, knooppunten kunnen dicht bij elkaar liggen, uitspreiden, of gerangschikt in meer gecompliceerde en onthullende patronen, zoals clusters van gelijk gerangschikte knooppunten.

"Ideeën uit de natuurkunde geven ons vaak elegante en effectieve algoritmen, "zegt Moore. "Dit is weer een overwinning voor die aanpak."

In de krant, de onderzoekers testten de voorspellende kracht van SpringRank op verschillende datasets en situaties, inclusief sporttoernooien, dominantiegedrag van dieren bij in gevangenschap levende parkieten en vrijlopende Aziatische olifanten, en het inhuren van docenten bij universiteiten.

De onderzoekers uploadden de code voor SpringRank naar GitHub, een online coderepository, en zeggen dat ze hopen dat andere onderzoekers, vooral in de sociale wetenschappen, zal het gebruiken. "Het kan worden toegepast op elke dataset, ’ zegt De Bacco.

De volgende dataset die zij en haar co-auteurs van plan zijn te analyseren met SpringRank is anders dan die in de wetenschappelijke vooruitgang papier. Ze werken samen met Elizabeth Bruch, een externe professor aan het Santa Fe Institute, om patronen van berichten in online datingmarkten te analyseren.