Parakeet pecking orders and basketball match-ups—Analyzing winners and losers can reveal rank within networks

Parakeet pecking orders, basketball match-ups, and the tenure-track
The authors tested the SpringRank approach on synthetic datasets, where ground-truth rankings are known, and compared the results to other ranking methods. Credit: Caterina De Bacco, Daniel B. Larremore, and Cristopher Moore

Sometimes, knowing who wins and who loses is more important than how the game is played.

In a paper published this week in Science Advances, researchers from the Santa Fe Institute describe a new called SpringRank that uses wins and losses to quickly find rankings lurking in large networks. When tested on a wide range of synthetic and real-world datasets, ranging from teams in an NCAA college basketball tournament to the social behavior of animals, SpringRank outperformed other ranking algorithms in predicting outcomes and in efficiency.

Physicist Caterina De Bacco, a former postdoctoral fellow at Santa Fe Institute, now at Columbia University, says SpringRank uses information that's already built into the network. It analyzes the outcomes of one-on-one, or pairwise, interactions between individuals. To rank NCAA basketball teams, for example, the algorithm would treat each team as an individual node, and represent each game as an edge that leads from the winner to the loser. SpringRank analyzes those edges, and which direction they travel, to determine a hierarchy. But it's more complicated than simply assigning the highest ranking to the team that won the most games; after all, a team that exclusively plays low-ranked teams may not deserve to be at the top.

Parakeet pecking orders, basketball match-ups, and the tenure-track
Comparison of SpringRank and Regularized Bradley-Terry-Luce (BTL) ranking methods in predicting a variety of datasets. Credit: Caterina De Bacco, Daniel B. Larremore, and Cristopher Moore
"It's not just a matter of wins and losses, but which teams you beat and which you lost to," says mathematician Dan Larremore, a former postdoctoral fellow at the Santa Fe Institute, now at the University of Colorado Boulder. Larremore and De Bacco collaborated with computer scientist Cris Moore, also at the Santa Fe Institute, on the paper.

As its name suggests, SpringRank treats the connections between nodes like physical springs that can contract and expand. Because physicists have long known the equations that describe the motions of springs, says De Bacco, the algorithm is easy to implement. And unlike other ranking algorithms which assign ordinal numbers to nodes—first, second, third, etc.,—SpringRank assigns each node a real-valued number. As a result, nodes may be close together, spread apart, or arranged in more complicated and revealing patterns, like clusters of similarly ranked nodes.

"Ideas from physics often give us elegant and effective algorithms," says Moore. "This is another win for that approach."

Parakeet pecking orders, basketball match-ups, and the tenure-track
NCAA basketball rankings are just one area in which the new SpringRank algorithm outperforms competitors. In the diagram above, the points over the line show trials where SpringRank more accurately predicted games. Credit: Caterina De Bacco, Dan Larremore, and Cris Moore

In the paper, the researchers tested the predictive power of SpringRank on a variety of datasets and situations, including sports tournaments, animal dominance behaviors among captive parakeets and free-ranging Asian elephants, and faculty hiring practices among universities.

The researchers uploaded the code for SpringRank to GitHub, an online code repository, and say they hope other researchers, especially in the social sciences, will use it. "It can be applied to any dataset," says De Bacco.

The next dataset she and her coauthors plan to analyze with SpringRank is unlike any of those featured in the Science Advances paper. They'll be working with Elizabeth Bruch, an external professor at the Santa Fe Institute, to analyze patterns of messaging in online dating markets.


Explore further

A new tool for multilayer networks

More information: "A physical model for efficient ranking in networks" Science Advances (2018). DOI: 10.1126/sciadv.aar8260 , http://advances.sciencemag.org/content/4/7/eaar8260
Provided by Santa Fe Institute
Citation: Parakeet pecking orders and basketball match-ups—Analyzing winners and losers can reveal rank within networks (2018, July 20) retrieved 16 December 2018 from https://techxplore.com/news/2018-07-parakeet-basketball-match-upsanalyzing-winners-losers.html
This document is subject to copyright. Apart from any fair dealing for the purpose of private study or research, no part may be reproduced without the written permission. The content is provided for information purposes only.
19 shares

Feedback to editors

User comments

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more