近日, Santa Fe 研究所在Science Advances 发表论文, 提出一种名为SpringRank 的新算法, 该算法利用输赢快速找到潜伏在大型网络中的排名。当在各种合成和真实世界数据集上进行测试时, 从NCAA 大学篮球锦标赛的团队到动物的社会行为,SpringRank 在预测结果和效率方面优于其他排名算法。

  Santa Fe 研究所的三名科学家合作完成了该论文, 物理学家Caterina De Bacco 表示SpringRank 使用的信息已经内置于网络中, 分析了个体之间一对一或成对相互作用的结果。例如, 为了对NCAA 篮球队进行排名, 算法会将每个队伍视为一个单独的节点, 并将每场比赛视为从胜利者连向失败者的一条边。SpringRank 通过分析这些边以及它们的方向, 以确定层次结构。但它比简单地将赢得比赛最多的团队排在第一名更加复杂, 毕竟一支低级别球队很可能不值得上榜。数学家Dan Larremore说: “这不只是一个输赢的问题, 而是你击败了哪支球队, 以及你输给了哪支球队。”

  顾名思义, SpringRank 将节点之间的连接视为可收缩和扩展的物理弹簧。描述弹簧运动的方程式算法很容易实现。并且与为节点分配序数的其他排序算法不同, SpringRank 为每个节点分配一个实数值。节点可以靠近在一起、分开或者以更复杂和显露的模式排列, 例如类似排序节点的集群。

  在该论文中, 研究人员测试了SpringRank 在各种数据集和情境中的预测能力。研究人员已将SpringRank 的代码上传到在线代码库GitHub, 并表示希望其他研究人员, 特别是社会科学领域的研究人员使用它。

  参考文献: Caterina De Bacco, Daniel B. Larremore, Cristopher Moore. A Physical Model for Efficient Ranking in Networks. Science Advances, 2018; 4(7): eaar8260 DOI:10.1126/sciadv.aar8260.

  (编译自: https://www.sciencedaily.com/releases/2018/07/180720140514.htm)

(本刊讯)