Parakeet pecking orders, basketball match-ups, and the tenure-track: How analyzing winners and losers can reveal rank within networks

Santa Fe Institute's picture
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. (Image courtesy Caterina De Bacco, Dan Larremore, and Cris Moore)

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

In a paper published today in Science Advances, researchers from the Santa Fe Institute describe a new algorithm 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.

“It’s not just a matter of wins and losses, but which teams you beat and which you lost to,” says mathematician Dan Larremore, former Omidyar Fellow, 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.”

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.

SpringRank outperformed other widely used algorithms when tested on synthetic datasets, where the ground-truth ranking was known. 

Share
News Media Contact

Jenna Marshall

Manager of Communications
marshall@santafe.edu
505-946-2798 (desk)

More SFI News

July 20th, 2018

Parakeet pecking orders, basketball match-ups, and the tenure-track: How analyzing winners and losers can reveal rank within networks

July 19th, 2018

Video: After Trump and Brexit: A New Economics (Forget Red and Blue)

July 18th, 2018

Study: Concentrated wealth in agricultural populations may account for the decline of polygyny

July 13th, 2018

New algorithm limits bias in machine learning

July 10th, 2018

Working group to discuss climate change and the human niche

June 25th, 2018

Workshop explores team culture and human performance

June 20th, 2018

Cooler computing through statistical physics?

June 20th, 2018

Video: James Hartle, Sean Carroll, David Krakauer and Jenniffer Ouellette on The Nature of Time

Copy this html code to your website/blog to embed this press release.

Comments

Post new comment

3 + 0 =

To prevent automated spam submissions leave this field empty.