分析贏家和輸家可以揭示網(wǎng)絡(luò)內(nèi)的排名

有時(shí)，知道誰贏了誰輸了比比賽更重要。

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

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

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

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

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

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

研究人員將SpringRank的代碼上傳到在線代碼庫GitHub，并表示希望其他研究人員，特別是社會(huì)科學(xué)領(lǐng)域的研究人員使用它。“它可以應(yīng)用于任何數(shù)據(jù)集，”De Bacco說。