财新传媒
位置:博客 > 集智俱乐部 > 圣塔菲研究所提出的新排序算法:从鹦鹉啄序到终身教职

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

编译:集智翻译组

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

推荐 0