Les auteurs ont testé l'approche SpringRank sur des jeux de données synthétiques, où les classements de vérité terrain sont connus, et comparé les résultats à d'autres méthodes de classement. Crédit :Caterina De Bacco, Daniel B. Larremore, et Christophe Moore
Parfois, savoir qui gagne et qui perd est plus important que la façon dont le jeu est joué.
Dans un article publié cette semaine dans Avancées scientifiques , des chercheurs du Santa Fe Institute décrivent un nouvel algorithme appelé SpringRank qui utilise les gains et les pertes pour trouver rapidement les classements cachés dans les grands réseaux. Testé sur un large éventail de jeux de données synthétiques et réels, allant des équipes dans un tournoi de basket-ball universitaire de la NCAA au comportement social des animaux, SpringRank a surpassé les autres algorithmes de classement en termes de prédiction des résultats et d'efficacité.
la physicienne Caterina De Bacco, un ancien boursier postdoctoral au Santa Fe Institute, maintenant à l'Université Columbia, affirme que SpringRank utilise des informations déjà intégrées au réseau. Il analyse les résultats des rencontres individuelles, ou par paire, interactions entre individus. Pour classer les équipes de basket-ball de la NCAA, par exemple, l'algorithme traiterait chaque équipe comme un nœud individuel, et représentez chaque jeu comme un avantage qui mène du gagnant au perdant. SpringRank analyse ces bords, et dans quelle direction ils voyagent, déterminer une hiérarchie. Mais c'est plus compliqué que d'attribuer simplement le classement le plus élevé à l'équipe qui a remporté le plus de matchs; après tout, une équipe qui joue exclusivement contre des équipes moins bien classées peut ne pas mériter d'être au sommet.
Comparaison des méthodes de classement SpringRank et Regularized Bradley-Terry-Luce (BTL) pour prédire une variété d'ensembles de données. Crédit :Caterina De Bacco, Daniel B. Larremore, et Christophe Moore
"Ce n'est pas seulement une question de victoires et de défaites, mais contre quelles équipes tu as battu et contre lesquelles tu as perdu, " dit le mathématicien Dan Larremore, un ancien stagiaire postdoctoral au Santa Fe Institute, maintenant à l'Université du Colorado Boulder. Larremore et De Bacco ont collaboré avec l'informaticien Cris Moore, également à l'Institut Santa Fe, sur le papier.
Comme son nom l'indique, SpringRank traite les connexions entre les nœuds comme des ressorts physiques qui peuvent se contracter et se dilater. Parce que les physiciens connaissent depuis longtemps les équations qui décrivent les mouvements des ressorts, dit De Bacco, l'algorithme est facile à mettre en œuvre. Et contrairement à d'autres algorithmes de classement qui attribuent des nombres ordinaux aux nœuds. seconde, troisième, etc., :SpringRank attribue à chaque nœud un nombre à valeur réelle. Par conséquent, les nœuds peuvent être rapprochés, écartées, ou disposés en motifs plus compliqués et révélateurs, comme des clusters de nœuds classés de manière similaire.
"Les idées de la physique nous donnent souvent des algorithmes élégants et efficaces, " dit Moore. " C'est une autre victoire pour cette approche. "
Les classements de basket-ball de la NCAA ne sont qu'un domaine dans lequel le nouvel algorithme SpringRank surpasse ses concurrents. Dans le schéma ci-dessus, les points au-dessus de la ligne montrent des essais où SpringRank a prédit les matchs avec plus de précision. Crédit :Caterina De Bacco, Dan Larremore, et Cris Moore
Dans le journal, les chercheurs ont testé le pouvoir prédictif de SpringRank sur une variété d'ensembles de données et de situations, y compris les tournois sportifs, comportements de dominance animale chez les perruches captives et les éléphants d'Asie en liberté, et les pratiques d'embauche des professeurs dans les universités.
Les chercheurs ont téléchargé le code de SpringRank sur GitHub, un référentiel de code en ligne, et disent qu'ils espèrent que d'autres chercheurs, surtout en sciences sociales, l'utilisera. "Il peut être appliqué à n'importe quel ensemble de données, " dit De Bacco.
Le prochain ensemble de données qu'elle et ses coauteurs prévoient d'analyser avec SpringRank ne ressemble à aucun de ceux présentés dans le Avancées scientifiques papier. Ils travailleront avec Elizabeth Bruch, un professeur externe au Santa Fe Institute, pour analyser les modèles de messagerie sur les marchés de rencontres en ligne.
