基于邊攻擊策略的城市交通網(wǎng)絡(luò)魯棒性分析

方晟浩，肖 堯，李 平，郭洪鵬

（1.蘭州交通大學(xué)交通運(yùn)輸學(xué)院，蘭州 730070；2.中鐵第一勘察設(shè)計(jì)院集團(tuán)有限公司線路運(yùn)輸院，西安 710043；3.中國(guó)鐵路設(shè)計(jì)集團(tuán)有限公司線路站場(chǎng)樞紐設(shè)計(jì)研究院，天津 300308）

復(fù)雜網(wǎng)絡(luò)魯棒性分析是研究在蓄意或隨機(jī)攻擊下網(wǎng)絡(luò)的抗毀能力與穩(wěn)定性.目前對(duì)魯棒性的研究主要集中于靜態(tài)魯棒性分析與動(dòng)態(tài)魯棒性分析兩個(gè)方面.通過(guò)移除一部分邊或節(jié)點(diǎn)分析復(fù)雜網(wǎng)絡(luò)連通性的方法被稱(chēng)為靜態(tài)魯棒性分析；通過(guò)分析復(fù)雜網(wǎng)絡(luò)中雪崩效應(yīng)與級(jí)聯(lián)效應(yīng)的方法被稱(chēng)為動(dòng)態(tài)魯棒性分析.對(duì)復(fù)雜網(wǎng)絡(luò)的攻擊方式一般分為蓄意攻擊與隨機(jī)攻擊兩種，蓄意攻擊通過(guò)刪除復(fù)雜網(wǎng)絡(luò)中重要的節(jié)點(diǎn)與邊達(dá)到攻擊目的，隨機(jī)攻擊則是隨機(jī)挑選節(jié)點(diǎn)與邊刪除以達(dá)到攻擊目的.

國(guó)內(nèi)外學(xué)者對(duì)城市交通網(wǎng)絡(luò)的魯棒性做了深入的研究，諸多學(xué)者提出若干種針對(duì)城市交通網(wǎng)絡(luò)魯棒性指標(biāo)的衡量標(biāo)準(zhǔn)，其中，沿用復(fù)雜網(wǎng)絡(luò)領(lǐng)域的分析方法較為主流.強(qiáng)添綱等［1］采用原始映射法構(gòu)建了包括小汽車(chē)網(wǎng)絡(luò)、地面公交網(wǎng)絡(luò)和軌道交通網(wǎng)絡(luò)三者疊加而成的城市多模式交通網(wǎng)絡(luò)模型.Duan等［2］以三種不同粒度的路網(wǎng)模型：基于分段模型、基于stroke模型和基于社區(qū)模型，分別研究了點(diǎn)狀、線性和帶狀交通中斷下路網(wǎng)的響應(yīng).趙玲等［3］采用基于角度綜合的對(duì)偶方法進(jìn)行路網(wǎng)建模處理路網(wǎng)空間數(shù)據(jù)和計(jì)算統(tǒng)計(jì)指標(biāo)，分析其小世界特性、無(wú)標(biāo)度特性以及同配異配性、網(wǎng)絡(luò)彈性等結(jié)構(gòu)特性.崔文巖等［4］以負(fù)載重分配動(dòng)力學(xué)過(guò)程有重要影響的節(jié)點(diǎn)度和介數(shù)兩種指標(biāo)作為構(gòu)建依據(jù)，提出一種節(jié)點(diǎn)度和介數(shù)相關(guān)邊權(quán)的網(wǎng)絡(luò)級(jí)聯(lián)抗毀性模型.馮霞等［5］將中國(guó)航空網(wǎng)絡(luò)建模成無(wú)向加權(quán)復(fù)雜網(wǎng)絡(luò)，在分析航空網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特性的基礎(chǔ)上，研究分析了航空網(wǎng)絡(luò)的魯棒性.王爾申等［6］提出了基于邊攻擊成本的復(fù)雜網(wǎng)絡(luò)魯棒性研究方法，通過(guò)將邊的攻擊成本因素考慮在內(nèi)，結(jié)合兩種人工合成網(wǎng)絡(luò)和四種真實(shí)網(wǎng)絡(luò)對(duì)每個(gè)網(wǎng)絡(luò)的魯棒性進(jìn)行了深入研究.Hong等［7］提出了一種改進(jìn)魯棒性指標(biāo)R的計(jì)算效率的方法，即當(dāng)失效節(jié)點(diǎn)的值達(dá)到臨界閾值qc時(shí)，引入一種計(jì)算效率較高的魯棒性測(cè)度R′.Holme等［8］對(duì)現(xiàn)有的幾種復(fù)雜網(wǎng)絡(luò)模型以及科學(xué)協(xié)作和互聯(lián)網(wǎng)的現(xiàn)實(shí)網(wǎng)絡(luò)進(jìn)行了數(shù)值研究，并用最大連通子圖的大小來(lái)定量測(cè)量網(wǎng)絡(luò)性能.田晶等［9］基于大樣本城市道路網(wǎng)的魯棒性及受不同魯棒性模型、不同攻擊測(cè)量的影響作出分析.金成菲等［10］為了評(píng)價(jià)公共交通在高峰時(shí)段的運(yùn)行狀態(tài)，研究交通擁堵影響下公交網(wǎng)絡(luò)的魯棒性.基于Python技術(shù)，獲取平臺(tái)分析車(chē)輛出行大數(shù)據(jù)得出的擁堵指數(shù)，以擁堵指數(shù)作為權(quán)值，構(gòu)建了公交線網(wǎng)無(wú)向加權(quán)的復(fù)雜網(wǎng)絡(luò).雷永霞等［11］針對(duì)我國(guó)高速鐵路客運(yùn)專(zhuān)線運(yùn)輸網(wǎng)絡(luò)受到站點(diǎn)攻擊時(shí)邊權(quán)值對(duì)網(wǎng)絡(luò)魯棒性的影響，依據(jù)復(fù)雜網(wǎng)絡(luò)理論，利用Pajek軟件建立了高速鐵路客運(yùn)專(zhuān)線無(wú)向加權(quán)運(yùn)輸網(wǎng)絡(luò)模型，利用Matlab分析了該網(wǎng)絡(luò)模型在隨機(jī)站點(diǎn)攻擊和蓄意站點(diǎn)攻擊下的連通魯棒性和功能魯棒性評(píng)價(jià)指標(biāo).

魯棒性分析是通過(guò)對(duì)復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行攻擊達(dá)到的，城市交通網(wǎng)絡(luò)通過(guò)原圖法（primal approach，PA）所組成的復(fù)雜網(wǎng)絡(luò)中，節(jié)點(diǎn)代表道路交叉口，邊表示城市道路.本文在傳統(tǒng)的攻擊節(jié)點(diǎn)方法的基礎(chǔ)上，提出了結(jié)合復(fù)合邊權(quán)重的對(duì)邊攻擊策略模型，該模型既體現(xiàn)了路口在整體城市交通網(wǎng)絡(luò)中的連接度，同時(shí)顧及最短路徑通過(guò)每條道路的次數(shù)，在城市交通網(wǎng)絡(luò)的魯棒性分析中更貼合實(shí)際，并最大限度的保留了城市交通網(wǎng)絡(luò)的布局特點(diǎn).

1 網(wǎng)絡(luò)研究方法

1.1 復(fù)雜網(wǎng)絡(luò)基本屬性

構(gòu)建網(wǎng)絡(luò)模型之前對(duì)復(fù)雜網(wǎng)絡(luò)的基本屬性進(jìn)行介紹，以便后文分析使用.

1）網(wǎng)絡(luò)的平均路徑長(zhǎng)度也被稱(chēng)為網(wǎng)絡(luò)的特征路徑長(zhǎng)度，用來(lái)界定一個(gè)網(wǎng)絡(luò)中所有節(jié)點(diǎn)對(duì)之間的最短路徑的平均長(zhǎng)度，可通過(guò)公式表達(dá)為：

式中：n為節(jié)點(diǎn)總數(shù)；dij為節(jié)點(diǎn)i與節(jié)點(diǎn)j間的最短路徑長(zhǎng)度．i，j∈ n，n=1，2，…，n．

2）加權(quán)網(wǎng)絡(luò)效率是指加權(quán)網(wǎng)絡(luò)在被攻擊導(dǎo)致本身的構(gòu)成發(fā)生了變化后對(duì)最短路徑產(chǎn)生的影響，在計(jì)算最短路徑時(shí)應(yīng)考慮兩點(diǎn)間最短路徑所涉及的邊的權(quán)重，若兩點(diǎn)間不存在最短路徑則將長(zhǎng)度表示為無(wú)窮大，兩個(gè)節(jié)點(diǎn)之間的效率通過(guò)計(jì)算兩點(diǎn)間最短路徑長(zhǎng)度的倒數(shù)表示，加權(quán)網(wǎng)絡(luò)效率則通過(guò)計(jì)算所有節(jié)點(diǎn)之間效率的平均值得出，可通過(guò)公式表達(dá)為：

3）節(jié)點(diǎn)介數(shù)代表網(wǎng)絡(luò)中所有經(jīng)過(guò)某節(jié)點(diǎn)的最短路徑數(shù)占最短路徑總數(shù)的比例，節(jié)點(diǎn)介數(shù)的提出彌補(bǔ)了節(jié)點(diǎn)度對(duì)于節(jié)點(diǎn)在網(wǎng)絡(luò)中重要性描述不夠精確的問(wèn)題，反映了該節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性，可通過(guò)公式表達(dá)為：

式中：njk為節(jié)點(diǎn) j、k之間最短路徑的總數(shù)；njk（i）為經(jīng)過(guò)節(jié)點(diǎn)i的j、k間最短路徑的數(shù)量．

4）最大連通子圖（maximal connected subgraph，MCS）表示把網(wǎng)絡(luò)中所有節(jié)點(diǎn)用最少的邊將其連接起來(lái)的子圖，因其具有不唯一性所以也可稱(chēng)為極大連通子圖.通常作為判斷網(wǎng)絡(luò)的連通性的指標(biāo)［12-15］.

1.2 網(wǎng)絡(luò)模型構(gòu)建方法

城市交通網(wǎng)絡(luò)根據(jù)其拓?fù)涮匦猿橄鬄榫W(wǎng)絡(luò)模型的方法有兩種：原圖法和對(duì)偶法（dual approach，DA）.原圖法是一種將城市道路之間的交叉抽象為網(wǎng)絡(luò)中的節(jié)點(diǎn)，將交叉間的路段抽象為連接節(jié)點(diǎn)的邊的建模方法；對(duì)偶法一般指原圖法的對(duì)偶，是一種將城市的道路抽象為網(wǎng)絡(luò)中的節(jié)點(diǎn)，將城市道路間的相連關(guān)系抽象為連接節(jié)點(diǎn)的邊的建模方法.

在實(shí)際應(yīng)用過(guò)程中，上述兩種網(wǎng)絡(luò)模型構(gòu)建方法各有優(yōu)劣.原圖法構(gòu)建的網(wǎng)絡(luò)最大限度的保留了城市交通網(wǎng)絡(luò)的布局特點(diǎn)，能夠精確的表現(xiàn)城市交通網(wǎng)絡(luò)的地理布局，但是在表達(dá)道路之間潛在的連接關(guān)系上不夠明確.對(duì)偶法構(gòu)建的網(wǎng)絡(luò)將道路間的連接關(guān)系表達(dá)得十分清楚，但是忽略了城市交通網(wǎng)絡(luò)的空間特性導(dǎo)致這種方法喪失了直觀性.在兩種方法的比對(duì)權(quán)衡后，本文選用原圖法進(jìn)行網(wǎng)絡(luò)的構(gòu)建與分析.

1.3 邊加權(quán)方法

現(xiàn)實(shí)世界中大部分網(wǎng)絡(luò)都是加權(quán)網(wǎng)絡(luò)，網(wǎng)絡(luò)中邊的權(quán)重通常表示這條邊的承載能力或與節(jié)點(diǎn)間的聯(lián)系程度．可以用V=（N，W）描述加權(quán)網(wǎng)絡(luò)，其中N為節(jié)點(diǎn)數(shù)，W為邊的權(quán)重，可構(gòu)建其加權(quán)鄰接矩陣W =（wij）n*n，其中 i，j=1，2，…，N．

目前定義邊權(quán)重的主流方法有兩種，分別是節(jié)點(diǎn)度法及節(jié)點(diǎn)介數(shù)法．其中節(jié)點(diǎn)度法的主要思路是將與邊相連的兩個(gè)節(jié)點(diǎn)的度k相乘以得到邊權(quán)重，可通過(guò)公式表達(dá)為：

介數(shù)法則是通過(guò)與邊相連的兩個(gè)節(jié)點(diǎn)的介數(shù)相乘得到的，這種方法的優(yōu)點(diǎn)是能夠更準(zhǔn)確的反應(yīng)邊在網(wǎng)絡(luò)中的重要程度，可通過(guò)公式表達(dá)為：

再結(jié)合式（4）與式（5）綜合考慮節(jié)點(diǎn)的度與介數(shù)后可得出復(fù)合邊權(quán)重的計(jì)算可通過(guò)公式表達(dá)為：

式中：θ為可調(diào)的權(quán)重參數(shù)，文獻(xiàn)［4-7］中總結(jié)出當(dāng)θ?1時(shí)臨界閾值最小；α為比重系數(shù)，0≤α≤1，當(dāng)α=0表示邊的權(quán)重僅與節(jié)點(diǎn)的度相關(guān)，當(dāng)α=1表示邊的權(quán)重僅與節(jié)點(diǎn)的介數(shù)相關(guān)．

2 實(shí)驗(yàn)及分析

2.1 網(wǎng)絡(luò)數(shù)據(jù)及構(gòu)建

在實(shí)驗(yàn)中本文選用2019年8月天津市中心路段交通地圖構(gòu)建城市交通網(wǎng)絡(luò)，以ArcGIS10.8作為空間數(shù)據(jù)的采集平臺(tái)，首先提取可編輯的路網(wǎng)數(shù)據(jù)，經(jīng)過(guò)拓?fù)錂z查處理懸掛點(diǎn)、偽結(jié)點(diǎn)、孤立路段與冗余路段，得到一個(gè)包含366個(gè)道路交叉口與703個(gè)路段的天津市中心路網(wǎng)圖，隨后通過(guò)原圖法將每個(gè)道路交叉口抽象為節(jié)點(diǎn)，路段抽象為邊，得到相應(yīng)的路網(wǎng)圖與連接圖如圖1所示.

圖1 天津市中心路網(wǎng)圖及其拓?fù)潢P(guān)系圖Fig．1 Tianjin center road network and its topological relationship

2.2 計(jì)算分析網(wǎng)絡(luò)特征值

根據(jù)連接圖，結(jié)合Python編寫(xiě)特征值計(jì)算程序可得該網(wǎng)絡(luò)的最大度、最小度、密度與平均度，并分別采用式（1）、式（2）得到該路網(wǎng)的群聚系數(shù)與平均路徑長(zhǎng)度如表1所列.

表1 網(wǎng)絡(luò)特征值計(jì)算結(jié)果Tab．1 Calculation results of network eigenvalues

2.3 計(jì)算邊權(quán)重

首先以節(jié)點(diǎn)度法對(duì)天津市中心路網(wǎng)中所包含的703條邊進(jìn)行加權(quán)，將網(wǎng)絡(luò)中所有節(jié)點(diǎn)進(jìn)行編號(hào)，計(jì)算構(gòu)成一條邊的兩個(gè)節(jié)點(diǎn)a與b各自的度并結(jié)合式（4）進(jìn)行相乘處理，而后將所得結(jié)果歸一化處理得到邊的節(jié)點(diǎn)度權(quán)重，部分結(jié)果如表2所列.

表2 節(jié)點(diǎn)度法權(quán)重計(jì)算結(jié)果Tab．2 Node degree method weight calculation result

其次以介數(shù)法對(duì)網(wǎng)絡(luò)中的邊加權(quán)，計(jì)算構(gòu)成一條邊的兩個(gè)節(jié)點(diǎn)各自的介數(shù)并結(jié)合式（5）進(jìn)行相乘處理，隨后將所得結(jié)果歸一化處理得到邊的介數(shù)權(quán)重，部分結(jié)果如表3所列.

表3 介數(shù)法權(quán)重計(jì)算結(jié)果Tab．3 Calculation result of betweenness method weight

最后以復(fù)合權(quán)重法對(duì)網(wǎng)絡(luò)中的邊加權(quán)，結(jié)合式（6）對(duì)節(jié)點(diǎn)度法權(quán)重與介數(shù)法權(quán)重進(jìn)行計(jì)算，取α=0．3，θ=1，得到邊的復(fù)合權(quán)重如表4所列.

表4 復(fù)合法權(quán)重計(jì)算結(jié)果Tab．4 Com pound method weight calculation result

2.4 魯棒性分析

魯棒性（robustness）由其英文音譯而來(lái)，也可稱(chēng)為抗毀性、穩(wěn)健性、強(qiáng)健性，是系統(tǒng)的抗毀能力，它是在異常和危險(xiǎn)情況下系統(tǒng)生存的關(guān)鍵，是指系統(tǒng)在一定的攻擊策略下，維持某些性能的特性.本文采用網(wǎng)絡(luò)效率與文獻(xiàn)［15-17］提出的通過(guò)最大聯(lián)通子圖衡量攻擊后網(wǎng)絡(luò)性能的方法.

本文通過(guò)最大連通子圖的相對(duì)大小S作為衡量網(wǎng)絡(luò)連通魯棒性的評(píng)價(jià)標(biāo)準(zhǔn)，其計(jì)算公式如下：

式中：N為未遭受攻擊時(shí)網(wǎng)絡(luò)中的初始節(jié)點(diǎn)總數(shù)；M為該網(wǎng)絡(luò)遭受攻擊后最大連通子圖中所包含的節(jié)點(diǎn)數(shù)．

本文采用隨機(jī)攻擊策略、基于度權(quán)重的邊攻擊策略、基于介數(shù)權(quán)重的邊攻擊策略與基于復(fù)合權(quán)重的邊攻擊策略四種方法對(duì)天津市中心路網(wǎng)進(jìn)行攻擊以分析其魯棒性.

圖2給出了天津市中心城區(qū)交通網(wǎng)中邊分別受到隨機(jī)攻擊與蓄意攻擊（度攻擊、介數(shù)攻擊與復(fù)合攻擊）后，最大聯(lián)通子圖相對(duì)大小S的變化，圖中的橫坐標(biāo)f表示網(wǎng)絡(luò)的損毀程度，即在網(wǎng)絡(luò)中受到攻擊的邊數(shù)與初始網(wǎng)絡(luò)中總邊數(shù)的比值.隨著網(wǎng)絡(luò)中被攻擊的邊的數(shù)量增加，逐漸出現(xiàn)了被孤立的節(jié)點(diǎn)，導(dǎo)致網(wǎng)絡(luò)的最大連通子圖的規(guī)模不斷的縮減直至網(wǎng)絡(luò)崩潰.分析圖2可知，在隨機(jī)攻擊的策略下，當(dāng)網(wǎng)絡(luò)的損毀程度接近1時(shí)，最大連通子圖的相對(duì)大小才接近于0；在度攻擊策略下，網(wǎng)絡(luò)的損毀程度接近0.8時(shí)，最大連通子圖的相對(duì)大小接近0；而在介數(shù)攻擊與復(fù)合攻擊策略下，網(wǎng)絡(luò)損毀程度接近0.7時(shí)，最大連通子圖的相對(duì)大小接近0.同時(shí)在邊損毀至35%時(shí)，在介數(shù)攻擊策略下網(wǎng)絡(luò)最大連通子圖的相對(duì)大小呈斷崖式下降；而在邊損毀至40%時(shí)，在度攻擊策略下網(wǎng)絡(luò)最大連通子圖的相對(duì)大小呈斷崖式下降，如圖2所示.

圖2 最大連通子圖與邊刪除比例關(guān)系圖Fig．2 Ratio of the largest connected subgraph to the removed edges

圖3 給出了天津市中心城區(qū)交通網(wǎng)中邊分別受到隨機(jī)攻擊與蓄意攻擊（度攻擊、介數(shù)攻擊與復(fù)合攻擊）后，加權(quán)網(wǎng)絡(luò)效率Ew的變化.網(wǎng)絡(luò)在初始狀態(tài)時(shí)，加權(quán)網(wǎng)絡(luò)效率為0.13，在隨機(jī)攻擊的策略下，當(dāng)網(wǎng)絡(luò)的損毀程度接近1時(shí)，加權(quán)網(wǎng)絡(luò)效率才接近于0；在蓄意攻擊的策略下，當(dāng)網(wǎng)絡(luò)的損毀程度接近0.8時(shí)，加權(quán)網(wǎng)絡(luò)效率接近于0，如圖3所示.

圖3 加權(quán)網(wǎng)絡(luò)效率與邊刪除比例關(guān)系圖Fig．3 Scale of weighted network efficiency vs．removed edges

上述分析可得，網(wǎng)絡(luò)在蓄意攻擊下魯棒性明顯變?nèi)酰瑫r(shí)在網(wǎng)絡(luò)損毀至不同階段時(shí)，度攻擊策略與介數(shù)攻擊策略都會(huì)使網(wǎng)絡(luò)最大連通子圖的相對(duì)大小呈現(xiàn)斷崖式下降.在單個(gè)邊受到攻擊時(shí)，整體網(wǎng)絡(luò)的魯棒性變化并不明顯.

3 結(jié)論

本文將天津市中心城區(qū)交通網(wǎng)絡(luò)抽象建模成無(wú)向加權(quán)復(fù)雜網(wǎng)絡(luò)，通過(guò)拓?fù)浣Y(jié)構(gòu)特性研究分析其魯棒性.利用本文涉及的多種邊攻擊策略，經(jīng)計(jì)算分析可得出如下結(jié)論：

1）在大部分邊受到隨機(jī)攻擊從而導(dǎo)致失效時(shí)，天津市中心城區(qū)交通網(wǎng)絡(luò)仍可以保持相對(duì)穩(wěn)定的連接，魯棒性較為優(yōu)秀，然而在蓄意攻擊策略下，當(dāng)受到攻擊的邊達(dá)到60%～80%時(shí)整個(gè)網(wǎng)絡(luò)便會(huì)崩潰癱瘓.同時(shí)，部分權(quán)重較大的邊對(duì)網(wǎng)絡(luò)的整體連通性起到至關(guān)重要的作用，這些道路失效會(huì)使網(wǎng)絡(luò)的連通性急速下降.

2）加權(quán)邊介數(shù)攻擊與加權(quán)度攻擊對(duì)網(wǎng)絡(luò)的破壞性較強(qiáng)，且復(fù)合權(quán)重攻擊策略可以兼顧上述兩種蓄意攻擊的模式.

3）通過(guò)對(duì)造成網(wǎng)絡(luò)連通性斷崖式下降的邊進(jìn)行分析與識(shí)別，發(fā)現(xiàn)天津市中心干道（如南京路、衛(wèi)津路等）的魯棒性明顯較差，應(yīng)對(duì)關(guān)鍵道路采取有效的防護(hù)措施并及時(shí)進(jìn)行日常維護(hù)，降低突發(fā)災(zāi)害事件對(duì)城市交通網(wǎng)絡(luò)連通性的影響從而降低損失.

本文只考慮了結(jié)合復(fù)合權(quán)重邊的攻擊策略，如何結(jié)合復(fù)雜網(wǎng)絡(luò)的動(dòng)力學(xué)并考慮網(wǎng)絡(luò)的級(jí)聯(lián)失效性以及其他因素對(duì)網(wǎng)絡(luò)魯棒性的影響，還有待進(jìn)一步的研究.