地鐵網絡節點的聚類分析與關鍵節點識別

薛 鋒 劉泳博 施 政 戶佐安* 何傳磊

(西南交通大學交通運輸與物流學院1) 成都 611756)(西南交通大學綜合交通大數據應用技術國家工程實驗室2) 成都 611756)(西南交通大學唐山研究生院3) 唐山 063000) (中鐵第一勘察設計院集團有限公司4) 西安 710043)

0 引 言

城市軌道交通網絡對城市公共交通系統具有重要支撐作用，網絡節點的暢通與否會影響城市軌道交通網絡的通行效率，嚴重時甚至會導致網絡的癱瘓.因此，對城市軌道交通網絡的關鍵節點進行有效識別，找出重要的“核心節點”，并通過重點保護這些“核心節點”提高整個地鐵網絡的可靠性，有助于提升網絡的運營安全和效率.

目前，對于城市軌道交通網絡關鍵節點識別的研究較多，大都是在復雜網絡節點重要度評估方法基礎上進行擴展，使用節點度、介數等指標對節點進行評價.Yang等[1]認為節點的重要度取決于度和介數兩個指標，但多個指標反映的結果往往不同，需要對多指標結果進一步分析，以得到更加完善結果.在這一過程中，有學者使用PageRank[2]、灰色關聯法[3]、TOPSIS[4]等方法對網絡節點的多個指標進行分析，得出節點重要程度的排名，但評價模型往往涉及多指標權重確定，這一環節的存在導致評價結果存在較大主觀性；其次在得出網絡節點重要度排名后，往往采用人為規定閾值的方法確定關鍵節點，主觀性較強，而使用聚類方法可以避免主觀因素對網絡關鍵節點識別的影響.蟻群聚類算法具有魯棒性、穩健性的特點，在實際應用中比較廣泛[5-7]，但蟻群聚類算法存在收斂慢，易陷入局部最優的缺點[8].

基于此，文中采用聚類分析的方法，根據評估節點重要度的指標對地鐵網絡節點進行分類，并構建了網絡關鍵節點識別的模型，采用改進的蟻群聚類算法對模型進行求解.選取最大連通子圖和網絡效率這兩個指標，分析不同節點類被隨機攻擊時網絡性能的下降趨勢，為地鐵網絡節點的維護提供參考.

1 地鐵網絡關鍵節點識別指標

評估網絡節點重要度的指標有很多，一般是從節點的度、介數、連通度等拓撲結構或脆弱性指標進行衡量[9]，但是地鐵網絡的節點重要度評估還需結合地鐵網絡的實際情況，不僅要反映節點在網絡中的重要性，還應體現車站周邊的經濟水平以及集散旅客、連接其他交通方式的能力.因此，根據已有的資料并結合文獻[4]和文獻[9]，選取識別地鐵網絡關鍵節點的指標，見圖1.

圖1 關鍵節點的識別指標

V1度，V2介數，V3補圖效率和V4連通度等指標根據文獻[4]中的公式計算所得，V5客運進站量用某一時間段內的日平均進站量計算所得，V7周邊資源根據地鐵站周邊的學校、醫院、商業街等資源評估所得，V8繁榮度則選擇車站所屬地區的人均GDP統計所得.

2 聚類識別關鍵節點類的原理及算法

地鐵網絡關鍵節點的識別可以采取聚類思想，通過將相同或相近屬性節點進行歸納[11-12]，將地鐵網絡關鍵節點找尋問題轉化為聚類問題來解決，其結果既能揭示不同類別的網絡節點內部的隱含關系，又能通過進一步的分析找出地鐵網絡中的關鍵節點類.

2.1 聚類分析進行關鍵節點類識別的原理

通過聚類來進行網絡關鍵節點識別的原理可以描述為：將地鐵網絡中的節點看作m維空間Rm中的n個向量(數據集)，把每個向量歸屬到K個聚類中的某一個，使每個向量與其聚類中心的距離最小，然后計算每個簇的類別中心值，中心值最大的那個簇即為網絡中的關鍵節點類，其數學模型描述如下所示：

已知地鐵網絡節點集X有n個節點和K個分類，每個節點有m個屬性，由此得到節點集矩陣為

(1)

將節點集中的n個節點進行聚類，在聚類過程中引入0-1決策變量wij，當節點Xi在j類節點S(j)中取值為1，否則取值為0，則有：

(2)

以每個節點與其聚類中心的距離最小為目標函數，構建網絡節點聚類的數學模型為

(3)

(4)

(5)

(6)

當JE最小時，聚類效果達到最佳.此時，類別中心值最大的簇即為關鍵節點簇，數學表達式為

(7)

(8)

2.2 關鍵節點識別的算法

蟻群聚類算法是一種基于螞蟻覓食行為的仿生算法，具有魯棒性強的優點，但是也存在容易陷入局部最優，在指定迭代次數的條件下很難找到最優解的缺點.

為了更好地運用蟻群聚類算法解決地鐵網絡關鍵節點的識別問題，需要對傳統的蟻群聚類算法進行改進.本文結合遺傳算法中的變異思想，對蟻群聚類算法進行改進，改進后的算法流程如下.

步驟1初始化算法的參數.

步驟2確定初始解.根據信息矩陣中信息素的值和狀態轉移概率確定螞蟻行走路徑，并進行標識，方法如下.

(9)

式中：pij(t)為螞蟻在第t次聚類過程時從數據Xi與Xj的狀態轉移概率；τij(t)為螞蟻在第t次聚類過程時從數據Xi與Xj產生的信息素；q為直接轉移閾值.

步驟3確定聚類中心.根據路徑標識得到當前聚類中心，計算所有樣本到對應聚類中心的偏差量JE.

步驟4對路徑進行變異操作.對JE_min所對應的路徑進行變異，并計算該路徑下所有樣本對應聚類中心的偏差量JE_new.若JE_new小于JE_min，則將變異后的路徑作為下一次迭代中螞蟻選擇的路徑，反之則返回原路徑.

步驟5更新信息素.每次聚類完成后，將所有的螞蟻產生的路徑按偏差量升序排列，同時更新路徑上的信息素濃度；信息素按比例rho揮發，而偏差量較小的L個螞蟻對其所在路徑產生增量.信息素的更新公式為

(10)

步驟6重復步驟3～6，直到偏差量JE穩定或者達到最大迭代次數為止.

步驟7關鍵節點識別.比較各節點類的類別中心值，將類別中心值最大的節點類確定為關鍵節點.

3 實例分析

選取文獻[4]中成都地鐵網絡節點的數據進行仿真實驗，截至到2018年4月，成都地鐵共計6條線路，136個站點，整個城市軌道交通網絡呈“井+環”形，可以視為線路與站點構成的復雜網絡，其各節點編號及網絡拓撲圖見圖2.

圖2 成都地鐵線路圖(2018年4月)

3.1 網絡關鍵節點識別前的準備

1) 數據預處理 為了提升實驗結果的精度，需對各指標的數據進行標準化處理.采用歸一化方法對成都地鐵網絡中的136個站點和8個屬性數據進行歸一化處理，計算公式為

(i=1,2,…,136;j=1,2,…,8)

(11)

2) 最佳聚類簇數的確定 前文設計的蟻群聚類算法的聚類簇數K需預先設定，為了找出合適的K值，結合文獻[12]，選取樣本聚類誤差平方和(SSE)指標作為最優聚類K確定的依據.SSE計算公式為

(12)

式中：K為聚類的簇數；p為聚類的樣本；mk為第k類的聚類中心.SSE隨著K的變大而逐漸變小，當K越大，此時SSE則越小，說明樣本的聚類效果越好.當K比真實的聚類簇數小時，K的增大會大幅降低聚類的效果，所以SSE也會大幅下降，當K為真實的聚類簇數時，SSE下降的趨勢會大幅減小，然后隨著K值的不斷增大而漸漸趨于平緩，而使SSE最先趨于平緩的K值就是最佳的聚類簇數.因此，本文將預處理后的數據按照不同的K值進行聚類，得到SSE-K的趨勢圖，見圖3.

圖3 SSE-K趨勢圖

根據圖3可以確定出在K=3時，曲線最先趨于平緩.因此，成都市地鐵網絡節點聚類分析問題的最佳聚類簇數K為3.

3.2 聚類性能檢驗及結果

3.2.1聚類性能的檢驗

分別用傳統蟻群聚類算法與改進的蟻群聚類算法將預處理后的136個站點的8個屬性指標的數據進行聚類，算法的參數設置如下：螞蟻數R=1 000，最大迭代次數t_max=3 000，轉移閾值q=0.9，變異率pls=0.1，局部尋優路徑L=2，信息素系數c=0.01，信息素揮發率rho=0.1.利用Matlab編程得到兩種算法偏差量的收斂曲線，結果見圖4.

圖4 偏差量的收斂曲線

由圖4可知，傳統的蟻群聚類算法在迭代3 000次以后收斂，而改進的蟻群聚類算法在迭代了1 600次的時候曲線收斂，其收斂的速度明顯更快，而且兩種算法在CPU為inter i7-8700K、內存為32 G的計算機每聚類一次，運行時間均在0.3 s左右.因此，從效率而言，改進的蟻群聚類算法，相較于傳統的蟻群聚類，運行效率提升了近1倍.

3.2.2聚類的結果

通過改進的蟻群聚類算法得到成都市136個地鐵站點的最佳聚類結果見表1.由表1可知:聚類結果與實際情況十分吻合，如：類別1中的站點，如韋家碾、廣州路、雙流機場等71個站點在地鐵線路中多為規模較小的中間站；類別2中的站點，如文殊院、錦江賓館、惠王陵等39個站點在地鐵線路中多為規模較大的中間站；類別3中的站點，如火車北站、天府廣場、成都東站等26個站點在成都的地鐵網絡中多為規模大的換乘站，這些站點多分布于成都經濟較為發達、人口密度大的區域，在整個地鐵網絡的運營中承擔了重要角色.

表1 聚類結果

3.2.3網絡關鍵節點的識別

結合3.2.2中聚類結果可計算得類別1、類別2、類別3的聚類中心及類別中心值見表2.按照類別中心值的大小排序為：類別3>類別2>類別1，因此可以判斷出類別3的節點為地鐵網絡中的關鍵節點.該結論與文獻[4]中運用灰色關聯和TOPSIS加權評價識別出的關鍵節點一致，從而驗證了改進的蟻群聚類算法在地鐵網絡關鍵節點識別中的有效性和準確性，同時也減少了傳統評價模型在識別關鍵點過程中主觀因素的影響.

表2 聚類中心及類別中心值

3.3 隨機攻擊下的網絡的魯棒性分析

3.3.1網絡魯棒性的衡量指標

參考文獻[13]，選取網絡效率、最大連通子圖

兩個指標來描述節點損壞后網絡性能的變化.其中，網絡效率反映網絡的效用情況，計算公式為

(13)

式中：dij為節點i,j之間的最短路徑.

最大連通子圖的大小指網絡被攻擊后被分成若干網絡，其中包含節點最多的圖為最大連通子圖，它反映了地鐵網絡的抗毀性，計算公式為

J=N′/N

(14)

式中：N′和N分別為損壞前后的最大連通子圖的大小.

3.3.2隨機攻擊對網絡魯棒性的影響分析

根據前文中對節點進行的聚類處理，觀察不同類的節點在隨機攻擊下失效而影響地鐵網絡性能變化的程度，具體步驟如下.

步驟1分別將類別1、類別2、類別3中的節點作為首先攻擊的對象，對每一類的節點隨機攻擊，即隨機地不斷移除節點.

步驟2計算移除節點后的網絡性能指標.

步驟3繪圖分析，得到相關結論.

按照上述步驟，依次損壞網絡中的節點，破壞地鐵網絡的連通性.默認初始性能為100%，對三種節點類中的節點依次隨機攻擊，并分析網絡性能的下降態勢與被攻擊節點間的關系，見圖5.

圖5 隨機攻擊下網絡性能的變化

根據文獻[14]，網絡崩潰的臨界值為初始性能的50%，結合網絡崩潰的臨界閾值，對網絡的魯棒性進行分析.由圖5可知：類別1中的節點被率先隨機攻擊時，當有27個節點被攻擊時，網絡效率下降到70.9%，最大連通子圖下降到54%；類別2中的節點被率先隨機攻擊時，當同樣有27個節點被攻擊時，網絡效率下降到39%，最大連通子圖指標下降較慢，此時為73%；類別3中的節點被率先隨機攻擊之后網絡效率和最大連通子圖會急劇下降，當有9個節點被破壞時，網絡效率和最大連通圖分別下降到28%和45%，整個網絡近乎癱瘓.

通過圖5的比較分析，可知類別1中的節點被破壞對最大連通子圖的影響較大，對網絡效率的影響較小，類別2中的節點被破壞則對網絡效率的影響較大，對最大連通子圖的影響較小，而類別3中的節點被破壞時，對網絡效率和最大連通子圖的影響非常大，因此可以將類別3中的節點作為關鍵節點進行重點防護，來增強網絡的抗毀性.同時，類別3中的節點與文獻[4]中識別出的關鍵節點一致，說明了本文采用聚類算法對地鐵網絡的關鍵節點識別是有效的.

4 結 論

1) 由于聚類劃分的各節點類之間存在著差異，可通過比較各節點類聚類中心的類別中心值實現關鍵節點的識別.

2) 對蟻群聚類算法每次迭代所得的結果進行遺傳算法變異操作，能夠在一定程度上提高算法的聚類效果和求解效率.

3) 通過對成都地鐵網絡的魯棒性分析發現，關鍵節點類被攻擊之后，網絡性能指標急劇下降，整個地鐵網絡近乎癱瘓，驗證了聚類算法對關鍵節點識別的可行性和有效性.