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.
Read the paper, "A physical model for efficient ranking in networks," in Science Advances (July 20, 2018)