黃大榮,沈利兵,趙 玲
(1. 重慶交通大學 信息科學與工程學院,重慶 400074;2.杜伊斯堡-埃森大學 自動控制與復雜系統(tǒng)研究所, 杜伊斯堡 47057,德國)
?
基于復雜網(wǎng)絡理論的城市路網(wǎng)脆弱性研究
黃大榮1,2,沈利兵1,趙 玲1
(1. 重慶交通大學 信息科學與工程學院,重慶 400074;2.杜伊斯堡-埃森大學 自動控制與復雜系統(tǒng)研究所, 杜伊斯堡 47057,德國)
首先,介紹了復雜網(wǎng)絡的靜態(tài)統(tǒng)計特性,并以新鄉(xiāng)市區(qū)路網(wǎng)為例計算了映射后包括度、介數(shù)、聚類系數(shù)等在內(nèi)的復雜網(wǎng)絡統(tǒng)計特征值。然后,針對城市路網(wǎng)的拓撲特性,以復雜網(wǎng)絡理論統(tǒng)計特性為基礎,建立了路網(wǎng)脆弱性研究模型。以新鄉(xiāng)市路網(wǎng)為例,研究了新鄉(xiāng)市路網(wǎng)在隨機性攻擊和最大度攻擊兩種攻擊策略下路網(wǎng)顯示出的脆弱性。最后,通過逐個攻擊網(wǎng)絡節(jié)點的方法定量計算出路網(wǎng)中各個節(jié)點對于攻擊表現(xiàn)出的脆弱性,通過該方法找到了路網(wǎng)中的關鍵路段,這對于后交通時代以維護為主體的路網(wǎng)保護具有重要的現(xiàn)實意義。
交通工程;城市路網(wǎng);關鍵性路段;復雜網(wǎng)絡;攻擊策略;脆弱性
城市道路交通網(wǎng)絡,不僅是城市的基礎設施,也是城市最重要的生命線之一[1]。而穩(wěn)健的城市交通道路網(wǎng)絡則是保障居民順暢出行和解決交通擁堵的有效手段。然而,當發(fā)生異常事件時,路網(wǎng)可能會受到某種程度的影響,直接造成整個城市路網(wǎng)的服務能力下降,從而對人們的生產(chǎn)生活造成不同程度的影響,因此,研究路網(wǎng)的脆弱性對于保障路網(wǎng)的健康暢通和緩解交通擁堵、提高路網(wǎng)的可靠性和健壯性都具有很強的現(xiàn)實意義。
近年來,城市路網(wǎng)脆弱性分析作為路網(wǎng)可靠性工程領域的一個研究熱點,得到了很快的發(fā)展,一些國內(nèi)外學者利用復雜網(wǎng)絡理論做了相關研究。胡一竑,等[2]在GIS技術和復雜網(wǎng)絡理論的基礎上,不但對以杭州為代表的4個城市的路網(wǎng)的基本拓撲性質進行了分析,而且分析了城市街道網(wǎng)絡的脆弱性,分析結果顯示整個網(wǎng)絡對選擇性攻擊表現(xiàn)出較高的脆弱性,但對隨機攻擊卻表現(xiàn)出較好的魯棒性;P. Luathe,等[3]在復雜網(wǎng)絡理論的基礎上提出了一種基于敏感性分析的脆弱性測度方法,該方法采用相對可訪問性指數(shù)作為評測網(wǎng)絡中線路重要性的指標,找出了路網(wǎng)中關鍵性的路段,并在蘇福爾斯市和曼谷大都會區(qū)的大型路網(wǎng)中得到了應用,驗證了該方法較傳統(tǒng)研究方法更為快速高效;L. Zhang,等[4]對交通網(wǎng)絡的脆弱性和易碎度進行了區(qū)分,認為路網(wǎng)的易碎度和網(wǎng)絡中的鏈接有很大關系,而路網(wǎng)脆弱性則取決于路網(wǎng)中關鍵性的節(jié)點和鏈接。以上研究盡管取得了一定的成果,但是更多地側重于對路網(wǎng)整體上拓撲特性的研究,缺乏在不同背景下路網(wǎng)以及各個路段脆弱性的定量化分析。
基于此,筆者在分析復雜網(wǎng)絡靜態(tài)統(tǒng)計特性的基礎上,以新鄉(xiāng)市區(qū)道路網(wǎng)絡為例,研究了其在隨機性攻擊和最大度攻擊兩種攻擊策略下路網(wǎng)所呈現(xiàn)的脆弱性,并通過逐個攻擊網(wǎng)絡中節(jié)點的方法定量計算出路網(wǎng)中各個節(jié)點對于攻擊表現(xiàn)出的脆弱性,通過該方法找出了路網(wǎng)中的關鍵路線,而這些路線正是路網(wǎng)管理者應重點關注與維護的對象。
目前,已有大量研究表明交通網(wǎng)絡屬于復雜網(wǎng)絡[5-6]。該網(wǎng)絡通常用無向圖G(V,E)表示,V代表節(jié)點集合,E代表邊的集合。用鄰接矩陣表示各節(jié)點之間相互連接的關系,若節(jié)點i和j相連接,則矩陣中的元素aij為1,否則aij為0。
一般而言,描述復雜網(wǎng)絡拓撲結構基本特征參量有3個,分別是網(wǎng)絡節(jié)點的度、節(jié)點的聚類系數(shù)以及網(wǎng)絡平均路徑長度[7]。以下對這上述基本參量逐一介紹。
1)節(jié)點Vi的度ki定義為與節(jié)點Vi有連接關系的路段的數(shù)目,其大小反映著該節(jié)點在網(wǎng)絡中的影響程度,是一個描述網(wǎng)絡局部特征的統(tǒng)計量,其度分布用分布函數(shù)p(k)來刻畫。而網(wǎng)絡的平均度則用網(wǎng)絡中全部節(jié)點度的平均值來刻畫。
(1)
式中:N為網(wǎng)絡節(jié)點數(shù)。
3)節(jié)點的路徑長度定義為從源節(jié)點到目的節(jié)點所要經(jīng)歷的路段數(shù)的最小值,也稱作節(jié)點間最短路徑長度。相應地,定義路網(wǎng)中所有OD對之間路徑長度的平均值為網(wǎng)絡的特征路徑長度。這里用特征路徑長度來表示網(wǎng)絡的尺寸,具體計算公式為:
(2)
式中:dij為節(jié)點i和j之間路徑長度。
城市路網(wǎng)是一個特殊的復雜網(wǎng)絡,用復雜網(wǎng)絡的思想研究路網(wǎng)特性,首先要將真實的城市路網(wǎng)抽象為拓撲模型[8-10]。而構建城市交通網(wǎng)絡拓撲模型較常用的方法有兩種,原始法和對偶法[2]。其中,原始法是指以城市路網(wǎng)的交叉口為節(jié)點,在交通路段上相鄰兩個節(jié)點之間建立領邊;對偶法則是指將道路映射為節(jié)點,交叉口映射為邊。由定義可知,原始法僅僅代表了純粹地理意義上的連接,而對偶法則高度抽象了道路間的相互聯(lián)結關系。因此,筆者選取對偶法構建路網(wǎng)的拓撲結構。
以新鄉(xiāng)市區(qū)道路網(wǎng)絡為例,作真實交通網(wǎng)絡的拓撲映射。首先在百度地圖上截取新鄉(xiāng)市區(qū)城市路網(wǎng)的結構(圖1),包含36條主干道,68條次干道和支路,限于篇幅限制,下述僅僅畫出了包含主干道的城市路網(wǎng)截圖。
圖1 新鄉(xiāng)市城市路網(wǎng)主干道結構
由于城市道路交通網(wǎng)絡系統(tǒng)極其復雜,要考慮所有對城市道路網(wǎng)絡有影響的因素太困難,同時也為了研究的方便,對上圖特做出如下假設:
1)只考慮城市路網(wǎng)中的主干道路,且不考慮上下線路區(qū)別,即將路網(wǎng)抽象為鄰接矩陣中無向圖,亦即無向網(wǎng)絡。
2)不考慮不同道路的長度和寬度,即不考慮網(wǎng)絡中權重問題,把主干道網(wǎng)絡抽象為無權網(wǎng)絡或者是把所有主干道抽象為權重1的網(wǎng)絡。
3)當?shù)缆返能嚨罃?shù)有兩條以上的時候,以車道數(shù)是否相同來區(qū)分不同道路,若車道數(shù)相同則為相同道路,否則為不同道路。
利用Ucient 6.0和Pajek軟件對上述包含次干道和支路在內(nèi)的新鄉(xiāng)市區(qū)真實路網(wǎng)結構圖做拓撲映射,如圖2。
圖2 新鄉(xiāng)市道路網(wǎng)絡拓撲映射
對圖2網(wǎng)絡做如下處理:首先,根據(jù)網(wǎng)絡拓撲利用對偶法寫出鄰接矩陣A。其次,編寫程序在MATLAB中對A進行計算。最后,得到新鄉(xiāng)市區(qū)路網(wǎng)復雜網(wǎng)絡各統(tǒng)計特性值,如表1。
表1 新鄉(xiāng)市城市路網(wǎng)復雜網(wǎng)絡統(tǒng)計特性
根據(jù)統(tǒng)計結果,可以看出,網(wǎng)絡的平均度只有5.5,少數(shù)節(jié)點的度大于10,說明新鄉(xiāng)市路網(wǎng)的道路網(wǎng)絡相互交叉的還不是很多;平均路徑長度為3.52,說明從一條路段到目的路段大概要經(jīng)過4條路段才能達到,這與新鄉(xiāng)市道路網(wǎng)絡建設的還不完善是相對應的。此外,對度做曲線擬合,發(fā)現(xiàn)其分布p(k)與冪律分布相似,又因為該網(wǎng)絡的特征路徑長度相對不大,但是網(wǎng)絡的聚類系數(shù)較大,所以該網(wǎng)絡小世界效應比較明顯,于是可以認定這樣的網(wǎng)絡為典型的無標度網(wǎng)絡。
網(wǎng)絡脆弱性指標主要用于測度網(wǎng)絡由于自身或者外部原因造成系統(tǒng)結構功能下降的程度,反映的是網(wǎng)絡功能水平的變化,因而測度指標應具有全局性[11]。同時,某個路段由于受到攻擊或自身原因而失效會使得該路段的流量流向其他路段,當流入該路段的流量超過了自身的容限,該路段就會變得擁堵,而該路段的擁堵又會造成流量流向其他路段,造成整個網(wǎng)絡的連鎖擁堵。因此,找出這些由于路段的失效造成其他路段嚴重擁堵的潛在路段,可以提前預防整個路網(wǎng)的連鎖擁堵。基于此,筆者用網(wǎng)絡效率的變化來衡量由于路網(wǎng)失效造成的路網(wǎng)流量和路網(wǎng)結構功能的變化。
網(wǎng)絡中任意兩個不同節(jié)點i和j之間的效率用εij表示:
(3)
式中:dij為節(jié)點i和j之間的距離。
當節(jié)點i和j不連接時,或i和j有任何一方受到攻擊,使原本連接的兩個節(jié)點變?yōu)榉沁B接狀態(tài),dij變?yōu)椤?,此時εij=0,因此,可以用εij=0來表示i和j之間的連接情況。整個網(wǎng)絡的效率E用網(wǎng)絡所有節(jié)點效率的平均值表示,即:
(4)
令ΔE=E攻擊前-E攻擊后,式中ΔE表示網(wǎng)絡性能的下降程度,網(wǎng)絡效率相對下降率為:
(5)
式中:e表示網(wǎng)絡效率的下降程度。
另外,在仿真過程中會發(fā)現(xiàn),有的網(wǎng)絡平均路徑指標開始隨著遭受攻擊節(jié)點的比例f的增加會逐漸增大,但是某個時候又會逐漸減少,因此,不宜直接選取網(wǎng)絡平均路徑作為路網(wǎng)脆弱性度量的指標,基于此,筆者選取網(wǎng)絡效率作為度量路網(wǎng)脆弱性的指標。
研究證明城市道路交通網(wǎng)絡是典型的無標度網(wǎng)絡[12-13]。一般地,該網(wǎng)絡主要面臨兩種異常事件的影響:選擇性攻擊與隨機性攻擊。隨機性攻擊通常是指隨機選擇網(wǎng)絡的一個節(jié)點進行攻擊,然后再攻擊其他節(jié)點中的一個,直至將所有節(jié)點全部攻擊完為止。選擇性攻擊是指有選擇地對網(wǎng)絡中的節(jié)點逐個進行攻擊[14-15]。因為節(jié)點在網(wǎng)絡中的影響程度可以用節(jié)點的度來表示,所以筆者選取節(jié)點的度的大小作為攻擊網(wǎng)絡節(jié)點的指標。具體策略是首先選取網(wǎng)絡中度最大的節(jié)點作為第一攻擊目標,攻擊完以后重新計算網(wǎng)絡各節(jié)點的度量等級,依舊對度量等級最高的節(jié)點進行攻擊,這樣重復下去,直到網(wǎng)絡中所有的節(jié)點全部被攻擊完為止。通過比較攻擊前后網(wǎng)絡效率E的改變量ΔE,分析網(wǎng)絡功能和結構的變化。
依照隨機性攻擊和選擇性攻擊的攻擊策略,利用MATLAB軟件做仿真結果,見圖3、圖4。
圖3 攻擊節(jié)點數(shù)目N和網(wǎng)絡效率
圖4 隨機性攻擊和選擇性攻擊下網(wǎng)絡效率相對變化率
從圖3可以看出,與城市路網(wǎng)在隨機性攻擊的情況相比,在選擇性攻擊同樣數(shù)量的道路情況下,其網(wǎng)絡效率下降的更快。當蓄意攻擊節(jié)點數(shù)量達到10個的時候,整個網(wǎng)絡的效率已經(jīng)下降到了最初的一半;當選擇性攻擊節(jié)點數(shù)量到達50個的時候,整個網(wǎng)絡幾乎全部癱瘓。而在隨機攻擊情況下,當攻擊節(jié)點數(shù)量達到30個左右的時候,網(wǎng)絡效率才下降到原來的一半;當攻擊節(jié)點數(shù)目達到100個的時候,網(wǎng)絡幾乎癱瘓。這說明新鄉(xiāng)市區(qū)道路網(wǎng)絡面對選擇性攻擊表現(xiàn)出更強的脆弱性。
從圖4可以看出,隨機攻擊下的網(wǎng)絡效率下降值相對選擇性攻擊下的網(wǎng)絡效率下降值變化的較平緩。在攻擊節(jié)點數(shù)目不至于使網(wǎng)絡癱瘓的情況下,選擇性攻擊網(wǎng)絡效率下降值更大,這是因為每次都是選擇網(wǎng)絡中度最大的節(jié)點進行攻擊的,這樣對網(wǎng)絡效率帶來的影響也更大,這與圖3中選擇性攻擊情況下的網(wǎng)絡效率斜率大于隨機性攻擊情況下的網(wǎng)絡效率的斜率相符合。
分析道路擁堵的原因可知,由于節(jié)點間存在著緊密的耦合關系,一個或某些關鍵性節(jié)點故障的存在,可能會引起網(wǎng)絡中其他節(jié)點發(fā)生故障,最終引起網(wǎng)絡中部分節(jié)點故障,更嚴重的后果是引起整個網(wǎng)絡的崩潰。因此,找出這些關鍵性的結點,并注意保護,這對于以信息維護為主體的后交通時代具有重要的現(xiàn)實意義。
對于節(jié)點重要度的評價,我們選擇的策略是首先攻擊網(wǎng)絡第1個節(jié)點,分析節(jié)點攻擊后網(wǎng)絡的效率E以及網(wǎng)絡效率變化量e,與網(wǎng)絡沒有受到攻擊時的E和e的變化情況,然后攻擊第2個節(jié)點,此時保持第1個節(jié)點健全(不受攻擊),分別分析第2個節(jié)點受到攻擊后網(wǎng)絡效率E、網(wǎng)絡效率變化量e和網(wǎng)絡健全時E,e的變化情況,依此類推,直至網(wǎng)絡中所有節(jié)點全部被攻擊完為止。結果如圖5、圖6。
圖5 攻擊節(jié)點及其對應的網(wǎng)絡效率的變化
圖6 攻擊節(jié)點及其對應網(wǎng)絡效率相對變化率
從圖5和圖6可以看出,攻擊不同的節(jié)點,網(wǎng)絡效率變化量和相對變化量大小是不同的。比如,攻擊節(jié)點2、節(jié)點4和節(jié)點1引起的網(wǎng)絡效率和網(wǎng)絡效率相對值下降都是很大的,這些節(jié)點一旦損壞對網(wǎng)絡造成的損害都是很大的,因此,這些節(jié)點是關鍵性節(jié)點。表2列出了所有節(jié)點中相對重要的前20個節(jié)點,并對這些節(jié)點進行了定量地數(shù)值計算。
表2 相對重要的前20個節(jié)點統(tǒng)計
表2列出了對網(wǎng)絡效率及相對效率改變量最大的20條路段,這些路段一旦發(fā)生故障將會對整個城市路網(wǎng)帶來很大影響,同時,由表2可以看出,某些度數(shù)和聚類系數(shù)大的路段引起的網(wǎng)絡效率E改變量,小于度數(shù)和聚類系數(shù)小的路段引起的網(wǎng)絡效率E的改變量,這說明路段重要性與該路段的度數(shù)和聚類系數(shù)沒有直接的關系。另外,從表上也可以看出,前20條重要路段中包含了15條主干道路,占到了關鍵性路段的75%,這說明對于城市路網(wǎng)來說,應注意保護關鍵性路段,尤其是主干道路,而不用把全部精力和資金放在所有路段上,這會更加有利于路網(wǎng)的暢通與高效運行。
城市路網(wǎng)脆弱性分析對于城市路網(wǎng)可靠性工程來說,是一項既重要又很急迫的工作,對于城市路網(wǎng)的管理維護起著越來越大的支撐作用。在復雜網(wǎng)絡理論的基礎上研究了城市路網(wǎng)的脆弱性,并以新鄉(xiāng)市路網(wǎng)為例,利用復雜網(wǎng)絡所特有的兩種攻擊策略對新鄉(xiāng)市道路網(wǎng)絡進行攻擊;結果表明,新鄉(xiāng)市道路網(wǎng)絡對選擇性攻擊表現(xiàn)出更強的脆弱性;最后通過逐個去除路段的方法確定了新鄉(xiāng)市區(qū)道路網(wǎng)絡中的關鍵性路段,這對交通管理部門進行路段保護維護具有重要的現(xiàn)實意義。
但是,這也僅僅是從理論角度推導出的結論,鑒于文中路段受到攻擊即被認為是該路段徹底發(fā)生了故障,而真實情況是路段受到攻擊時該條道路可能只是部分失效而不至于全部癱瘓,這正是筆者研究的不足之處,也是下一步要解決的重點問題,限于篇幅,在此不做研究,將另文給出。
[1] 涂穎菲,楊超,陳小鴻. 路網(wǎng)拓撲脆弱性及關鍵路段分析[J]. 同濟大學學報:自然科學版, 2010,38(3):364-367. Tu Yingfei, Yang Chao, Chen Xiaohong. Analysis of road network topology vulnerability and critical links [J]. Journal of Tongji University: Natural Science, 2010, 38(3): 364-367.
[2] 胡一竑,吳勤旻,朱道立.城市道路網(wǎng)絡的拓撲性質和脆弱性分析[J].復雜系統(tǒng)與復雜性科學, 2009,6(3):69-76. Hu Yihong, Wu Qinmin, Zhu Daoli. Topological Properties and vulnerability analysis of spatial urban street network [J]. Complex Systems and Complexity Science, 2009, 6(3): 69-76.
[3] Luathe P , Sumalee A, Ho H W, et al. Large-scale road network vulnerability analysis: a sensitivity analysis based approach [J]. Transportation, 2011, 38(5): 799-817.
[4] Zhang L, Levinson D. Investing for reliability and security in transportation network [J].Transportation Research Record: Journal of the Transportation Research Board, 2008, 2041: 1-10.
[5] Crucitti P, Latora V, Marchiori M, et al. Error and attack tolerance of complex network [J].Physica A, 2004, 340(1): 388-394.
[6] Sullivan J L, Novak D C, Aultman-Hall L,et al. Identifying critical road segments and measuring system-wide robustness in transportation networks with isolating links: a link-based capacity-reduction approach [J]. Transportation Research Part A: Policy and Practice, 2010,44(5): 323-336.
[7] 葉青.基于復雜網(wǎng)絡理論的軌道交通網(wǎng)絡脆弱性分析[J].中國安全科學學報,2012,22(2):122-126. Ye Qing. Vulnerability analysis of rail transit based on complex network theory [J]. China Safety Science Journal, 2012, 22(2): 122-126.
[8] 李永樹,劉剛,張帥毅.基于GIS的多粒度復雜網(wǎng)絡模型[J] .西南交通大學學報, 2012,47(3): 406-412. Li Yongshu, Liu Gang, Zhang Shuaiyi. Multi-granularity complex network model based on GIS [J]. Journal of Southwest Jiaotong University, 2012, 47(3) : 406-412.
[9] 鄧亞娟,楊云峰,馬榮國.基于復雜網(wǎng)絡理論的公路網(wǎng)結構特征[J].中國公路學報,2010,23(1):98-104. Deng Yajuan, Yang Yunfeng, Ma Rongguo. Highway network structure characteristics based on complex network theory [J]. China Journal of Highway and Transport, 2010, 23(1): 98-104.
[10] Velaga N R, Quddus M A, Bristow A L. Developing an enhanced weight-based topological map matching algorithm for intelligent transport systems [J]. Transportation Research Part C: Emerging Technologies, 2009, 17(6): 672-283.
[11] 楊露萍,錢大琳.道路交通網(wǎng)絡脆弱性研究[J].交通運輸系統(tǒng)工程與信息,2012,12(1):105-110. Yang Luping, Qian Dalin. Vulnerability analysis of road networks [J]. Journal of Transportation Systems Engineering and Information Technology, 2012,12(1): 105 -110.
[12] 張勇,楊曉光.城市路網(wǎng)的復雜網(wǎng)絡特性及可靠性仿真分析[J].系統(tǒng)仿真學報,2008,20(2):464-513. Zhang Yong, Yang Xiaoguang. Complex network property and reliability simulation analysis of urban street networks [J]. Journal of System Simulation, 2008, 20(2):464-513.
[13] 趙月,杜文,陳爽.復雜網(wǎng)絡理論在城市交通網(wǎng)絡分析中的應用[J].城市交通,2009,7(1):57-64. Zhao Yue, Du Wen, Cheng Shuang. Application of complex network theory to urban transportation network analysis [J]. Urban Transport of China, 2009, 7(1): 57-64.
[14] Barabasi A L, Albert R. Emergence of scaling in random networks [J]. Science,1999, 286(5439): 509-512.
[15] 汪玲,王劍.基于異質結構的復雜交通網(wǎng)絡擁塞分析[J].交通運輸系統(tǒng)工程與信息,2012,12(2):119-125. Wang Ling, Wang Jian. Congestion analysis of complex traffic network based on heterogeneity [J]. Journal of Transportation Systems Engineering and Information Technology, 2012, 12(2): 119-125.
Vulnerability Analysis of Urban Road Network Based on Complex Network Theory
Huang Darong1, 2, Shen Libing1, Zhao Ling1
(1. School of Information Science & Engineering, Chongqing Jiaotong University, Chongqing 400074, China;2. Research Institute of Automatic Control & Complex Systems, Duisburg-Essen University, Duisburg 47057, Germany)
Firstly, the statistic characteristics of complex network were introduced, and Xinxiang urban road network was taken as a case study, which calculated the statistical characteristics of complex network, including degree, betweenness, clustering coefficient and etc. Then, according to the topology characteristics of city road network, the model of road network vulnerability research was established by the statistic features of complex network theory. Taking the road network in Xinxiang city as an example, the vulnerability of the road network of Xinxiang city in two attack strategies which were randomly attacked and maximum degree attack were demonstrated. Finally, the vulnerability of every node in the network was calculated when they were attacked by assaulting the network rodes one by one, and the key sections of road network were found out by this algorithm. It is of important and practical significance for the network protection which takes the maintenance as the main body in post traffic times.
traffic engineering; city road network; key sections of road network; complex networks; attack strategy; vulnerability
10.3969/j.issn.1674-0696.2015.01.24
2013-10-13;
2014-03-10
國家自然科學基金項目(61004118,61304104);重慶市高等學校優(yōu)秀人才技術計劃項目(2014-18);重慶市教委自然科學基金項目(KJ120422)
黃大榮(1978—),男,湖北建始人,教授,博士,主要從事交通可靠性工程方面的研究。E-mail:drhuangjs@gmail.com。
U491
A
1674-0696(2015)01-110-06