分析赢家和输家可以揭示网络内的排名

有时，知道谁赢了谁输了比比赛更重要。

在本周发表在Science Advances上的一篇论文中，来自Santa Fe Institute的研究人员描述了一种名为SpringRank 的新算法，该算法利用输赢来快速找到潜伏在大型网络中的排名。在各种合成和真实世界数据集上进行测试，从NCAA大学篮球锦标赛的团队到动物的社会行为，SpringRank在预测结果和效率方面优于其他排名算法。

物理学家Caterina De Bacco是哥伦比亚大学Santa Fe研究所的前博士后研究员，他说SpringRank使用的信息已经内置于网络中。它分析了个体之间一对一或成对的相互作用的结果。例如，为了对NCAA篮球队进行排名，该算法会将每个队伍视为一个单独的节点，并将每个游戏视为从胜者到失败者的优势。SpringRank分析这些边缘以及它们行进的方向，以确定层次结构。但这比简单地将最高排名分配给赢得最多游戏的团队要复杂得多; 毕竟，一支专门打低级别球队的球队可能不应该排在首位。

“这不仅仅是一个输赢的问题，而是你击败的哪支球队，以及你输给的球队，”数学家Dan Larremore说，他是Santa Fe研究所的前博士后研究员，现在在科罗拉多大学博尔德分校。Larremore和De Bacco在圣菲研究所与计算机科学家Cris Moore合作。

顾名思义，SpringRank将节点之间的连接视为可收缩和扩展的物理弹簧。因为物理学家早就知道描述弹簧运动的方程式，De Bacco说，算法很容易实现。与将序数分配给节点的其他排序算法(第一，第二，第三等)不同，SpringRank为每个节点分配一个实数值。结果，节点可以靠近在一起，分开，或者以更复杂和显露的模式排列，例如类似排序的节点的集群。

“来自物理学的想法经常为我们提供优雅而有效的算法，”摩尔说。“这是这种方法的又一次胜利。”

在论文中，研究人员测试了SpringRank对各种数据集和情境的预测能力，包括体育比赛，圈养鹦鹉和自由放养的亚洲大象中的动物优势行为，以及大学之间的教师招聘实践。

研究人员将SpringRank的代码上传到在线代码库GitHub，并表示希望其他研究人员，特别是社会科学领域的研究人员使用它。“它可以应用于任何数据集，”De Bacco说。