地鐵網(wǎng)絡(luò)節(jié)點的聚類分析與關(guān)鍵節(jié)點識別

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

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

0 引 言

城市軌道交通網(wǎng)絡(luò)對城市公共交通系統(tǒng)具有重要支撐作用，網(wǎng)絡(luò)節(jié)點的暢通與否會影響城市軌道交通網(wǎng)絡(luò)的通行效率，嚴(yán)重時甚至?xí)?dǎo)致網(wǎng)絡(luò)的癱瘓.因此，對城市軌道交通網(wǎng)絡(luò)的關(guān)鍵節(jié)點進(jìn)行有效識別，找出重要的“核心節(jié)點”，并通過重點保護(hù)這些“核心節(jié)點”提高整個地鐵網(wǎng)絡(luò)的可靠性，有助于提升網(wǎng)絡(luò)的運營安全和效率.

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

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

1 地鐵網(wǎng)絡(luò)關(guān)鍵節(jié)點識別指標(biāo)

評估網(wǎng)絡(luò)節(jié)點重要度的指標(biāo)有很多，一般是從節(jié)點的度、介數(shù)、連通度等拓?fù)浣Y(jié)構(gòu)或脆弱性指標(biāo)進(jìn)行衡量[9]，但是地鐵網(wǎng)絡(luò)的節(jié)點重要度評估還需結(jié)合地鐵網(wǎng)絡(luò)的實際情況，不僅要反映節(jié)點在網(wǎng)絡(luò)中的重要性，還應(yīng)體現(xiàn)車站周邊的經(jīng)濟(jì)水平以及集散旅客、連接其他交通方式的能力.因此，根據(jù)已有的資料并結(jié)合文獻(xiàn)[4]和文獻(xiàn)[9]，選取識別地鐵網(wǎng)絡(luò)關(guān)鍵節(jié)點的指標(biāo)，見圖1.

圖1 關(guān)鍵節(jié)點的識別指標(biāo)

V1度，V2介數(shù)，V3補(bǔ)圖效率和V4連通度等指標(biāo)根據(jù)文獻(xiàn)[4]中的公式計算所得，V5客運進(jìn)站量用某一時間段內(nèi)的日平均進(jìn)站量計算所得，V7周邊資源根據(jù)地鐵站周邊的學(xué)校、醫(yī)院、商業(yè)街等資源評估所得，V8繁榮度則選擇車站所屬地區(qū)的人均GDP統(tǒng)計所得.

2 聚類識別關(guān)鍵節(jié)點類的原理及算法

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

2.1 聚類分析進(jìn)行關(guān)鍵節(jié)點類識別的原理

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

已知地鐵網(wǎng)絡(luò)節(jié)點集X有n個節(jié)點和K個分類，每個節(jié)點有m個屬性，由此得到節(jié)點集矩陣為

(1)

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

(2)

以每個節(jié)點與其聚類中心的距離最小為目標(biāo)函數(shù)，構(gòu)建網(wǎng)絡(luò)節(jié)點聚類的數(shù)學(xué)模型為

(3)

(4)

(5)

(6)

當(dāng)JE最小時，聚類效果達(dá)到最佳.此時，類別中心值最大的簇即為關(guān)鍵節(jié)點簇，數(shù)學(xué)表達(dá)式為

(7)

(8)

2.2 關(guān)鍵節(jié)點識別的算法

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

為了更好地運用蟻群聚類算法解決地鐵網(wǎng)絡(luò)關(guān)鍵節(jié)點的識別問題，需要對傳統(tǒng)的蟻群聚類算法進(jìn)行改進(jìn).本文結(jié)合遺傳算法中的變異思想，對蟻群聚類算法進(jìn)行改進(jìn)，改進(jìn)后的算法流程如下.

步驟1初始化算法的參數(shù).

步驟2確定初始解.根據(jù)信息矩陣中信息素的值和狀態(tài)轉(zhuǎn)移概率確定螞蟻行走路徑，并進(jìn)行標(biāo)識，方法如下.

(9)

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

步驟3確定聚類中心.根據(jù)路徑標(biāo)識得到當(dāng)前聚類中心，計算所有樣本到對應(yīng)聚類中心的偏差量JE.

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

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

(10)

步驟6重復(fù)步驟3～6，直到偏差量JE穩(wěn)定或者達(dá)到最大迭代次數(shù)為止.

步驟7關(guān)鍵節(jié)點識別.比較各節(jié)點類的類別中心值，將類別中心值最大的節(jié)點類確定為關(guān)鍵節(jié)點.

3 實例分析

選取文獻(xiàn)[4]中成都地鐵網(wǎng)絡(luò)節(jié)點的數(shù)據(jù)進(jìn)行仿真實驗，截至到2018年4月，成都地鐵共計6條線路，136個站點，整個城市軌道交通網(wǎng)絡(luò)呈“井+環(huán)”形，可以視為線路與站點構(gòu)成的復(fù)雜網(wǎng)絡(luò)，其各節(jié)點編號及網(wǎng)絡(luò)拓?fù)鋱D見圖2.

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

3.1 網(wǎng)絡(luò)關(guān)鍵節(jié)點識別前的準(zhǔn)備

1) 數(shù)據(jù)預(yù)處理 為了提升實驗結(jié)果的精度，需對各指標(biāo)的數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理.采用歸一化方法對成都地鐵網(wǎng)絡(luò)中的136個站點和8個屬性數(shù)據(jù)進(jìn)行歸一化處理，計算公式為

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

(11)

2) 最佳聚類簇數(shù)的確定 前文設(shè)計的蟻群聚類算法的聚類簇數(shù)K需預(yù)先設(shè)定，為了找出合適的K值，結(jié)合文獻(xiàn)[12]，選取樣本聚類誤差平方和(SSE)指標(biāo)作為最優(yōu)聚類K確定的依據(jù).SSE計算公式為

(12)

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

圖3 SSE-K趨勢圖

根據(jù)圖3可以確定出在K=3時，曲線最先趨于平緩.因此，成都市地鐵網(wǎng)絡(luò)節(jié)點聚類分析問題的最佳聚類簇數(shù)K為3.

3.2 聚類性能檢驗及結(jié)果

3.2.1聚類性能的檢驗

分別用傳統(tǒng)蟻群聚類算法與改進(jìn)的蟻群聚類算法將預(yù)處理后的136個站點的8個屬性指標(biāo)的數(shù)據(jù)進(jìn)行聚類，算法的參數(shù)設(shè)置如下：螞蟻數(shù)R=1 000，最大迭代次數(shù)t_max=3 000，轉(zhuǎn)移閾值q=0.9，變異率pls=0.1，局部尋優(yōu)路徑L=2，信息素系數(shù)c=0.01，信息素?fù)]發(fā)率rho=0.1.利用Matlab編程得到兩種算法偏差量的收斂曲線，結(jié)果見圖4.

圖4 偏差量的收斂曲線

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

3.2.2聚類的結(jié)果

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

表1 聚類結(jié)果

3.2.3網(wǎng)絡(luò)關(guān)鍵節(jié)點的識別

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

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

3.3 隨機(jī)攻擊下的網(wǎng)絡(luò)的魯棒性分析

3.3.1網(wǎng)絡(luò)魯棒性的衡量指標(biāo)

參考文獻(xiàn)[13]，選取網(wǎng)絡(luò)效率、最大連通子圖

兩個指標(biāo)來描述節(jié)點損壞后網(wǎng)絡(luò)性能的變化.其中，網(wǎng)絡(luò)效率反映網(wǎng)絡(luò)的效用情況，計算公式為

(13)

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

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

J=N′/N

(14)

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

3.3.2隨機(jī)攻擊對網(wǎng)絡(luò)魯棒性的影響分析

根據(jù)前文中對節(jié)點進(jìn)行的聚類處理，觀察不同類的節(jié)點在隨機(jī)攻擊下失效而影響地鐵網(wǎng)絡(luò)性能變化的程度，具體步驟如下.

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

步驟2計算移除節(jié)點后的網(wǎng)絡(luò)性能指標(biāo).

步驟3繪圖分析，得到相關(guān)結(jié)論.

按照上述步驟，依次損壞網(wǎng)絡(luò)中的節(jié)點，破壞地鐵網(wǎng)絡(luò)的連通性.默認(rèn)初始性能為100%，對三種節(jié)點類中的節(jié)點依次隨機(jī)攻擊，并分析網(wǎng)絡(luò)性能的下降態(tài)勢與被攻擊節(jié)點間的關(guān)系，見圖5.

圖5 隨機(jī)攻擊下網(wǎng)絡(luò)性能的變化

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

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

4 結(jié) 論

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

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

3) 通過對成都地鐵網(wǎng)絡(luò)的魯棒性分析發(fā)現(xiàn)，關(guān)鍵節(jié)點類被攻擊之后，網(wǎng)絡(luò)性能指標(biāo)急劇下降，整個地鐵網(wǎng)絡(luò)近乎癱瘓，驗證了聚類算法對關(guān)鍵節(jié)點識別的可行性和有效性.