分層PageRank算法和逆序系數(shù)在鐵路網(wǎng)絡(luò)中的應(yīng)用

劉芝秀，熊 可，黃小杰*

(1.南昌工程學(xué)院理學(xué)院,江西 南昌 330099;2.江西財(cái)經(jīng)大學(xué)統(tǒng)計(jì)學(xué)院,江西 南昌 330077)

鐵路交通是最為重要的公共基礎(chǔ)設(shè)施之一，是社會(huì)經(jīng)濟(jì)發(fā)展的重要支撐。隨著我國鐵路和高鐵建設(shè)的不斷推進(jìn)，其建設(shè)規(guī)模與技術(shù)都取得了巨大的成就，國內(nèi)各個(gè)城市和區(qū)域之間的交通往來更為便利。通常經(jīng)濟(jì)發(fā)達(dá)的地方其城際鐵路交通也較發(fā)達(dá)，顯然各城市列車站點(diǎn)的重要性是一個(gè)值得探討的問題，至少有助于分析鐵路網(wǎng)絡(luò)的安全性與效能。關(guān)于城市網(wǎng)絡(luò)結(jié)點(diǎn)重要性的計(jì)算，文獻(xiàn)[1]提出了一種適應(yīng)PageRank算法，此算法考慮了來源數(shù)據(jù)本身的重要程度，使城市網(wǎng)絡(luò)中來自相鄰結(jié)點(diǎn)的數(shù)據(jù)比來自較遠(yuǎn)結(jié)點(diǎn)的數(shù)據(jù)更有可能被考慮，并據(jù)此計(jì)算每個(gè)城市結(jié)點(diǎn)的重要性。

其中PageRank方法最初是用于評價(jià)互聯(lián)網(wǎng)上網(wǎng)站的知名度和重要性，它是由Page及其同事于1998年提出的[2]。經(jīng)過不斷的發(fā)展和改進(jìn)，PageRank方法已被廣泛的應(yīng)用于社會(huì)生活的各個(gè)方面，例如近期的文獻(xiàn)[3]將其應(yīng)用于挖掘各學(xué)科的優(yōu)秀和潛在人才，文獻(xiàn)[4]將其用于對負(fù)責(zé)生物狀態(tài)動(dòng)態(tài)變化的轉(zhuǎn)錄因子進(jìn)行排序，文獻(xiàn)[5]采用PageRank方法識(shí)別了光伏并網(wǎng)系統(tǒng)中的關(guān)鍵線路，文獻(xiàn)[6]將PageRank方法應(yīng)用于分析陜西省COVID-19患者動(dòng)態(tài)接觸網(wǎng)絡(luò)，文獻(xiàn)[7]也基于PageRank算法對號(hào)稱全球貿(mào)易先行“晴雨表”的中間品貿(mào)易的關(guān)鍵節(jié)點(diǎn)進(jìn)行了識(shí)別和分析。一般的，如果所研究的事物能夠用網(wǎng)絡(luò)連接圖模型來描述，PageRank方法就有其潛在的應(yīng)用價(jià)值，而城市間的鐵路交通網(wǎng)絡(luò)正是一個(gè)典型的網(wǎng)絡(luò)連接圖，本文基于這一事實(shí)，并考慮到我國直轄和省會(huì)城市在城市群中的特殊地位，而提出了便于并行計(jì)算的分層PageRank算法，結(jié)合各城市鐵路站點(diǎn)間往返列車班次數(shù)據(jù)，將其用于計(jì)算各城市鐵路站點(diǎn)的重要性及排名；為說明所計(jì)算的PageRank值能夠體現(xiàn)城市列車站點(diǎn)的重要性，本文還將城市列車站點(diǎn)的PageRank排名與2020年城市GDP排名進(jìn)行了比較，比較過程中引入了逆序系數(shù)的概念，逆序系數(shù)越大，兩種排序差異越大，而逆序系數(shù)越小，兩種排序越相近。數(shù)據(jù)實(shí)驗(yàn)的結(jié)果顯示城市列車站點(diǎn)的PageRank排名與城市GDP排名的逆序系數(shù)較小，兩者排名較近似，從而佐證了采用分層PageRank算法計(jì)算城市列車站點(diǎn)的重要性是有效的。

1 數(shù)據(jù)來源

本文所使用的鐵路列車班次數(shù)據(jù)來自12306網(wǎng)站。收集數(shù)據(jù)時(shí)，在12306允許查詢的時(shí)間范圍內(nèi)，隨機(jī)選擇了對2021年4月13日的列車班次進(jìn)行了查詢，收集了當(dāng)日國內(nèi)31個(gè)直轄和省會(huì)城市之間往返列車班次數(shù)據(jù)和江西、江蘇兩省省內(nèi)地級市之間往返列車班次數(shù)據(jù)。同時(shí)，通過百度查詢采集了2020年相應(yīng)各城市的GDP數(shù)據(jù)。

2 主要算法和概念

下面介紹本文的主要算法和概念，它包括用于計(jì)算城市列車站點(diǎn)重要性的分層PageRank算法和用于度量城市列車站點(diǎn)PageRank排名與城市GDP排名差異的逆序系數(shù)的概念，其基本步驟和原理分別如下：

2.1 分層PageRank算法

可以認(rèn)為對于一個(gè)城市，如果開往其站點(diǎn)的列車越多、開往的列車班次越多，則該城市的列車站點(diǎn)就越重要，這一點(diǎn)與互聯(lián)網(wǎng)網(wǎng)頁排名的基本假設(shè)完全類似，所以可以采用網(wǎng)頁的PageRank算法對各城市列車站點(diǎn)的重要性進(jìn)行計(jì)算，它仍然是分層PageRank算法的主體思想。不過在運(yùn)用PageRank算法對城市列車站點(diǎn)的重要性進(jìn)行計(jì)算時(shí)，可以充分利用已有信息，考慮城市行政級別的層次性和特殊地位，通常直轄和省會(huì)城市能在很大程度上反映本省級行政區(qū)域與區(qū)域外的鐵路連通情況。利用這一點(diǎn)可將我國城市鐵路網(wǎng)絡(luò)進(jìn)行分層，將整個(gè)城市鐵路網(wǎng)絡(luò)劃分為一些子網(wǎng)絡(luò)(以省級行政區(qū)為子網(wǎng)絡(luò)進(jìn)行劃分)，再在每個(gè)子網(wǎng)絡(luò)中選擇一個(gè)重要結(jié)點(diǎn)(以直轄和省會(huì)城市為該結(jié)點(diǎn))，這些重要結(jié)點(diǎn)構(gòu)成第1層次的鐵路站點(diǎn)網(wǎng)絡(luò)，而這些重要結(jié)點(diǎn)所在的子網(wǎng)絡(luò)均為第2層次的鐵路站點(diǎn)網(wǎng)絡(luò)(有多個(gè)第2層次子網(wǎng)絡(luò))，即把直轄和省會(huì)城市放在第一個(gè)網(wǎng)絡(luò)層次，把各省省會(huì)和省內(nèi)地級市放在第二個(gè)網(wǎng)絡(luò)層次。直觀表述如下圖1所示，細(xì)線圓圈結(jié)點(diǎn)構(gòu)成第1層次的網(wǎng)絡(luò)，細(xì)線圓圈表示的結(jié)點(diǎn)就是細(xì)線圓圈所圍的粗線圓圈所表示的結(jié)點(diǎn)中的某個(gè)重要的結(jié)點(diǎn)，而細(xì)線圓圈所圍繞的所有粗線圓圈所表示的結(jié)點(diǎn)則構(gòu)成了第2層次的網(wǎng)絡(luò)。

圖1 分層網(wǎng)絡(luò)示意圖

分層將一個(gè)大的網(wǎng)絡(luò)分成了若干小網(wǎng)絡(luò)，其優(yōu)點(diǎn)是可以并行計(jì)算第1層網(wǎng)絡(luò)和第2層各個(gè)子網(wǎng)絡(luò)結(jié)點(diǎn)的PageRank值，再綜合計(jì)算出整個(gè)綜合網(wǎng)絡(luò)的PageRank值，即未分層網(wǎng)絡(luò)的PageRank值。

分層PageRank算法步驟：

(a) 輸入第1層次n個(gè)列車站點(diǎn)間的往返列車班次數(shù)據(jù)矩陣P={pij}n×n，其中pij是從站點(diǎn)j到開往站點(diǎn)i的班車次數(shù)。

(b) 計(jì)算第1層次n個(gè)站點(diǎn)間的轉(zhuǎn)移概率矩陣M={mij}n×n，其中mij表示旅客從站點(diǎn)j到站點(diǎn)i的概率。根據(jù)往返列車班次數(shù)據(jù)矩陣P={pij}n×n計(jì)算轉(zhuǎn)移概率的公式如下:

這里假設(shè)了旅客以等可能性乘坐從站點(diǎn)j開往站點(diǎn)i的任意一趟班次的列車。

圖2 站點(diǎn)連接與往返列車班次示意圖

為直觀表述，見上圖2，設(shè)有A,B,C三地站點(diǎn)，它們間往返列車班次數(shù)據(jù)矩陣P={pij}為

則轉(zhuǎn)移概率矩陣M={mij}為

(c) 輸入阻尼因子d和初始向量R0，其中d∈(0，1)，此處取d=0.85，而初始向量R0=(R0(1),R0(2),…,R0(n))T設(shè)定了各個(gè)站點(diǎn)的初始重要性，滿足

(d) 對初始向量關(guān)于轉(zhuǎn)移概率矩陣做帶平滑項(xiàng)的迭代，即

其中I表示所有分量均為1的n維向量，t=0,1,2,…。

(e) 如果Rt+1與Rt充分接近，令R=Rt+1，停止迭代。

(f) 否則，令t=t+1，繼續(xù)執(zhí)行(d)步。

最后得到的R=(R(1),R(2),…,R(n))T即是第1層次各個(gè)站點(diǎn)的PageRank值，它表示第1層次各個(gè)列車站點(diǎn)的重要性。

(g) 輸入第1層次站點(diǎn)所對應(yīng)的第2層次子網(wǎng)絡(luò)中各列車站點(diǎn)間的往返列車班次數(shù)據(jù)矩陣，類似步驟(b)～(f)，計(jì)算第2層次子網(wǎng)絡(luò)各列車站點(diǎn)的PageRank值，設(shè)第2層次的第k個(gè)子網(wǎng)絡(luò)中含有的結(jié)點(diǎn)數(shù)為mk，k=1,2,…,n，記它們的PageRank值為

rk=(rk(1),rk(2),…,rk(mk))Tk=1,2,…,n

注意：此步驟可以與(a)～(f)同步進(jìn)行。

R(k)rk(mk))T

(1)

k=1,2,…,n。綜合PageRank值的計(jì)算亦可如下表1所示。

表1 綜合PageRank值的計(jì)算

2.2 逆序系數(shù)—兩種排序差異的度量指標(biāo)

利用上述分層PageRank算法計(jì)算各城市列車站點(diǎn)的PageRank值并排序，通過對比以GDP為標(biāo)準(zhǔn)而進(jìn)行的城市排名，可以佐證PageRank值是否較好的反映了城市站點(diǎn)的重要性，這是因?yàn)槌鞘蠫DP反映了城市的經(jīng)濟(jì)發(fā)展情況，從某種角度可以認(rèn)為經(jīng)濟(jì)越發(fā)達(dá)的城市越重要，該城市列車站點(diǎn)自然也越重要，那么用城市GDP排序佐證城市列車站點(diǎn)的PageRank排序的關(guān)鍵的問題就是如何度量兩種排序的差異。下面采用逆序系數(shù)來進(jìn)行衡量，其思想來自定義方陣行列式時(shí)所采用的序列逆序數(shù)的概念[8]，它的具體概念如下：

設(shè)有n個(gè)城市，根據(jù)其GDP排序依次為A1,A2,…,An，而根據(jù)其列車站點(diǎn)的PageRank值排序?yàn)锳k1,Ak2,…,Akn，其中Aki∈{A1,A2,…,An}。

考慮自然數(shù)序列k1,k2,…,kn，如果kp>kq(p

可以看出逆序系數(shù)取值在[0，1]之內(nèi)，逆序系數(shù)越小，兩種排序越接近，逆序系數(shù)越大，兩種排序差異越大。設(shè)有A、B兩組城市，按城市的GDP排名分別為A1,A2,A3,A4和B1,B2,B3,B4,B5，如果它們列車站點(diǎn)的PageRank排名分別為A3,A2,A1,A4和B4,B1,B2,B3,B5，則A組城市有(3,2)、(3,1)、(2,1)這3個(gè)逆序，逆序系數(shù)為τA=3/[4(4-1)/2]=1/2；而B組城市有(4,1)、(4,2)、(4,3)這3個(gè)逆序，逆序系數(shù)為τB=3/[5(5-1)/2]=3/10，因而認(rèn)為B組城市列車站點(diǎn)的PageRank排名比A組更接近其城市GDP排名。

3 數(shù)據(jù)實(shí)驗(yàn)

根據(jù)所采集的列車班次數(shù)據(jù)，并將直轄和省會(huì)城市作為第1層網(wǎng)絡(luò)結(jié)點(diǎn)，各省會(huì)城市和本省內(nèi)地級市作為第2層子網(wǎng)絡(luò)結(jié)點(diǎn)。由2.1節(jié)分層PageRank算法的(a)～(f)步，計(jì)算各直轄和省會(huì)城市的列車站點(diǎn)的第1層PageRank值如下表2的第2列，按PageRank值從大到小向下排列；表2的第3列城市名前面的序號(hào)是根據(jù)第4列GDP(單位為：億元)從大到小排序的序號(hào)。

以城市GDP的排序序號(hào)為準(zhǔn)，表2的城市根據(jù)列車站點(diǎn)的第1層PageRank值調(diào)整后，城市對應(yīng)的序號(hào)列表如下，如北京對應(yīng)2，鄭州對應(yīng)11，上海對應(yīng)1等等：

[2,11,1,8,7,10,19,6,9,14,12,3,18,13,23,5,20,4,26,17,21,16,24,15,22,30,28,27,25,31,29]

表2 直轄和省會(huì)城市的第1層PageRank值

由2.1節(jié)分層PageRank算法的(g)步，計(jì)算江西和江蘇兩省省內(nèi)地級市列車站點(diǎn)的第2層PageRank值，如下表3和表4的第2列。

表3 江西城市第2層PageRank值

表4 江蘇城市第2層PageRank值

同上，由表3與表4可知，江西和江蘇兩省城市站點(diǎn)的第2層PageRank值排序和城市GDP排序的逆序系數(shù)分別為：

由2.1節(jié)分層PageRank算法的(h)步，計(jì)算江西和江蘇兩省省內(nèi)地級市列車站點(diǎn)的綜合PageRank值如下表5的第2列

表5 江西、江蘇兩省城市綜合PageRank值

由表5可知，江西江蘇兩省城市站點(diǎn)的綜合PageRank值排序和城市GDP排序的逆序系數(shù)為：

對于通常PageRank的計(jì)算有許多不同的數(shù)值計(jì)算方法，例如文獻(xiàn)[9]和[10]分別提出了一種基于子空間的啟發(fā)式搜索算法和采用多冪次、多分裂的內(nèi)外迭代算法。而采用2.1節(jié)分層PageRank算法對上述表2至表5中的PageRank值進(jìn)行計(jì)算時(shí)，可以合并步驟(c)(d)(e)(f)。因?yàn)橥ㄟ^下述公式

迭代時(shí)，如果Rt+1與Rt能充分接近，說明極限存在，將上述迭代格式兩邊取極限(Rt→R)，那么迭代計(jì)算R則變?yōu)榍蠼饩€性方程組

(2)

對于線性方程組的求解，文獻(xiàn)[11-12]歸納了多種求解算法，可以使用已有且成熟的數(shù)學(xué)工具包進(jìn)行實(shí)驗(yàn)，其中R為PageRank值，d取0.85，n表示列車站點(diǎn)的個(gè)數(shù)，M表示列車站點(diǎn)間的轉(zhuǎn)移概率矩陣，I是所有分量均為1的n維向量。

表2至表5中PageRank值計(jì)算流程圖如下

圖3 表2至表5中的PageRank值的計(jì)算流程圖

4 分析與結(jié)果

在表2中可以看到，首都北京的第1層PageRank值排名第一，而表3和表4又可以看到江西和江蘇兩省的省會(huì)城市南昌和南京的第2層PageRank值都排第一，而綜合PageRank值排序仍然保持子網(wǎng)絡(luò)的原順序，見第5節(jié)補(bǔ)充說明部分的圖4解釋.直轄和省會(huì)城市的PageRank值排名第一與鐵路布局政策的傾向是吻合的。此外，在表2中還可以看到鄭州鐵路站點(diǎn)的PageRank值很大，這與鄭州站是國內(nèi)鐵路網(wǎng)絡(luò)的一個(gè)樞紐事實(shí)相吻合，同樣的，由表3和表4可以發(fā)現(xiàn)上饒和蘇州是江西和江蘇兩省省內(nèi)的重要鐵路交匯點(diǎn)，這些PageRank數(shù)據(jù)與事實(shí)的相符性在一定程度上說明了分層PageRank算法用于計(jì)算我國城市鐵路站點(diǎn)的重要性是合理的。

更進(jìn)一步的對比城市GDP排序，可以看出國內(nèi)31個(gè)直轄和省會(huì)城市構(gòu)成的第1層城市網(wǎng)絡(luò)的PageRank排序和GDP排序是比較接近的，逆序系數(shù)僅為0.2，與0更接近而與1相距更遠(yuǎn)，小于0.5；第2層PageRank值(0.4、0.205128)和綜合PageRank值(0.205128)也均小于0.5。這說明如果城市GDP可以反映城市的重要性(至少在經(jīng)濟(jì)發(fā)展角度上可以承認(rèn))，那么用分層PageRank算法計(jì)算的城市站點(diǎn)的重要性可以從城市GDP方面得到佐證。繼而可看到，江西城市站點(diǎn)的第2層網(wǎng)絡(luò)逆序系數(shù)0.4比江蘇城市站點(diǎn)的第2層網(wǎng)絡(luò)逆序系數(shù)0.205128要大；另外，江西和江蘇兩省城市網(wǎng)絡(luò)的綜合PageRank排序與GDP排序的逆序系數(shù)為0.286232，恰好在江西第2層城市網(wǎng)絡(luò)逆序系數(shù)0.4與江蘇第2層城市網(wǎng)絡(luò)逆序系數(shù)0.205128之間，說明如果把江西和江蘇作為一個(gè)綜合城市網(wǎng)絡(luò)來看，兩省城市站點(diǎn)綜合網(wǎng)絡(luò)比江蘇城市站點(diǎn)網(wǎng)絡(luò)變的偏離了GDP排序，但比江西城市站點(diǎn)網(wǎng)絡(luò)變得貼近了GDP排序，這反映了江西鐵路交通相比江蘇而言有進(jìn)一步提升加強(qiáng)的空間。這些計(jì)算結(jié)果更進(jìn)一步的說明了由分層PageRank算法計(jì)算的鐵路站點(diǎn)的PageRank值有效的刻畫了列車站點(diǎn)的重要性。

5 補(bǔ)充說明

最后需要補(bǔ)充說明的是，由兩個(gè)第2層子網(wǎng)絡(luò)構(gòu)成的綜合網(wǎng)絡(luò)的逆序系數(shù)不一定總在第2層子網(wǎng)絡(luò)的兩個(gè)逆序系數(shù)之間，但是已知第2層子網(wǎng)絡(luò)的逆序系數(shù)，是可以給出綜合網(wǎng)絡(luò)逆序系數(shù)的上下界估計(jì)的。推而廣之，由d個(gè)第2層子網(wǎng)絡(luò)構(gòu)成的綜合網(wǎng)絡(luò)，其逆序系數(shù)的估計(jì)也可以給出，其下界估計(jì)是

(3)

而上界估計(jì)是

(4)

其中τi，ni分別表示第2層網(wǎng)絡(luò)中第i個(gè)子網(wǎng)絡(luò)的逆序系數(shù)和第i個(gè)子網(wǎng)絡(luò)的結(jié)點(diǎn)個(gè)數(shù)，i=1,2,…,d。

為便于說明，下面以第2層三個(gè)結(jié)點(diǎn)的A網(wǎng)絡(luò)和四個(gè)結(jié)點(diǎn)的B網(wǎng)絡(luò)構(gòu)成的綜合網(wǎng)絡(luò)逆序系數(shù)估計(jì)為例進(jìn)行分析，根據(jù)2.1節(jié)分層PageRank算法(h)步的(1)式可知，子網(wǎng)絡(luò)結(jié)點(diǎn)在第2層網(wǎng)絡(luò)的PageRank排序與在綜合網(wǎng)絡(luò)中的綜合PageRank排序是保持一致的，綜合后可能發(fā)生兩類種情況，一類是兩組結(jié)點(diǎn)按原順序交叉排序，一類是兩組結(jié)點(diǎn)按原順序分離排序，如下圖4所示。

無論哪種情況，逆序個(gè)數(shù)都不會(huì)減少，而新增逆序個(gè)數(shù)要么為0，要么最多為3×4，原有的逆序數(shù)為

圖4 子網(wǎng)絡(luò)結(jié)點(diǎn)的綜合排序示意圖

τA3(3-1)/2和τB4(4-1)/2，所以綜合網(wǎng)絡(luò)的逆序個(gè)數(shù)在

之間，而綜合網(wǎng)絡(luò)的總結(jié)點(diǎn)數(shù)變?yōu)榱?+4，所以逆序系數(shù)在

之間，其中τA,τB分別是第2層子網(wǎng)絡(luò)A,B的逆序系數(shù)。用完全類似的推理可得，一般綜合網(wǎng)絡(luò)的逆序系數(shù)上下界估計(jì)式(3)和(4)，用(3)式和(4)式計(jì)算江西和江蘇兩省城市綜合網(wǎng)絡(luò)的逆序系數(shù)在

之間，這與江西江蘇兩省綜合逆序系數(shù)為0.286 232吻合。