基于貪心介數的地鐵-公交復合網絡關鍵車站識別算法

汪 軍,夏永躍,王運明,李衛東

(大連交通大學自動化與電氣工程學院,大連 116028)

引言

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

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

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

1 地鐵-公交復合網絡模型

為準確描述地鐵-公交復合交通網絡的相互關系，采用復雜網絡理論建立地鐵-公交復合網絡模型。交通網絡主要有Space L和Space P兩種建模方法。Space L方法將車站抽象為節點，若兩個車站地理位置相鄰并有同一個車次通過，則節點之間有連邊；Space P方法也將車站抽象為節點，若車站之間有直達的車次，則節點之間有連邊。

地鐵-公交復合交通網絡是由不同的車站和線路構成的復雜網絡，采用Space L方法構建網絡模型，將地鐵-公交復合網絡分為層內網絡和層間網絡，其中層內網絡為公交和地鐵兩個獨立的復雜網絡，層間網絡為地鐵網絡和公交網絡的車站之間存在耦合關系而形成的網絡。地鐵-公交復合網絡表示為GB-S={GB，GS，RB-S}。

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

在城市規劃建設中，為增強城市交通系統的運輸效率和運輸范圍，一般1個地鐵車站周圍會設置多個公交車站，形成一對多的耦合關系，即?si∈VS，?bj∈VB，使得si→bj。設矩陣R為層間網絡的耦合矩陣，矩陣元素rij表示節點si和bj之間的耦合關系，則R=[rij]NP×NF，其中si→bj時，rij=1；否則rij=0。

城市地鐵-公交復合網絡進一步表示為GB-S。其中，V表示地鐵-公交復合網絡的節點集合，V=VB∪VS；E表示地鐵-公交復合網絡的邊集合，E=EB∪ES∪ER，ER表示地鐵網絡GS和公交網絡GB之間存在的耦合邊集合。

地鐵-公交復合網絡的拓撲結構如圖1所示，上層為公交網絡，下層為地鐵網絡，兩層之間的連接為層間耦合關系。地鐵網絡的車站S2周圍存在3個公交車站B1、B2、B3，乘客步行就可到達并換乘(限定200 m)，兩者建立層間耦合關系s2→(b1，b2，b3)。

圖1 地鐵-公交復合網絡的拓撲結構

2 基于貪心介數的復合網絡關鍵車站識別算法

2.1 貪心策略

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

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

(2)初始化一個空集L=?，將重要度最大的節點記錄于集合L，并從網絡中刪除該節點，此時，最大連通分支記為CV；

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

(4)調用Warshall算法判斷是否存在連通子圖，若存在，重復步驟(3)，直至網絡不存在連通子圖，或網絡剩余節點都成為孤立節點，貪心策略結束。

貪心算法具有較高的魯棒性，算法在解決影響力最大化問題中準確率最低也可以達到63%。但是，較高的準確率帶來的卻是非常高的時間復雜度，在小規模的網絡中，貪心算法可以發揮出其優異的性能，但對于規模較大的網絡，算法的時間復雜度過高。

2.2 介數中心性

介數中心性表示網絡中節點間最短路徑經過某節點的數目，是刻畫節點網絡結構特征的重要指標之一。節點介數中心性越大，網絡中經過該節點的最短路徑條數越多，說明節點對網絡的信息傳播或流通控制能力越強，該節點在網絡中也就越重要。定義為

(1)

2.3 基于貪心介數的關鍵車站識別算法

為提高關鍵車站的識別精度，考慮刪除某些重要車站后，剩余車站的重要度排序發生動態變化的特點，引入貪心算法，提出基于貪心介數的地鐵-公交復合網絡關鍵車站識別算法。

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

算法的具體過程描述如下：

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

(2)計算當前網絡各節點的介數值，介數最大節點序號記錄到重要度序列L=L∪{i}；

(3)刪除網絡中介數最大的節點i，刪除后網絡中的孤立節點記錄到集合CS中；

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

3 仿真分析

為驗證本文提出的地鐵-公交復合網絡關鍵車站識別算法的可行性和有效性，根據百度地圖網站提供的成都市市區地鐵-公交復合網絡數據，利用復雜網絡理論，將公交、地鐵的車站抽象為節點，車站之間的連接關系抽象為邊，建立成都市地鐵-公交復合網絡模型。考慮部分近鄰公交站點的重復性，合并處理相距100 m的重名站點，限定地鐵車站周邊200 m范圍內的公交站點為有效站點，與地鐵車站建立連邊。該網絡包含886個公交車站的162條公交線路和只考慮市區范圍內42個地鐵車站的5條地鐵線路。利用Gephi軟件建立的成都市地鐵-公交復合網絡拓撲結構如圖2所示。

圖2 成都市地鐵-公交復合網絡拓撲結構

成都市地鐵-公交復合網絡與獨立網絡的各類特征指標對比結果如表1所示。地鐵-公交復合網絡的平均度4.287最高，說明復合網絡中任意車站的鄰接車站數高于地鐵和公交網絡。因所選取地鐵網絡數據中有5個換乘車站，10個邊緣站點，所以地鐵平均度為2，地鐵網絡的平均聚集系數為0。因為任意一個地鐵車站的鄰接車站并不會通過地鐵線路再相互連接，只能通過地面公交中轉，地鐵和公交相互銜接、配合可有效提高出行效率。復合網絡的平均路徑長度7.237小于公交網絡9.188，說明復合網絡中客流從一個車站到另一車站出行的平均距離比單獨使用公交出行要小。交通網絡中度值大于2的站點一般為換乘車站，起到樞紐作用，聚集系數超過0.05，表明此車站應是居住型、商業、旅游景點等人群密集型車站，其中復合網絡聚集系數為0.216遠高于地鐵、公交網絡，具有很強的聚集特性。通過對網絡拓撲特性的分析，表明地鐵-公交復合網絡具備無標度和小世界特性。

表1 成都市地鐵-公交復合網絡拓撲靜態指標

最大連通子圖、網絡效率、圈數率、連通度等指標是衡量復雜網絡中關鍵節點識別精度重要指標[19-20]，因此，本文采用這些指標評價基于貪心介數的地鐵-公交復合網絡關鍵節點識別算法的優勢。運用軟件Matlab進行仿真分析。

地鐵-公交復合交通網絡中存在大量度為2的節點，攻擊此類節點易形成獨立子集團，使得最大連通子圖能夠很好地評估關鍵節點識別的精度。網絡的最大連通子圖比例定義為網絡的最大連通子圖節點數與網絡總節點數的比值，反映被刪除節點對網絡結構的影響。如果被刪除的是邊緣節點，則最大連通子圖的節點個數依然接近網絡初始節點數；如果被刪除的節點是關鍵節點，網絡會被劃分成多個子網，新的最大連通子圖節點個數較少。為增強最大連通子圖的區分度，提出最大連通子圖相對大小的概念，定義為

(2)

式中，n為最大連通子圖的節點數；N為初始網絡節點數；f為移除節點的比例。

采用不同策略刪除網絡中節點對最大連通子圖相對大小的影響，如圖3所示。

圖3 最大連通子圖相對大小變化曲線

從圖3可知，隨著攻擊車站比例f的增加，地鐵-公交復合網絡最大連通子圖逐漸下降。當攻擊比例達到15%時，隨機攻擊時，最大連通子圖相對大小曲線下降為0.813 9，速度最為緩慢；蓄意攻擊時，最大連通子圖相對大小曲線均快速下降，表明攻擊關鍵節點對網絡結構魯棒性產生較大影響。其中，攻擊貪心介數算法識別出的關鍵節點時，最大連通子圖相對大小曲線下降至0.031 25，下降最快；其次是貪心度中心攻擊下降至0.393 3、介數攻擊下降至0.575 4、度中心攻擊下降至0.813 9。說明貪心介數算法識別地鐵-公交復合網絡的關鍵節點準確率最高。

網絡效率一般定義為所有節點對之間效率的平均值，能夠從全局性的角度分析網絡效率對網絡性能的影響，表示為

(3)

式中，N為網絡的節點數量；dij為節點i和j之間的最短路徑長度。

采用不同策略刪除網絡中節點對網絡效率的影響如圖4所示。

圖4 網絡效率變化曲線

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

圈數描述了城市公共交通網絡的可替代路徑的提供能力。城市公共交通網絡規模逐漸擴大后，圈數相應增加，但網絡規模越大并不代表網絡的魯棒性越強。采用圈數率反映地鐵-公交復合網絡的魯棒性，表示為

(4)

式中，圈數μ=|D|-|Vd|+1；D為網絡的邊數；Vd為網絡的節點數目。

采用不同策略刪除網絡中節點對圈數率的影響如圖5所示。

圖5 網絡圈數率變化曲線

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

網絡連通度是網絡實際邊數目與理論最大邊數目的比值。與聚集系數的區別在于連通度是面向整個網絡，而不是網絡中某個節點的域。連通度的計算公式如下

(5)

式中，D為城市公共交通拓撲網絡的邊數；Vd為城市公共交通網絡的節點數目。

采用不同策略刪除網絡中節點對網絡連通度的影響如圖6所示。

圖6 網絡連通度變化曲線

由圖6可以看出，隨著攻擊車站比例f增加，隨機攻擊時，網絡連通度下降最為緩慢，蓄意攻擊策略下，網絡連通度下降幅度最大。當攻擊比例達到15%時，貪心介數攻擊策略下網絡連通度下降至0.001、貪心度中心攻擊下降至0.138 8、介數攻擊下降至0.153 5、介數攻擊下降至0.288 9、度中心性攻擊下降至0.288 9、隨機攻擊策略下降至0.796 4。在4種蓄意攻擊策略中，貪心介數中心性策略對網絡連通度的影響最大，說明關鍵車站的識別精度更準確。

4 結語

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

文中主要分析地鐵-公交無權復合網絡的性能，未考慮車站的不同類型對網絡的影響，因此，建立加權網絡模型并分析網絡特征將是今后需進一步研究的重點。