蔡鑒明,鄧薇
?
長沙地鐵網絡復雜特性與級聯失效魯棒性分析
蔡鑒明,鄧薇
(中南大學 交通運輸工程學院 智慧交通湖南省重點實驗室,湖南 長沙 410075)
基于復雜網絡理論,采用Space-L方法對長沙地鐵網絡的拓撲結構特性進行研究。通過4項魯棒性評價指標,定量分析有無級聯失效情況下的長沙地鐵網絡魯棒性。研究結果表明:長沙地鐵網絡既不是無標度網絡,也不是小世界網絡,而是具備部分隨機網絡特性的混合拓撲網絡;無論有無級聯失效,蓄意攻擊下網絡皆比隨機攻擊更加脆弱;級聯失效下考慮客流量重新分配的地鐵網絡在面對故障時更具脆弱性;與傳統的節點重要程度排序相比,加入客流量會使排序發生較大的變化。
長沙地鐵網絡;復雜網絡;級聯失效;魯棒性
完善公共交通建設、減少私家車的出行是防治城市交通堵塞等問題的重要舉措。地鐵由于快捷、安全、舒適和運量大等特點而備受青睞,我國當前已有30多個城市已建或正在規劃建設地鐵系統,因此對其進行系統的分析,保障其合理、安全的運行具有十分重要的意義。國內外學者從復雜網絡的角度對地鐵開展了一定的研究。針對地鐵拓撲結構,曲迎春等[1]研究了地鐵網絡的脆弱性;DENG等[2]實證分析了南京市的地鐵,得出該網絡具有小世界和無標度特性;高鵬等[3]采用加權的方式分析了地鐵網絡的魯棒性;Latora等[4]分析了波士頓地鐵的網絡特性;SUN等[5]以線路為整體研究城市地鐵的脆弱性;Angeloudisa等[6]驗證了地鐵網絡的抗毀性。近年來,級聯失效的概念開始被應用到地鐵網絡中來,沈犁等[7]通過建立地鐵與公交復合網絡模型,分析了復合網絡抗毀性并對其進行了級聯失效仿真研究;陳峰等[8]分別從無權和有權2方面分析了地鐵網絡的復雜參數以及相繼故障下北京地鐵網絡的可靠性。目前,地鐵研究對象主要集中在如北京、上海等地鐵網絡較為發達的大都市,且關于地鐵網絡的級聯失效魯棒性研究較少;長沙地鐵網正處在建設與發展中,很具有代表性,文獻檢索尚未發現有學者對長沙市地鐵網絡的復雜特性、級聯失效等方面的研究成果。因此,論文針對長沙規劃年的地鐵網絡,實證分析其復雜網絡結構特性,并加入客流量這一指標,研究級聯失效下地鐵網絡的魯棒性。
長沙地鐵線路(含磁懸浮線)近期規劃8條,遠期規劃一共13條線,目前已開通1號線、2號線和磁懸浮線。論文中研究的長沙市地鐵網絡包括地鐵1至9號線和磁懸浮線,構建的地鐵網絡含有201個站點,根據201個站點之間的連接情況可以建立一個201×201的鄰接矩陣,相鄰的2個站點之間矩陣數值為1,反之為0。由于Space-L法是基于鄰接矩陣建立復雜網絡拓撲結構圖,2個站點相鄰則有邊相連,較為真實的反映了乘客出行路徑長度,因此采取Space-L方式來構建長沙地鐵網絡,如圖1所示。
長沙地鐵拓撲結構構建說明:
1) 網絡包含遠期規劃中已大致確定站點的線路,這與未來的實際站點可能存在微小的差別,但大致的走向不變,依舊有較高的參考價值。
2) 不考慮上下行差異、列車的發車頻次、列車型號、客流量以及一些其他的客觀因素。
3) 除桐梓坡路和六溝垅表示同一個站點以及湘府路和板塘沖表示同一站點外,其余皆為不同名則不同站。
4) 2號線和4號線都經過光達至火車南站這一區間,在計算度時對這2個站點都增加了一個度值。


式中:e表示地鐵網絡的實際邊數;n表示網絡節點數。
運用excel建立長沙市地鐵網絡的鄰接矩陣,將其導入到matlab中編程計算各個拓撲性指標,計算結果如表1所示。該網絡一共有201個節點,231條邊,網絡的平均度為2.308 5,網絡有16個度值為1的節點,這一部分節點為首末站;146個節點的度為2,為僅有一條線路經過的中間站;既是中間站又是端點站的節點有2個,度值分別為3和5;度值為4的節點有37個,為有2條線路經過的換乘站。平均最短路徑長度為12.687 0,這說明2站點之間平均經過12.687 0個站能到達,平均介數、全局效率和連接度都偏低。

表1 長沙市地鐵網絡基本指標
圖2依次為節點度分布和累計度分度,70%以上的節點度為2,最大度值僅為5,線網較為稀疏。

圖2 節點度分布和累計度分布
長沙地鐵網絡的網絡直徑為37,圖3是最短路徑概率分布及累計概率分布圖,任意兩個站點間路徑長度不超過20的占整體84.3%,63.5%的節點間距離不超過15;居民出行大部分路徑長度較短,說明線路站點數的設置及換乘站的位置設置較為 合理。

(a) 最短路徑概率分布圖;(b) 最短路徑累計分布圖
圖4對長沙地鐵網絡累計度分布進行了3種不同的擬合,擬合函數如下。
其中高斯分布擬合度最高,網絡不具備無標度網絡特性,主要原因是受長沙市地形、經濟、客流分布和城市用地規劃等各個方面的影響,地鐵網絡不能擇優增長,另外換乘站是地下分層結構,設計與施工難度高、風險大,這就導致長沙地鐵網絡的度分布范圍較小,新站點的確定及其與既有站點之間的連接都具有一定的隨機性。

圖4 長沙地鐵網絡累計度分布各類擬合曲線
表2為長沙地鐵網絡的平均路徑長度和聚類系數,以及與其規模一致的隨機網絡的平均路徑長度和聚類系數。根據小世界網絡需要滿足的特性要求[10],即網絡平均路徑長度接近于隨機網絡而聚類系數接近于規則網絡,通過比較長沙地鐵網絡與對應規模的隨機網絡的復雜性指標,可知長沙地鐵網絡的聚類系數小于隨機網絡,且平均路徑長度大于隨機網絡,因此長沙地鐵網絡不具備小世界網絡的特征。主要原因是為了滿足居民的出行,地鐵線路在規劃區域內盡量均勻的覆蓋,大部分站點僅有一條線路經過,少有站點聚集的現象。

表2 地鐵網絡和同規模隨機網絡的拓撲特征參數
根據以上分析可知,長沙地鐵網絡既不是小世界網絡也不是無標度網絡,這一結論與張鐵巖等[11]對北上廣的研究分析結果一致,而杜斐等[12]的研究表明2015年上海地鐵網絡已具備小世界網絡的特征,這說明隨著網絡的規模不斷發展,站點之間的聯系更加緊密,地鐵網絡逐步具備小世界網絡的特性。
表3為長沙地鐵網絡聚類系數非0的8個站點的數值,其余站點為0,站點間的聚類程度極低。聚類系數是一個局部參數,當聚類系數偏小時,則網絡的容錯性更差,可替代的節點和線路越少,一旦有節點或區間失效將給網絡整體帶來極大的影響,甚至會導致網絡崩潰。

表3 節點的聚類系數
長沙地鐵網絡度與介數的關系如圖5。
從圖5(a)可以看出,度越大,則介數的起始值越大,介數在一個更大的范圍內波動;度和相同度的平均介數用matlab編程擬合后發現其呈現正相關性,斜率為0.027 73。
長沙地鐵網絡度與緊密度的關系如圖6。
運用matlab擬合的度與相同度的平均緊密度為直線,斜率為0.000 026 9,度與緊密度正相關。網絡節點的緊密度即為節點到其它節點的路徑長度和的倒數,緊密度越大說明節點到其他節點出行的距離越短、出行更加便利。

(a) 介數;(b) 度

(a) 緊密度;(b) 度
由以上分析可知,長沙地鐵網絡的度、介數和緊密度三者正向相關。度是一個微觀上的特征參量,介數和緊密度是宏觀上的特征參量,這3個參量的正相關性說明長沙地鐵網絡節點的重要程度在微觀和宏觀上呈現出相似性。
表4為長沙地鐵網絡2015~2024年的各項特征參數值。平均度在2左右,整體呈現遞增的趨勢,2024年減小是因為增加的4號線東延線與其它線路無任何相交。網絡直徑、平均路徑長度和連接度逐年增大,說明網絡規模在不斷擴大,覆蓋的區域越來越廣,網絡節點之間的聯系進一步加強。2015~ 2018年由于地鐵線路太少,平均聚類系數為0,之后隨著線路的增加節點開始出現聚集的現象。地鐵線路的不斷增加,雖然部分站點間的聯系增強,但大部分新增節點與原有節點距離較大,因此,網絡的平均介數和全局效率逐漸減少。

表4 長沙地鐵網絡不同時期的特征參數值
站點或區間發生故障時,由正常態轉為失效態,此時對于網絡的影響并非只是簡單的移除,它的失效會影響到周圍的區間和節點甚至整個網絡,當某些節點或區間超負荷時會接連失效,導致地鐵網絡部分或全面癱瘓,這就是級聯失效現象。要分析地鐵網絡的級聯失效現象就需要建立合理的級聯失效模型,模型主要包含3個部分。
許多學者利用介數或度來計算節點的初始負載,雖然能在一定程度上反映節點負載的分布情況,但與現實情況仍有一定的差異。論文模型采用地鐵車站近期規劃預測的客流量(上下車總人數)作為節點的初始負載Q,更能反映長沙地鐵網絡的實際情況。
地鐵車站受到技術因素、當地經濟以及周邊規劃等的影響,形成的規模各有不同,這就使得每個車站的容量有所差異。依據ML模型[13]可知,節點的最大容量C與它的初始負載Q正向相關。模型的初始負載為地鐵建設初期預測的客流量,這是車站建設規模的一個重要衡量標準,因此車站的最大容量必然與初始負載成正比的關系。

C為節點的最大容量;為容量限制系數,它代表了節點在處理超過初始負載時的能力,取值0.5;Q為節點的初始負載。
假設由于故障的突發性,消息未能及時發布,乘客無法規劃其他的出行方式,選擇地鐵出行。具體分配模型如下:


式中:為失效節點的集合;為失效節點;Q()為節點在時間步長為時所負載的客流量;ΔQ為節點的負載增量。
關于分配模型中計算節點負載增量的方式:一種是基于節點最大容量,如式(5)所示;另一種是基于節點自身拓撲特性,如式(6)所示。本文綜合運用這2種方法,更加全面地考慮多項參數對網絡的 影響。


地鐵網絡的魯棒性是指節點或邊在遭遇突發故障或故意襲擊后仍能保持網絡正常運行的能力,網絡級聯失效魯棒性是指節點或邊遭受攻擊后點或邊發生接連失效時仍能保持網絡正常運作的能力。圖7為具體研究的長沙地鐵網絡,表5為其網絡特征參數值。有關說明如下。
1) 受現有數據的限制,僅分析長沙地鐵1~5號線;
2) 僅探討長沙地鐵網絡站點遭受攻擊時對網絡的影響;
3) 級聯失效模型研究網絡客流量的重新分配問題,不考慮實際運營中的其他因素,分配的負載超過最大容量則視為節點失效。

圖7 長沙地鐵 1至5號線拓撲結構圖

表5 長沙地鐵1至5號線的網絡特征參數
復雜網絡魯棒性的研究主要是抗毀性和生存性,這2類性質的不同之處在于攻擊方式的差異,抗毀性是指發生蓄意攻擊(人為縱火、恐怖襲擊、戰爭等)時網絡正常運行的能力,生存性是指發生隨機故障(信號干擾、機械故障、自然災害等)時網絡正常運行的能力。
研究長沙地鐵網絡的生存性采用對網絡隨機選取節點的方式,抗毀性研究通過人為的選取重要度排序在前的節點,每次刪除一個節點直至刪除50個節點為止,占整體網絡40.65%,但在對考慮級聯失效下的網絡進行攻擊時,攻擊的節點數量為導致網絡崩潰的節點數。節點的重要程度排序[14]主要有3種以下方法:節點度、節點介數和節點緊密度,其中度排序是應用最廣泛也是最簡單的,但相同度的節點無法辨別在網絡中的重要程度,且容易忽略一些度小但起到關鍵紐帶作用的節點。介數排序準確性高,但計算難度有所增加。地鐵是為人的出行服務的,乘客的數量在地鐵的運營建設中起到了決定性的作用,因此,車站近期規劃中客流量的大小在很大程度上說明了站點的重要程度,加入客流量這一指標會使得節點在重要程度排序時更具現實意義。節點重點程度排序計算公式如下:

其中:I為節點重要程度的度量值;Q為節點的客流量;BC為節點的介數;K為節點的度。
地鐵網絡的魯棒性尚未有統一的度量標準,論文采用全局效率、最大連通子圖相對大小、失效節點個數和網絡連接度來分析長沙地鐵網絡的魯 棒性。
1) 網絡的全局效率E,它能衡量網絡的整體有效性,計算公式如下:

其中:為節點個數;d為節點之間的路徑長度。
2) 網絡節點遭受攻擊后,某些節點被摧毀導致初始網絡被拆分成多個部分,最大連通子圖與原地鐵網絡圖的相對大小計算公式如下:

其中:為節點個數;0為網絡被攻擊后最大連通子圖的節點數量。
3) 失效節點個數SF,網絡中遭受攻擊的節點會使得剩余節點的負載增大,引發節點的接連失效,因此失效節點個數是一項重要的評價指標。
4) 網絡連接度,用連接度代替了聚類系 數[15],連接度越大網絡發展程度越高,代表了網絡的全局發展水平。
按照式(7)的計算方法,選取重要程度排序前21的節點分別對網絡進行蓄意攻擊,以此來研究單個節點失效對網絡產生的影響,表6為各個參數具體的計算結果。
從表6可知,某一節點失效引發的失效節點個數越多,則網絡連接度越小,但二者與網絡全局效率變化無明顯的關聯。網絡效率變化率前八的站點中望月湖和六溝垅站盡管只是中間站,但這2個站點失效會使得網絡效率的變化率高于許多一般的換乘站,因為這2個節點是眾多節點間連接的唯一紐帶,即橋梁站,一旦失效致使部分節點間無連接,網絡的全局效率大幅降低。其余6個站點既是換乘站也是橋梁站,在實際運營中這幾個站點的客流量較大,在網絡拓撲結構中是關鍵節點,一旦遭遇破壞,同樣將使某些節點斷開連接,導致網絡效率下降顯著。部分重要程度節點排序靠前,但網絡效率變化較小的是因為這些節點周圍的線路較為密集,失效后不會導致節點間無法通行,可替代路徑起到了網絡疏通的作用,但考慮到站點的客流量大,失效后會使得其他站點承受更多的負載,容易引起網絡崩潰,因此這些站點同樣十分重要。中信廣場作為換乘站且它的失效引發周圍的2個節點同時失效,但該站靠近線路的端點處與網絡節點的聯系少,引起的網絡效率變化相對較低。

表6 長沙地鐵網絡節點單個失效時網絡的特征參數值
由上述分析可知,長沙地鐵網絡在運營和建設的過程中要重視重要度排序靠前的站點(溁灣鎮站、五一廣場站等)以及目前客流量較少但充當橋梁作用的站點(六溝垅站、望月湖站等)的安保措施和運行維護工作,這些節點的失效會引起整個網絡的連通性和網絡效率大幅下降,為保證網絡的正常運營要避免此類節點失效。
此外,為研究長沙地鐵網絡在有無級聯失效下網絡魯棒性的區別,分別對網絡進行單個節點依次的隨機和蓄意襲擊,由于非級聯失效下即為單一的拓撲結構,不考慮流量對其影響,僅采用介數對節點進行排序。
圖8為不同狀態不同攻擊方式下的網絡效率變化趨勢圖,從中可以明顯地看出4種不同情況對網絡效率的影響程度。在非級聯失效下對長沙地鐵網絡進行隨機攻擊,網絡全局效率下降較為緩慢,這說明小范圍內的隨機故障對網絡的整體運行影響較小,但隨著攻擊范圍的不斷擴大會對網絡產生較大的影響,失效節點數達到28個時,僅為初始效率的16.98%,使網絡的功能大幅降低。當網絡節點遭受蓄意的破壞,網絡效率快速下降,失效節點數達到9個時,此時攻擊節點的數量不足網絡整體的5%,網絡效率已下降到了0.027 1,這說明這部分節點對于整個網絡都極為重要,發揮著連通網絡的關鍵作用,一旦失效將給網絡帶來重創。當失效節點達到27個后,隨機攻擊造成的網絡效率下降更快,這可以解釋為隨機攻擊時一些介數較高的節點在之后才失效,而采用蓄意攻時越靠后的節點介數越小,對網絡產生的影響就越小。在級聯失效下當蓄意攻擊節點數達到3個,網絡效率驟降為0,對網絡是毀滅性的災難;隨機攻擊網絡效率下降較慢,但當失效節點達到24個時,網絡效率也突變為0,地鐵網絡將無法運作。
長沙地鐵網絡不同攻擊方式下的最大連通子圖相對大小的變化曲線如圖9所示,在級聯失效狀態下,蓄意攻擊節點數達到3個時,網絡崩潰,最大連通子圖瞬間變為0;隨機攻擊時變化較為緩慢,但當失效節點達到一定數量后,一旦遇到關鍵節點失效將導致網絡剩余節點全部失效變成孤立的點,如圖隨機攻擊的第26個節點為16號節點(溁灣鎮站),該節點在重要度排序中排第3,此時最大連通子圖突變為0。對于非級聯失效下的蓄意攻擊在前6個點失效時最大連通子圖相對大小快速減小,之后變化微小;而隨機攻擊整體平穩下降。

圖8 不同攻擊方式下的網絡效率值

圖9 不同攻擊方式下的最大連通子圖相對大小
通過對圖8和圖9的分析可知,長沙地鐵網絡在考慮級聯失效的情況下遠比僅考慮網絡拓撲結構要脆弱。但無論是否為級聯失效,相應的蓄意攻擊和隨機攻擊對網絡的影響在前部分下降趨勢較為相似,不同的是級聯失效下,節點的失效經過一定的數量累積之后會發生突發性的全網崩潰的現象,而非級聯狀態下越到后面變化越平穩。兩者對抗隨機故障時具有較強的魯棒性,蓄意攻擊時表現出很強的脆弱性。
1) 通過對長沙地鐵網絡拓撲特性的研究發現,該網絡不具備小世界網絡的特性,同時度分布也不服從冪律分布,而是帶有隨機網絡特征的混合型復雜網絡,但仍具有一定的無標度網絡特征,即面對隨機故障具有較強的魯棒性,蓄意攻擊時體現出脆弱性。
2) 實證分析長沙地鐵的復雜網絡特性和不同時期的網絡特征參數值,研究有無級聯失效下網絡的魯棒性,比較兩者之間的差別,級聯失效模型參考了長沙地鐵近期規劃的客流量,考慮了節點失效對整個網絡的影響,相對于單一的拓撲結構而言更加貼近于地鐵網絡的實際情況。
3) 研究成果可對長沙及其類似的城市地鐵的運營、安全維護、后期規劃建設等提供參考依據。但實際的地鐵運營還包括列車發車頻次、乘客換乘和故障信息的發布時間等,且近期規劃的客流量與地鐵的實時客流量存在一定的差別,今后需要結合這一系列的情況做更加詳細、深入的研究。
[1] 曲迎春, 徐仲之, 龔航, 等. 城市軌道交通網絡脆弱性分析[J]. 鐵道科學與工程學報, 2016, 13(11): 2277? 2283. QU Yingchun, XUN Zhongzhi, GONG Hang, et al. Vulnerability analysis of urban rail transit networks[J]. Journal of Railway Science and Engineering, 2016, 13(11): 2277?2283.
[2] DENG Yongliang, LI Qiming, LU Ying, et al. Topology vulnerability analysis and measure of urban metro net-work: The case of Nanjing [J]. Journal of Networks, 2013, 8(6): 1350?1356.
[3] 高鵬, 胡劍波, 魏高樂. 變權重的城市軌道交通復雜網絡魯棒性分析[J]. 計算機仿真, 2013, 30(9): 153?156. GAO Peng, HU Jianbo, WEI Gaole. Robustness analysis of urban transit network based on complex network with varied weight[J]. Computer Simulation, 2013, 30(9): 153?156.
[4] Latora V, Marchiori M. Is the Boston subway a small-world network[J]. Physical A: Statistical Mechanics and its Applications, 2002,314(1/2/3/4): 109?113.
[5] SUN D, GUAN S. Measuring vulnerability of urban metro network from line operation perspective[J]. Transportation Research Part A, 2016(94): 348?359.
[6] Angeloudis P, Fisk D. Large subway systems as complex networks[J]. Physic A, 2006, 367(4): 553?558.
[7] 沈犁, 張殿業, 向陽, 等. 城市地鐵-公交復合網絡抗毀性與級聯失效傳播性仿真研究[J]. 西南交通大學學報, 2017, 52(6): 1?9. SHEN Li, ZHANG Dianye, XIANG Yang, et al. Simulation study on survivability and cascading failure propagation of urban subway transit complex network[J]. Journal of Southwest Jiaotong University, 2017, 52(6): 1?9.
[8] 陳峰, 胡映月, 李小紅, 等. 城市軌道交通有權網絡相繼故障可靠性研究[J]. 交通運輸系統工程與信息, 2016, 16(2): 139?145. CHEN Feng, HU Yingyue, LI Xiaohong, et al. Cascading failures in weighted network of urban rail transit[J]. Journal of Transportation Systems Engineering and Information Technology, 2016, 16(2): 139?145.
[9] Derrible S, Kennedy C. The complexity and robustness of metro networks[J]. Physica A, 2010(389): 3678–3691.
[10] Duncan J W, Steven H S. Collective dynamic of small world networks[J]. Nature, 1998, 393(6684): 440?442.
[11] 張鐵巖, 宋瑞, 鄭鋰, 等. 基于復雜網絡理論的國內地鐵網絡特性分析[J]. 交通信息與安全, 2012, 30(5): 50?54. ZHANG Tieyan, SONG Rui, ZHENG Li, et al. Analysis of domestic subway network characteristics based on complex network theory[J]. Journal of Transport Information and Safety, 2012, 30(5): 0?54.
[12] 杜斐, 黃宏偉, 張東明, 等. 上海軌道交通網絡的復雜網絡特性及魯棒性研究[J]. 武漢大學學報(工學版), 2016, 49(50): 701?707. DU Fei, HUANG Hongwei, ZHANG Dongming, et al. Analysis of characteristics of complex network and robustness in Shanghai metro network[J]. Engineering Journal of Wuhan University, 2016, 49(5): 701?707.
[13] Motter A E, Lai Y C. Cascade-based attacks on complex networks[J]. Physical Review E, 2002, 66(6): 065102.
[14] GAO C, WEI D J, HU Y, et al. A modified evidential methodology of identifying influential nodes in weighted networks[J]. Physica A, 2013, 392(21): 5490?5500.
[15] 張晉, 梁青槐, 賀曉彤. 北京市地鐵網絡拓撲結構復雜性研究[J]. 北京交通大學學報, 2013, 37(6): 78?84. ZHANG Jin, LIANG Qinghuai, HE Xiaotong. Study on the complexity of Beijing metro network[J]. Journal of Beijing Jiaotong University, 2013, 37(6): 78?84.
Complex characteristics of Changsha metro network and robustness analysis of cascading failures
CAI Jianming, DENG Wei
(Smart Transport key Laboratory of Hunan Province, School of Traffic and Transportation Engineering,Central South University, Changsha 410075, China)
Based on the complex network theory, the topological structure of Changsha metro network was studied by using Space-L method. The robustness of Changsha metro network under the condition of cascading failure was quantitatively analyzed through 4 robustness evaluation indexes. It is concluded that the Changsha metro network is neither a small world network nor a scale-free network, but a hybrid topology network with certain random network characteristics. Whether there is a cascading failure, the network is deliberately more vulnerable than random attacks. The metro network considering redistribution of passenger flow under cascading failure is more vulnerable. Compared with traditional ranking of node importance, adding traffic will cause great changes in sorting.
Changsha metro network; complex network; cascading failure; robustness
U231+.2
A
1672 ? 7029(2019)06? 1587 ? 10
10.19713/j.cnki.43?1423/u.2019.06.031
2018?07?31
國家重點研發計劃資助項目(2018YFB1201601)
蔡鑒明(1964?),男,湖南長沙人,高級實驗師,博士,從事交通運輸規劃與管理研究;E?mail:jmcai@csu.edu.cn
(編輯 蔣學東)