基于貪心介數(shù)的地鐵-公交復(fù)合網(wǎng)絡(luò)關(guān)鍵車站識(shí)別算法

汪 軍,夏永躍,王運(yùn)明,李衛(wèi)東

(大連交通大學(xué)自動(dòng)化與電氣工程學(xué)院,大連 116028)

引言

城市軌道交通具有快速、大運(yùn)量和污染小等優(yōu)勢(shì)，能有效緩解城市交通擁堵問題。隨著城市化進(jìn)程快速發(fā)展，大中型城市構(gòu)建了以軌道交通為骨架，快速公交、常規(guī)公交等相融合的地鐵-公交復(fù)合交通網(wǎng)絡(luò)體系。地鐵-公交復(fù)合網(wǎng)絡(luò)作為重要的城市交通基礎(chǔ)設(shè)施，極大地方便了人們出行，提高了整個(gè)城市的運(yùn)轉(zhuǎn)效率。然而，網(wǎng)絡(luò)規(guī)模的擴(kuò)大，增加了網(wǎng)絡(luò)的復(fù)雜性，對(duì)地鐵-公交復(fù)合網(wǎng)絡(luò)的魯棒性提出了更高要求。尤其是關(guān)鍵車站發(fā)生故障會(huì)極大影響交通網(wǎng)絡(luò)的運(yùn)輸效率，甚至引發(fā)網(wǎng)絡(luò)癱瘓。因此，識(shí)別地鐵-公交復(fù)合網(wǎng)絡(luò)的關(guān)鍵車站不僅對(duì)指導(dǎo)線網(wǎng)規(guī)劃、線站位布局以及運(yùn)營(yíng)管理具有重要意義，還可為應(yīng)對(duì)大型群眾活動(dòng)、自然災(zāi)害等突發(fā)公共事件引發(fā)的集群式人員流動(dòng)提供科學(xué)的疏導(dǎo)策略。

近年來(lái)，復(fù)雜網(wǎng)絡(luò)理論在交通網(wǎng)絡(luò)領(lǐng)域得到了廣泛引用，分析了交通網(wǎng)絡(luò)的特征與規(guī)律。學(xué)者們提出了Space L、Space P、Space R等多種交通網(wǎng)絡(luò)建模方法。LI等[1]采用Space L、Space P方法分別構(gòu)建地鐵網(wǎng)絡(luò)、公交網(wǎng)絡(luò)和地鐵-公交復(fù)合網(wǎng)絡(luò)模型，發(fā)現(xiàn)地鐵-公交復(fù)合網(wǎng)絡(luò)具有更強(qiáng)的魯棒性。DING等[2]采用復(fù)雜網(wǎng)絡(luò)建立城市地鐵網(wǎng)絡(luò)模型，并分析了網(wǎng)絡(luò)特征。LUO等[3]采用Space L和Space P方法構(gòu)建北京市地鐵-公交復(fù)合網(wǎng)絡(luò)及其子網(wǎng)絡(luò)模型，分析表明網(wǎng)絡(luò)具備小世界和無(wú)標(biāo)度特性，復(fù)合網(wǎng)絡(luò)可增強(qiáng)乘客的換乘效率。沈黎等[4]通過(guò)L、P、R空間建立城市公共交通網(wǎng)絡(luò)模型并分析網(wǎng)絡(luò)特征。KUNT等[5]提出基于網(wǎng)絡(luò)聚集的關(guān)鍵車站識(shí)別方法，通過(guò)考慮節(jié)點(diǎn)的度和位置確定關(guān)鍵車站。CAO等[6]分析了關(guān)鍵節(jié)點(diǎn)對(duì)公交網(wǎng)絡(luò)健壯性的影響，發(fā)現(xiàn)采用介數(shù)中心性方法識(shí)別的關(guān)鍵車站對(duì)網(wǎng)絡(luò)破壞性最嚴(yán)重。嚴(yán)開等[7]提出了基于Pagerank的道路交通關(guān)鍵車站識(shí)別方法。江成等[8]提出通過(guò)計(jì)算最小二階路徑內(nèi)連通節(jié)點(diǎn)對(duì)的個(gè)數(shù)判斷節(jié)點(diǎn)重要性。LIU等[9]結(jié)合交通流量特征，提出基于加權(quán)中心性的關(guān)鍵節(jié)點(diǎn)識(shí)別算法，提高城市交通網(wǎng)絡(luò)的關(guān)鍵站點(diǎn)識(shí)別精度。劉菁[10]提出了考慮節(jié)點(diǎn)連通可靠度的關(guān)鍵節(jié)點(diǎn)識(shí)別算法，分析了交通效能的變化情況。薛鋒[11]提出灰色關(guān)聯(lián)和TOPSIS相結(jié)合的關(guān)鍵站點(diǎn)識(shí)別方法。陳詩(shī)等[12]從時(shí)序網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和動(dòng)力學(xué)角度，系統(tǒng)地分析了現(xiàn)有的關(guān)鍵節(jié)點(diǎn)識(shí)別方法。ADDIS等[13]提出基于貪心策略的關(guān)鍵節(jié)點(diǎn)識(shí)別算法。YE等[14]提出了貪心隨機(jī)動(dòng)態(tài)組合選擇算法，從局部最優(yōu)中尋找最優(yōu)子集的極值，加強(qiáng)迭代之間的鏈接，提高關(guān)鍵車站的識(shí)別精度。KIM[15]改進(jìn)貪婪控制方法對(duì)特定交通條件下的流量限制，提高了搜索效率。蔡盼等[16]提出了一種基于貪心策略的最近鄰算法。

為挖掘地鐵-公交復(fù)合網(wǎng)絡(luò)的關(guān)鍵車站，提高關(guān)鍵車站的識(shí)別精度，采用復(fù)雜網(wǎng)絡(luò)理論建立地鐵-公交復(fù)合網(wǎng)絡(luò)模型，提出基于貪心介數(shù)的地鐵-公交復(fù)合網(wǎng)絡(luò)關(guān)鍵車站識(shí)別算法。考慮刪除某些重要車站后，剩余車站的重要度排序發(fā)生動(dòng)態(tài)變化的特點(diǎn)，在介數(shù)中心性算法的基礎(chǔ)上，引入貪心算法，選擇當(dāng)前最關(guān)鍵的車站，擴(kuò)大關(guān)鍵車站的影響力。以成都市地鐵-公交復(fù)合網(wǎng)絡(luò)為例，驗(yàn)證該算法的可行性與有效性，提高網(wǎng)絡(luò)的魯棒性。

1 地鐵-公交復(fù)合網(wǎng)絡(luò)模型

為準(zhǔn)確描述地鐵-公交復(fù)合交通網(wǎng)絡(luò)的相互關(guān)系，采用復(fù)雜網(wǎng)絡(luò)理論建立地鐵-公交復(fù)合網(wǎng)絡(luò)模型。交通網(wǎng)絡(luò)主要有Space L和Space P兩種建模方法。Space L方法將車站抽象為節(jié)點(diǎn)，若兩個(gè)車站地理位置相鄰并有同一個(gè)車次通過(guò)，則節(jié)點(diǎn)之間有連邊；Space P方法也將車站抽象為節(jié)點(diǎn)，若車站之間有直達(dá)的車次，則節(jié)點(diǎn)之間有連邊。

地鐵-公交復(fù)合交通網(wǎng)絡(luò)是由不同的車站和線路構(gòu)成的復(fù)雜網(wǎng)絡(luò)，采用Space L方法構(gòu)建網(wǎng)絡(luò)模型，將地鐵-公交復(fù)合網(wǎng)絡(luò)分為層內(nèi)網(wǎng)絡(luò)和層間網(wǎng)絡(luò)，其中層內(nèi)網(wǎng)絡(luò)為公交和地鐵兩個(gè)獨(dú)立的復(fù)雜網(wǎng)絡(luò)，層間網(wǎng)絡(luò)為地鐵網(wǎng)絡(luò)和公交網(wǎng)絡(luò)的車站之間存在耦合關(guān)系而形成的網(wǎng)絡(luò)。地鐵-公交復(fù)合網(wǎng)絡(luò)表示為GB-S={GB，GS，RB-S}。

地鐵網(wǎng)絡(luò)描述為GS，其中，VS表示地鐵車站集合，ES表示地鐵線路集合；公交網(wǎng)絡(luò)描述為GB，其中，VB表示公交車站集合，EB表示公交線路集合。

在城市規(guī)劃建設(shè)中，為增強(qiáng)城市交通系統(tǒng)的運(yùn)輸效率和運(yùn)輸范圍，一般1個(gè)地鐵車站周圍會(huì)設(shè)置多個(gè)公交車站，形成一對(duì)多的耦合關(guān)系，即?si∈VS，?bj∈VB，使得si→bj。設(shè)矩陣R為層間網(wǎng)絡(luò)的耦合矩陣，矩陣元素rij表示節(jié)點(diǎn)si和bj之間的耦合關(guān)系，則R=[rij]NP×NF，其中si→bj時(shí)，rij=1；否則rij=0。

城市地鐵-公交復(fù)合網(wǎng)絡(luò)進(jìn)一步表示為GB-S。其中，V表示地鐵-公交復(fù)合網(wǎng)絡(luò)的節(jié)點(diǎn)集合，V=VB∪VS；E表示地鐵-公交復(fù)合網(wǎng)絡(luò)的邊集合，E=EB∪ES∪ER，ER表示地鐵網(wǎng)絡(luò)GS和公交網(wǎng)絡(luò)GB之間存在的耦合邊集合。

地鐵-公交復(fù)合網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)如圖1所示，上層為公交網(wǎng)絡(luò)，下層為地鐵網(wǎng)絡(luò)，兩層之間的連接為層間耦合關(guān)系。地鐵網(wǎng)絡(luò)的車站S2周圍存在3個(gè)公交車站B1、B2、B3，乘客步行就可到達(dá)并換乘(限定200 m)，兩者建立層間耦合關(guān)系s2→(b1，b2，b3)。

圖1 地鐵-公交復(fù)合網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)

2 基于貪心介數(shù)的復(fù)合網(wǎng)絡(luò)關(guān)鍵車站識(shí)別算法

2.1 貪心策略

王翔等[17-18]最早提出的貪心算法用于解決網(wǎng)絡(luò)的影響力最大化問題。在問題求解時(shí)，使用貪心策略做出在當(dāng)前最好的選擇。主要思想是每一步迭代都將重新計(jì)算當(dāng)前未被激活的節(jié)點(diǎn)加入種子節(jié)點(diǎn)集后的邊際效益，選擇使得邊際效益增加最大的節(jié)點(diǎn)作為下一個(gè)種子節(jié)點(diǎn)。具體過(guò)程如下：

(1)輸入網(wǎng)絡(luò)圖D=(aij)n×n，利用重要度(如：度、PR值、接近中心性等)計(jì)算方法計(jì)算節(jié)點(diǎn)重要程度并進(jìn)行排序；

(2)初始化一個(gè)空集L=?，將重要度最大的節(jié)點(diǎn)記錄于集合L，并從網(wǎng)絡(luò)中刪除該節(jié)點(diǎn)，此時(shí)，最大連通分支記為CV；

(3)選擇CV中重要度最大的節(jié)點(diǎn)記錄于集合L，并刪除該節(jié)點(diǎn)；

(4)調(diào)用Warshall算法判斷是否存在連通子圖，若存在，重復(fù)步驟(3)，直至網(wǎng)絡(luò)不存在連通子圖，或網(wǎng)絡(luò)剩余節(jié)點(diǎn)都成為孤立節(jié)點(diǎn)，貪心策略結(jié)束。

貪心算法具有較高的魯棒性，算法在解決影響力最大化問題中準(zhǔn)確率最低也可以達(dá)到63%。但是，較高的準(zhǔn)確率帶來(lái)的卻是非常高的時(shí)間復(fù)雜度，在小規(guī)模的網(wǎng)絡(luò)中，貪心算法可以發(fā)揮出其優(yōu)異的性能，但對(duì)于規(guī)模較大的網(wǎng)絡(luò)，算法的時(shí)間復(fù)雜度過(guò)高。

2.2 介數(shù)中心性

介數(shù)中心性表示網(wǎng)絡(luò)中節(jié)點(diǎn)間最短路徑經(jīng)過(guò)某節(jié)點(diǎn)的數(shù)目，是刻畫節(jié)點(diǎn)網(wǎng)絡(luò)結(jié)構(gòu)特征的重要指標(biāo)之一。節(jié)點(diǎn)介數(shù)中心性越大，網(wǎng)絡(luò)中經(jīng)過(guò)該節(jié)點(diǎn)的最短路徑條數(shù)越多，說(shuō)明節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)的信息傳播或流通控制能力越強(qiáng)，該節(jié)點(diǎn)在網(wǎng)絡(luò)中也就越重要。定義為

(1)

2.3 基于貪心介數(shù)的關(guān)鍵車站識(shí)別算法

為提高關(guān)鍵車站的識(shí)別精度，考慮刪除某些重要車站后，剩余車站的重要度排序發(fā)生動(dòng)態(tài)變化的特點(diǎn)，引入貪心算法，提出基于貪心介數(shù)的地鐵-公交復(fù)合網(wǎng)絡(luò)關(guān)鍵車站識(shí)別算法。

該算法的設(shè)計(jì)思想是：首先計(jì)算地鐵-公交復(fù)合網(wǎng)絡(luò)中每個(gè)車站的介數(shù)值，刪除網(wǎng)絡(luò)中車站介數(shù)最大的節(jié)點(diǎn)，并將其記錄到車站重要性序列表中；如果剩余車站構(gòu)成的節(jié)點(diǎn)集合還存在連通性，則再次計(jì)算剩余車站構(gòu)成的網(wǎng)絡(luò)最大連通分支以及最大連通分支中每個(gè)車站的介數(shù)值，刪除最大連通分支中車站介數(shù)最大的節(jié)點(diǎn)，并將其記錄到車站重要性序列表中；如此反復(fù)，直至車站重要性序列表的車站個(gè)數(shù)為網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)或剩余車站都為孤立節(jié)點(diǎn)。

算法的具體過(guò)程描述如下：

(1)輸入地鐵-公交復(fù)合網(wǎng)絡(luò)的鄰接矩陣D=(aij)n×n，初始化重要度序列L=?、最大連通分支節(jié)點(diǎn)集合CV=?、孤立節(jié)點(diǎn)集合CS=?；

(2)計(jì)算當(dāng)前網(wǎng)絡(luò)各節(jié)點(diǎn)的介數(shù)值，介數(shù)最大節(jié)點(diǎn)序號(hào)記錄到重要度序列L=L∪{i}；

(3)刪除網(wǎng)絡(luò)中介數(shù)最大的節(jié)點(diǎn)i，刪除后網(wǎng)絡(luò)中的孤立節(jié)點(diǎn)記錄到集合CS中；

(4)調(diào)用Warshall算法判斷刪除節(jié)點(diǎn)后的網(wǎng)絡(luò)是否存在連通子圖，若存在，將最大連通分支節(jié)點(diǎn)集合記錄到CV，并返回至(2)；若不存在，則結(jié)束。

3 仿真分析

為驗(yàn)證本文提出的地鐵-公交復(fù)合網(wǎng)絡(luò)關(guān)鍵車站識(shí)別算法的可行性和有效性，根據(jù)百度地圖網(wǎng)站提供的成都市市區(qū)地鐵-公交復(fù)合網(wǎng)絡(luò)數(shù)據(jù)，利用復(fù)雜網(wǎng)絡(luò)理論，將公交、地鐵的車站抽象為節(jié)點(diǎn)，車站之間的連接關(guān)系抽象為邊，建立成都市地鐵-公交復(fù)合網(wǎng)絡(luò)模型?？紤]部分近鄰公交站點(diǎn)的重復(fù)性，合并處理相距100 m的重名站點(diǎn)，限定地鐵車站周邊200 m范圍內(nèi)的公交站點(diǎn)為有效站點(diǎn)，與地鐵車站建立連邊。該網(wǎng)絡(luò)包含886個(gè)公交車站的162條公交線路和只考慮市區(qū)范圍內(nèi)42個(gè)地鐵車站的5條地鐵線路。利用Gephi軟件建立的成都市地鐵-公交復(fù)合網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖2所示。

圖2 成都市地鐵-公交復(fù)合網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

成都市地鐵-公交復(fù)合網(wǎng)絡(luò)與獨(dú)立網(wǎng)絡(luò)的各類特征指標(biāo)對(duì)比結(jié)果如表1所示。地鐵-公交復(fù)合網(wǎng)絡(luò)的平均度4.287最高，說(shuō)明復(fù)合網(wǎng)絡(luò)中任意車站的鄰接車站數(shù)高于地鐵和公交網(wǎng)絡(luò)。因所選取地鐵網(wǎng)絡(luò)數(shù)據(jù)中有5個(gè)換乘車站，10個(gè)邊緣站點(diǎn)，所以地鐵平均度為2，地鐵網(wǎng)絡(luò)的平均聚集系數(shù)為0。因?yàn)槿我庖粋€(gè)地鐵車站的鄰接車站并不會(huì)通過(guò)地鐵線路再相互連接，只能通過(guò)地面公交中轉(zhuǎn)，地鐵和公交相互銜接、配合可有效提高出行效率。復(fù)合網(wǎng)絡(luò)的平均路徑長(zhǎng)度7.237小于公交網(wǎng)絡(luò)9.188，說(shuō)明復(fù)合網(wǎng)絡(luò)中客流從一個(gè)車站到另一車站出行的平均距離比單獨(dú)使用公交出行要小。交通網(wǎng)絡(luò)中度值大于2的站點(diǎn)一般為換乘車站，起到樞紐作用，聚集系數(shù)超過(guò)0.05，表明此車站應(yīng)是居住型、商業(yè)、旅游景點(diǎn)等人群密集型車站，其中復(fù)合網(wǎng)絡(luò)聚集系數(shù)為0.216遠(yuǎn)高于地鐵、公交網(wǎng)絡(luò)，具有很強(qiáng)的聚集特性。通過(guò)對(duì)網(wǎng)絡(luò)拓?fù)涮匦缘姆治?，表明地鐵-公交復(fù)合網(wǎng)絡(luò)具備無(wú)標(biāo)度和小世界特性。

表1 成都市地鐵-公交復(fù)合網(wǎng)絡(luò)拓?fù)潇o態(tài)指標(biāo)

最大連通子圖、網(wǎng)絡(luò)效率、圈數(shù)率、連通度等指標(biāo)是衡量復(fù)雜網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)識(shí)別精度重要指標(biāo)[19-20]，因此，本文采用這些指標(biāo)評(píng)價(jià)基于貪心介數(shù)的地鐵-公交復(fù)合網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別算法的優(yōu)勢(shì)。運(yùn)用軟件Matlab進(jìn)行仿真分析。

地鐵-公交復(fù)合交通網(wǎng)絡(luò)中存在大量度為2的節(jié)點(diǎn)，攻擊此類節(jié)點(diǎn)易形成獨(dú)立子集團(tuán)，使得最大連通子圖能夠很好地評(píng)估關(guān)鍵節(jié)點(diǎn)識(shí)別的精度。網(wǎng)絡(luò)的最大連通子圖比例定義為網(wǎng)絡(luò)的最大連通子圖節(jié)點(diǎn)數(shù)與網(wǎng)絡(luò)總節(jié)點(diǎn)數(shù)的比值，反映被刪除節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的影響。如果被刪除的是邊緣節(jié)點(diǎn)，則最大連通子圖的節(jié)點(diǎn)個(gè)數(shù)依然接近網(wǎng)絡(luò)初始節(jié)點(diǎn)數(shù)；如果被刪除的節(jié)點(diǎn)是關(guān)鍵節(jié)點(diǎn)，網(wǎng)絡(luò)會(huì)被劃分成多個(gè)子網(wǎng)，新的最大連通子圖節(jié)點(diǎn)個(gè)數(shù)較少。為增強(qiáng)最大連通子圖的區(qū)分度，提出最大連通子圖相對(duì)大小的概念，定義為

(2)

式中，n為最大連通子圖的節(jié)點(diǎn)數(shù)；N為初始網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)；f為移除節(jié)點(diǎn)的比例。

采用不同策略刪除網(wǎng)絡(luò)中節(jié)點(diǎn)對(duì)最大連通子圖相對(duì)大小的影響，如圖3所示。

圖3 最大連通子圖相對(duì)大小變化曲線

從圖3可知，隨著攻擊車站比例f的增加，地鐵-公交復(fù)合網(wǎng)絡(luò)最大連通子圖逐漸下降。當(dāng)攻擊比例達(dá)到15%時(shí)，隨機(jī)攻擊時(shí)，最大連通子圖相對(duì)大小曲線下降為0.813 9，速度最為緩慢；蓄意攻擊時(shí)，最大連通子圖相對(duì)大小曲線均快速下降，表明攻擊關(guān)鍵節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)結(jié)構(gòu)魯棒性產(chǎn)生較大影響。其中，攻擊貪心介數(shù)算法識(shí)別出的關(guān)鍵節(jié)點(diǎn)時(shí)，最大連通子圖相對(duì)大小曲線下降至0.031 25，下降最快；其次是貪心度中心攻擊下降至0.393 3、介數(shù)攻擊下降至0.575 4、度中心攻擊下降至0.813 9。說(shuō)明貪心介數(shù)算法識(shí)別地鐵-公交復(fù)合網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)準(zhǔn)確率最高。

網(wǎng)絡(luò)效率一般定義為所有節(jié)點(diǎn)對(duì)之間效率的平均值，能夠從全局性的角度分析網(wǎng)絡(luò)效率對(duì)網(wǎng)絡(luò)性能的影響，表示為

(3)

式中，N為網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)量；dij為節(jié)點(diǎn)i和j之間的最短路徑長(zhǎng)度。

采用不同策略刪除網(wǎng)絡(luò)中節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)效率的影響如圖4所示。

圖4 網(wǎng)絡(luò)效率變化曲線

由圖4可以看出，隨著攻擊車站比例f增加，地鐵-公交復(fù)合網(wǎng)絡(luò)的網(wǎng)絡(luò)效率逐漸下降，且蓄意攻擊比隨機(jī)攻擊下降迅速，蓄意攻擊15%以內(nèi)的車站，貪心介數(shù)網(wǎng)絡(luò)效率下降至0.005，貪心度攻擊下降至0.01，介數(shù)下降至0.024，度中心性下降至0.046，隨機(jī)攻擊下降最為緩慢降至0.1。本文提出的基于貪心介數(shù)的關(guān)鍵車站識(shí)別算法相比其他攻擊策略，網(wǎng)絡(luò)效率下降的更快，對(duì)地鐵-公交復(fù)合網(wǎng)絡(luò)的抗毀性影響更大，說(shuō)明本文提出的關(guān)鍵車站識(shí)別精度更高。

圈數(shù)描述了城市公共交通網(wǎng)絡(luò)的可替代路徑的提供能力。城市公共交通網(wǎng)絡(luò)規(guī)模逐漸擴(kuò)大后，圈數(shù)相應(yīng)增加，但網(wǎng)絡(luò)規(guī)模越大并不代表網(wǎng)絡(luò)的魯棒性越強(qiáng)。采用圈數(shù)率反映地鐵-公交復(fù)合網(wǎng)絡(luò)的魯棒性，表示為

(4)

式中，圈數(shù)μ=|D|-|Vd|+1；D為網(wǎng)絡(luò)的邊數(shù)；Vd為網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)目。

采用不同策略刪除網(wǎng)絡(luò)中節(jié)點(diǎn)對(duì)圈數(shù)率的影響如圖5所示。

圖5 網(wǎng)絡(luò)圈數(shù)率變化曲線

由圖5可以看出，隨著攻擊車站比例f增加，隨機(jī)攻擊策略時(shí)，圈數(shù)率下降最為緩慢，蓄意攻擊策略下僅攻擊少量車站，圈數(shù)率從0.13快速下降至0，其中貪心介數(shù)的攻擊策略在攻擊比例達(dá)到15%時(shí)，地鐵-公交復(fù)合網(wǎng)絡(luò)圈數(shù)率降至0.003，下降速度最快，網(wǎng)絡(luò)最先癱瘓；其次是貪心度攻擊下降至0.005、介數(shù)攻擊下降至0.006、度中心性攻擊下降至0.01、隨機(jī)攻擊下降至0.07。通過(guò)對(duì)比說(shuō)明，采用本文提出的關(guān)鍵車站識(shí)別算法攻擊地鐵-公交復(fù)合網(wǎng)絡(luò)，對(duì)網(wǎng)絡(luò)的抗毀性影響最大，關(guān)鍵車站的識(shí)別效果更好。

網(wǎng)絡(luò)連通度是網(wǎng)絡(luò)實(shí)際邊數(shù)目與理論最大邊數(shù)目的比值。與聚集系數(shù)的區(qū)別在于連通度是面向整個(gè)網(wǎng)絡(luò)，而不是網(wǎng)絡(luò)中某個(gè)節(jié)點(diǎn)的域。連通度的計(jì)算公式如下

(5)

式中，D為城市公共交通拓?fù)渚W(wǎng)絡(luò)的邊數(shù)；Vd為城市公共交通網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)目。

采用不同策略刪除網(wǎng)絡(luò)中節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)連通度的影響如圖6所示。

圖6 網(wǎng)絡(luò)連通度變化曲線

由圖6可以看出，隨著攻擊車站比例f增加，隨機(jī)攻擊時(shí)，網(wǎng)絡(luò)連通度下降最為緩慢，蓄意攻擊策略下，網(wǎng)絡(luò)連通度下降幅度最大。當(dāng)攻擊比例達(dá)到15%時(shí)，貪心介數(shù)攻擊策略下網(wǎng)絡(luò)連通度下降至0.001、貪心度中心攻擊下降至0.138 8、介數(shù)攻擊下降至0.153 5、介數(shù)攻擊下降至0.288 9、度中心性攻擊下降至0.288 9、隨機(jī)攻擊策略下降至0.796 4。在4種蓄意攻擊策略中，貪心介數(shù)中心性策略對(duì)網(wǎng)絡(luò)連通度的影響最大，說(shuō)明關(guān)鍵車站的識(shí)別精度更準(zhǔn)確。

4 結(jié)語(yǔ)

為挖掘地鐵-公交復(fù)合網(wǎng)絡(luò)中的關(guān)鍵車站并提高網(wǎng)絡(luò)魯棒性，采用Space L方法，建立了地鐵-公交復(fù)合網(wǎng)絡(luò)模型，提出了基于貪心介數(shù)的地鐵-公交復(fù)合網(wǎng)絡(luò)關(guān)鍵車站識(shí)別算法。以成都市地鐵-公交復(fù)合網(wǎng)絡(luò)為例，分析表明網(wǎng)絡(luò)具有無(wú)標(biāo)度和小世界特性，在多種攻擊策略中，貪心介數(shù)蓄意攻擊對(duì)網(wǎng)絡(luò)性能影響最大，表明本文提出的關(guān)鍵車站識(shí)別算法具有較高的精度。

文中主要分析地鐵-公交無(wú)權(quán)復(fù)合網(wǎng)絡(luò)的性能，未考慮車站的不同類型對(duì)網(wǎng)絡(luò)的影響，因此，建立加權(quán)網(wǎng)絡(luò)模型并分析網(wǎng)絡(luò)特征將是今后需進(jìn)一步研究的重點(diǎn)。