圣塔菲研究所提出的新排序算法：从鹦鹉啄序到终身教职



啄序（Pecking order）或啄食顺序或啄食次序指群居动物通过争斗取得社群地位的阶层化及支配等级区分现象。

图片来源：Greg Matthews

编译：集智翻译组

来源：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

翻译：Leo

审校：李时嘉

编辑：李宇峰

原文地址：

https://www.santafe.edu/news-center/news/parakeet-pecking-orders-basketball-match-ups-and-tenure-track-how-analyzing-winners-and-losers-can-reveal-rank-within-networks

推荐阅读

活动预告

---

集智QQ群｜292641157

商务合作及投稿转载｜[e-mail]

◆ ◆ ◆

搜索公众号：集智俱乐部

加入“没有围墙的研究所”

让苹果砸得更猛烈些吧！