编译：集智翻译组

来源：santafe.edu

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

NCAA 篮球排名只是新算法 SpringRank 胜出的领域之一。如上图所示，高于分割线的点表明 SpringRank 预测的比赛结果更加准确。（图片来自 Caterina De Bacco，Dan Larremore 和 Cris Moore）

有时候，知道谁赢谁输比知道比赛怎么打更加重要。

在7月20日发表在 Science Advances 上的一篇论文【1】中，来自圣塔菲研究所的研究员描述了一种名为 SpringRank 的新算法，该算法利用输赢揭示潜藏于大型网络中的位次信息。本研究测试了大量的人工合成以及真实数据的数据集，从 NCAA 大学篮球联赛团队数据到动物社会行为学数据。测试结果表明，SpringRank 算法的预测结果和效率优于其他排名算法。

哥伦比亚大学的物理学家 Caterina De Bacco 是圣塔菲研究所的博士后，他表示，SpringRank 使用的是已经内置在网络中的信息。本算法分析个体间两两相互作用的结果。例如，为了给 NCAA 篮球队排名，该算法会把每一个球队视为一个单独的节点，把一场比赛的输赢关系视作一条边，一条从胜利球队指向失败球队的边。SpringRank 会分析这些边，沿着边的方向遍历，以此确定层次结构。但这个算法过程不仅仅是“给赢的比赛最多的球队最高排名”；毕竟，一支专门虐菜鸟的球队不值得上榜。

现在科罗拉多大学博尔德分校的数学家 Dan Larremore 说，“这不仅仅是一个输赢问题，而是你击败了哪支球队以及你输给了哪支球队”。他曾是 Omidyar 的成员。Larremore、De Bacco 与圣塔菲的计算机学家 Cris Moore 合作了本论文。

顾名思义，SpringRank 将节点之间的连接视为可以伸缩的物理弹簧。 De Bacco 表示，因为物理学家早就知道描述弹簧运动的方程式，所以算法就很容易实现。不同于其他的那种“非得排出个一二三”的次序排名算法，SpringRank 为每一个节点分配一个实数值。因此，节点可以紧紧的挨在一起，也可以分离的很远，甚至显示出更为复杂的排列模式—— 相似的节点会组成集簇。

“来自物理学的思想经常为我们提供优雅又有效的算法，”Moore 说，“本成果这种方法的又一次胜利。”

在本论文中，研究人员测试了 SpringRank 算法在各种数据集和情境中的预测能力，包括体育比赛，圈养的鹦鹉与放养的亚洲象中的动物支配行为，以及大学里的教职招聘实践。

研究者把 SpringRank 的代码发布到了线上代码仓库 Github 【2】上。他们希望其他的研究者（特别是社会科学的研究者）能够试用本算法。De Bacco 表示：“本算法能胜任任何的数据库。”

她和她的合作者计划用 SpringRank 分析的下一个数据集与 Science Advances 精选过的任何论文都不同。他们将与圣塔菲研究所的外聘教授 Elizabeth Bruch 合作，分析在线约会平台的消息传递模式。

在真实排名是已知的人工合成数据集上进行测试时，SpringRank 的表现优于其他广泛使用的算法。

1. http://advances.sciencemag.org/content/4/7/eaar8260

2. https://github.com/cdebacco/SpringRank