分析贏家和輸家可以揭示網絡內的排名

有時，知道誰贏了誰輸了比比賽更重要。

在本周發(fā)表在Science Advances上的一篇論文中，來自Santa Fe Institute的研究人員描述了一種名為SpringRank 的新算法，該算法利用輸贏來快速找到潛伏在大型網絡中的排名。在各種合成和真實世界數據集上進行測試，從NCAA大學籃球錦標賽的團隊到動物的社會行為，SpringRank在預測結果和效率方面優(yōu)于其他排名算法。

物理學家Caterina De Bacco是哥倫比亞大學Santa Fe研究所的前博士后研究員，他說SpringRank使用的信息已經內置于網絡中。它分析了個體之間一對一或成對的相互作用的結果。例如，為了對NCAA籃球隊進行排名，該算法會將每個隊伍視為一個單獨的節(jié)點，并將每個游戲視為從勝者到失敗者的優(yōu)勢。SpringRank分析這些邊緣以及它們行進的方向，以確定層次結構。但這比簡單地將最高排名分配給贏得最多游戲的團隊要復雜得多; 畢竟，一支專門打低級別球隊的球隊可能不應該排在首位。

“這不僅僅是一個輸贏的問題，而是你擊敗的哪支球隊，以及你輸給的球隊，”數學家Dan Larremore說，他是Santa Fe研究所的前博士后研究員，現在在科羅拉多大學博爾德分校。Larremore和De Bacco在圣菲研究所與計算機科學家Cris Moore合作。

顧名思義，SpringRank將節(jié)點之間的連接視為可收縮和擴展的物理彈簧。因為物理學家早就知道描述彈簧運動的方程式，De Bacco說，算法很容易實現。與將序數分配給節(jié)點的其他排序算法(第一，第二，第三等)不同，SpringRank為每個節(jié)點分配一個實數值。結果，節(jié)點可以靠近在一起，分開，或者以更復雜和顯露的模式排列，例如類似排序的節(jié)點的集群。

“來自物理學的想法經常為我們提供優(yōu)雅而有效的算法，”摩爾說。“這是這種方法的又一次勝利。”

在論文中，研究人員測試了SpringRank對各種數據集和情境的預測能力，包括體育比賽，圈養(yǎng)鸚鵡和自由放養(yǎng)的亞洲大象中的動物優(yōu)勢行為，以及大學之間的教師招聘實踐。

研究人員將SpringRank的代碼上傳到在線代碼庫GitHub，并表示希望其他研究人員，特別是社會科學領域的研究人員使用它。“它可以應用于任何數據集，”De Bacco說。