分層PageRank算法和逆序系數在鐵路網絡中的應用

劉芝秀，熊 可，黃小杰*

(1.南昌工程學院理學院,江西 南昌 330099;2.江西財經大學統計學院,江西 南昌 330077)

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

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

1 數據來源

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

2 主要算法和概念

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

2.1 分層PageRank算法

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

圖1 分層網絡示意圖

分層將一個大的網絡分成了若干小網絡，其優點是可以并行計算第1層網絡和第2層各個子網絡結點的PageRank值，再綜合計算出整個綜合網絡的PageRank值，即未分層網絡的PageRank值。

分層PageRank算法步驟：

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

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

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

圖2 站點連接與往返列車班次示意圖

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

則轉移概率矩陣M={mij}為

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

(d) 對初始向量關于轉移概率矩陣做帶平滑項的迭代，即

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

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

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

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

(g) 輸入第1層次站點所對應的第2層次子網絡中各列車站點間的往返列車班次數據矩陣，類似步驟(b)～(f)，計算第2層次子網絡各列車站點的PageRank值，設第2層次的第k個子網絡中含有的結點數為mk，k=1,2,…,n，記它們的PageRank值為

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

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

R(k)rk(mk))T

(1)

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

表1 綜合PageRank值的計算

2.2 逆序系數—兩種排序差異的度量指標

利用上述分層PageRank算法計算各城市列車站點的PageRank值并排序，通過對比以GDP為標準而進行的城市排名，可以佐證PageRank值是否較好的反映了城市站點的重要性，這是因為城市GDP反映了城市的經濟發展情況，從某種角度可以認為經濟越發達的城市越重要，該城市列車站點自然也越重要，那么用城市GDP排序佐證城市列車站點的PageRank排序的關鍵的問題就是如何度量兩種排序的差異。下面采用逆序系數來進行衡量，其思想來自定義方陣行列式時所采用的序列逆序數的概念[8]，它的具體概念如下：

設有n個城市，根據其GDP排序依次為A1,A2,…,An，而根據其列車站點的PageRank值排序為Ak1,Ak2,…,Akn，其中Aki∈{A1,A2,…,An}。

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

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

3 數據實驗

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

以城市GDP的排序序號為準，表2的城市根據列車站點的第1層PageRank值調整后，城市對應的序號列表如下，如北京對應2，鄭州對應11，上海對應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 直轄和省會城市的第1層PageRank值

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

表3 江西城市第2層PageRank值

表4 江蘇城市第2層PageRank值

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

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

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

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

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

迭代時，如果Rt+1與Rt能充分接近，說明極限存在，將上述迭代格式兩邊取極限(Rt→R)，那么迭代計算R則變為求解線性方程組

(2)

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

表2至表5中PageRank值計算流程圖如下

圖3 表2至表5中的PageRank值的計算流程圖

4 分析與結果

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

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

5 補充說明

最后需要補充說明的是，由兩個第2層子網絡構成的綜合網絡的逆序系數不一定總在第2層子網絡的兩個逆序系數之間，但是已知第2層子網絡的逆序系數，是可以給出綜合網絡逆序系數的上下界估計的。推而廣之，由d個第2層子網絡構成的綜合網絡，其逆序系數的估計也可以給出，其下界估計是

(3)

而上界估計是

(4)

其中τi，ni分別表示第2層網絡中第i個子網絡的逆序系數和第i個子網絡的結點個數，i=1,2,…,d。

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

無論哪種情況，逆序個數都不會減少，而新增逆序個數要么為0，要么最多為3×4，原有的逆序數為

圖4 子網絡結點的綜合排序示意圖

τA3(3-1)/2和τB4(4-1)/2，所以綜合網絡的逆序個數在

之間，而綜合網絡的總結點數變為了3+4，所以逆序系數在

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

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