考慮節點相互影響的公交網絡節點重要性識別算法

鐘志敏，姜仙童，田秀珠，王 昌

（1.交科院技術咨詢（北京）有限公司，北京 100029；2.交通運輸部科學研究院，北京 100029）

0 引言

《國務院關于印發“十四五”現代綜合交通運輸體系發展規劃的通知》（國發〔2021〕27號）[1]指出，要提高交通網絡抗風險能力，增強交通運輸網絡韌性。其中，城市公交網絡的抗風險性、可靠性是兩個重要方面。在城市公交網絡中，重要公交站點對維持網絡的結構完善和功能正常運轉有著重要的作用，因此準確識別公交網絡的重要站點，進而采取適當的管控措施優化站點的通行條件和服務能力，對增強城市公交網絡穩定性，保障公交安全高效運營具有重要意義。

重要節點是指對網絡結構或功能具有較大影響的節點，識別復雜網絡重要節點是當前的研究熱點。經典的節點重要性算法有度中心性[2]、半局部中心性[3]、介數中心性[4]、緊密度中心性[5]、k-殼分解法[6]等。有些學者在此基礎上進行了優化，如王清晨[7]、任卓明等[8]、阮逸潤等[9]、胡鋼等[10]、Xu 等[11]、朱敬成等[12]用度、集聚系數、拓撲重合度等拓撲特性描述節點和鄰居節點間的聯系，提出各自的節點重要性算法，但只考慮了網絡的局部結構。部分學者提出的算法綜合考慮了網絡的局部結構和全局結構，對重要節點的識別具有不錯的效果，如Yang 等[13]、Li 等[14]結合鄰居節點信息和路徑信息，分別提出基于重力中心性的k 殼算法（K-shell Based on Gravity Centrality,KSGC）、基于度和k 殼的重力模型算法（DKBased Gravity Model,DKGM）算法；盧鵬麗等[15]結合節點的介數中心性和鄰居節點的度中心性，提出用介度熵來衡量節點重要性；Ullah 等[16]提出考慮節點自身影響和全局影響的全局結構模型（Global Structure Model,GSM）算法；劉書磊等[17]和周漩等[18]考慮了邊對節點的影響，但僅關注邊的局部信息，未考慮邊對網絡全局的影響。

當前，對節點與鄰居節點互相影響的節點重要性算法研究中，更多地關注網絡的局部結構，較少研究節點連邊對兩端節點的影響，也忽視了網絡的全局特征。同時，研究也更多聚焦在使用SIS/SIR（Susceptible-Infectious-Susceptible/Susceptible-Infectious-Recovered）等網絡模型對各種算法進行效果評估，較少使用真實復雜系統驗證算法有效性，易忽略不同真實復雜系統之間的差異。因此，在考慮網絡局部特征、全局特征和節點間相互影響的節點重要性算法的基礎上，為準確識別公交網絡中的重要站點，以增強網絡的連通性和可靠性，保障乘客順利出行，本文提出一種基于復雜網絡的節點度、鄰居節點度、邊介數和節點間客流的算法——DeB（Degree and edge Betweenness），并以真實的公交網絡為例進行仿真分析，驗證算法性能，以期準確有效地識別公交網絡的重要站點，增強網絡的連通性和韌性，提升網絡的可靠性。

1 復雜網絡基礎理論

近年來，因城鎮化發展和城市規模擴張，城市公交系統規模不斷擴大，逐漸變成一個復雜巨系統，由此引發一系列難題。復雜網絡理論因而被用于城市公交網絡相關研究中。復雜網絡中存在一些特殊的節點被稱為重要節點，其受到攻擊不能正常發揮作用時，整個復雜網絡可能會受到較大的影響，因此節點重要性識別研究是復雜網絡領域的重要研究方向。

復雜網絡的數學表現形式為節點構成的集合V和連邊構成的集合E組成的圖G=(V,E)，網絡節點數量N=|V|，連邊數量M=|E|。

1.1 重要節點識別方法

1.1.1 節點度和度中心性

節點度ki表示與節點i直接連通的節點的數量，即網絡中以節點i為端點的邊的數量[2]，其計算公式為：

式（1）中：eij為節點i與節點j之間的邊。

其中，若節點i與節點j有直接相連的邊，則eij=1，反之eij=0。

度中心性D(i) 認為網絡中與節點相連的節點越多，則該節點在網絡中越重要。節點i的度中心性定義為節點i的度與該節點可能存在最大連邊數量的比值[2]，其計算公式為：

式（2）中：N為網絡中節點的數量。

度中心性是最早用于識別重要節點的算法，具有計算速度較快、應用范圍較廣的優勢，但其僅關注網絡的局部特征，具有較大的片面性。

1.1.2 節點介數和介數中心性

介數Bi表示網絡中經過節點i的最短路徑的數量與網絡中所有最短路徑數量總和的比值[4]，其計算公式為：

式（3）中：njk為節點對j、k間的最短路徑數量；njk(i)為節點對j、k之間的最短路徑中通過節點i的最短路徑數量。

介數中心性B(i)認為網絡中所有節點對的最短路徑中經過節點i的次數越多，節點越重要[4]。對無向網絡來說，B(i)計算公式為：

介數中心性考慮了節點之間的最短路徑，節點介數越高，表明途經該節點的最短路徑越多、節點的重要性越高，是容易造成網絡擁堵的瓶頸點。

1.2 網絡建模方法

復雜網絡由節點和邊組成，網絡建模是將現實網絡抽象成適合進行復雜網絡分析的過程。本文針對公交網絡進行建模，與其他建模方法相比，L空間法更能體現公交網絡站點與站點之間、站點與線路之間的拓撲關系，側重于公交基礎設施的連接，反映網絡自然連接的狀態，便于分析網絡最基本的特征和形態。因此，本文采用L 空間法，將公交網絡構造成由站點和線路構成的復雜網絡，考慮站點間的連接情況和客流情況，將公交系統中的站點當作網絡節點，站點間的關系當作節點的連邊。按照以下原則構建無向加權復雜公交網絡。

1）公交?？空军c為網絡節點，若兩站點是某條線路中相鄰的?？空?，則兩節點間有邊相連，否則兩節點不相連；兩節點之間至多只能存在一條邊。

2）名稱相同的站點視為同一節點，若站點有多個分站，也視為同一節點；名稱不同的兩個站點即使距離很近，也視為不同節點。

3）環形線路以內環線的?？空军c為準；支線與主線視為兩條線路；上行線路與下行線路走向不一致時，以上行線路的?？空军c為準。

4）節點間連邊的權重為途經節點的客流情況。

2 DeB節點重要性識別算法

2.1 算法原理

現實公交網絡中，相鄰的兩個公交站點之間往往相距不遠，特別是在城市中心區域，干線和支線公交線路的平均站距一般分別為0.5～0.8 km和0.3～0.5 km[19]，因此經常出現乘客在搭乘同方向公交線路時，在不同公交站點上、下車的現象。如圖1 所示，出行起點S 到公交站點A 和B、出行終點T 到公交站點C 和D 的距離相差很少，因此從出行起點S到出行終點T之間可能存在4條出行路徑，即S→A→C→T、S→B→C→T、S→A→D→T、S→B→D→T。

圖1 公交出行上下車站點選擇及其出行路徑

站點的距離越近，各條路徑出行時間相差不大的可能性越大，站點間客流的相互影響也越大。該影響力的大小與途經站點的線路數量、發車間隔、客流大小有關，也與站點之間的路徑在整個網絡中的位置有關。由此，本文認為在復雜公交網絡中，節點的重要性不僅與節點及其鄰居節點的度值有關，也與該節點及其鄰居節點間的相互影響有關。鑒于此，本文提出基于節點度、鄰居節點度、邊介數和節點間客流的DeB 重要節點識別算法，邊介數和節點間客流是連邊的重要屬性，也分別作為網絡拓撲結構特征和網絡運營特征，在DeB 算法中表現為節點連邊對兩端節點影響力的大小。

同節點介數一樣，邊介數Beij是指網絡中所有節點對的最短路徑中經過邊eij的數量占最短路徑總數的比例[4]，其計算公式為：

式（5）中：nkl為節點對k,l間最短路徑的數量；nkl(ij)為節點對k,l間最短路徑中通過邊eij的最短路徑數量。

由邊介數的定義可知，Beij越大，表示途經邊eij的最短路徑越多，邊eij兩端的節點i和節點j相互之間的影響越大。

為描述DeB 算法下節點的重要性，引入節點吸引度Ai指標，定義節點i的吸引度Ai為節點i向其鄰居節點吸收的度值與其自身度值之和。吸引度Ai計算公式為：

式（6）中：Γi為節點i的鄰居節點集合；pij為途經節點對i、j間的客流。

更進一步，考慮到鄰居節點對其鄰居節點也會產生吸引，因此定義節點i的n階吸引度為節點向其鄰居節點吸收n次之后的節點重要性指標，其計算公式為：

式（7）中：n≥1，且=ki，即節點i的0 階吸引度等于其節點度。

2.2 算法有效性評價指標

通過節點重要性算法獲得節點重要性序列后，需進一步驗證算法的有效性。驗證方法是：按節點重要性排序在所獲得的節點序列中依次移除節點，即基于節點重要性算法的蓄意攻擊，觀察節點移除過程中網絡結構和功能的變化情況。網絡效率和最大連通子圖是常用的評價網絡結構或功能的指標。在公交網絡中，網絡效率表現為乘客通過公交出行到達網絡中其他節點的難易程度，即網絡效率越高，乘客公交出行越方便；最大連通子圖表現為乘客通過公交出行可到達網絡中其他節點的能力，即最大連通子圖越大，乘客可到達目的地的概率越大。

1）網絡效率和累積網絡效率

網絡效率E[20]是指網絡中所有節點對距離倒數之和的平均值，計算公式為：

式（8）中：dij為節點對i、j間的最短距離。

其中，若節點對i、j之間不存在最短路徑，則1/dij=0。對于加權網絡，式（8）中的dij可替換為邊權wij，即考慮了邊權wij的網絡效率。

累積網絡效率Ec[21]是指節點移除的過程中，得到的所有網絡效率之和，其計算公式為：

式（9）中：m為已移除的節點的集合。

按照不同序列移除節點所得到的Ec不同，Ec越小表示該序列對網絡效率的影響越大。

2）最大連通子圖和累積最大連通子圖

最大連通子圖是體現網絡連通性的度量指標，連通圖的最大連通子圖就是其本身，非連通圖的最大連通子圖是指連接節點數量最多的連通子圖[22]。節點移除后，連通圖可能變成非連通圖，并形成多個節點數量不同的連通子圖，最大連通子圖的規模Nmax越大，其最大限度保持正常通行的能力就越強。Nmax計算公式為：

式（10）中：Nmax為最大連通子圖規模，即最大連通子圖包含的節點數量；N1,N2,N3…為各連通子圖包含的節點數目。

2.3 算例分析

為驗證DeB 算法的有效性，本節以圖2 所示的算例網絡為例，研究分析DeB 算法與度中心性、介數中心性兩種算法在節點刪除時網絡結構和功能的變化。假設圖2中節點間客流均為1，即算例網絡為無權網絡。因算例網絡的直徑為6，故將DeB 算法得到的1 階吸引度、2 階吸引度和6階吸引度與度中心性、介數中心性相比較，重要節點序列如表1所示。

表1 算例網絡的重要節點序列

圖2 算例網絡拓撲結構圖

由圖2 和表1 可知，節點6、7 是“橋節點”，只要移除其中一個，網絡將變成非連通圖。介數中心性認為節點6、7是最重要的節點，介數均為0.56，DeB 算法認為節點6 的重要性較節點7 更高，這符合節點6 的一側較節點7 連接了更多的節點，重要性應較節點7更高的現象；節點2、3、4、5 的度中心性均為0.44，節點8、10 的度中心性均為0.11，但節點3、5 更靠近網絡的中心位置，因此其介數中心性更高，在DeB 算法中，其吸引度也比節點2、4、10 更高；節點1、9 的度中心性均為0.22，但節點9 是到達節點10的必經之路，其各階吸引度也都比節點1的更高。由此可知，當網絡為無權網絡時，采用吸引度衡量節點重要性的DeB算法可有效識別出重要節點。

DeB 算法得到不同階數的節點吸引度不同，其節點重要性排序也不同，當階數n=6 時，節點9 的吸引度比節點2 和節點4 的高，節點8 與節點2 和4 的吸引度相接近，這與節點移除后對網絡結構和功能的影響表現不一致（見圖3）。因此，為提高DeB 算法對重要節點識別的準確性，需針對不同的網絡確定節點吸引度最佳階數。

圖3 移除節點8或節點2后算例網絡拓撲結構圖

3 實證分析

本文以寧波市公交系統為例，按照上文描述的建模方法構建無向加權的復雜公交網絡。網絡包含1 531 個節點、2 231 條邊，平均節點度為2.91，平均最短距離為17.06站。

3.1 節點吸引度最佳階數

節點i的n階吸引度，是n-1 階吸引度與節點通過連邊的邊介數向其鄰居節點中吸引而來的吸收值之和。該吸收值與邊介數、鄰居節點的n-1 階吸引度有關，而鄰居節點的n-1 階吸引度與其鄰居節點的n-2 階吸引度有關，由此推之，當n達到一定值時，節點吸引度將遍歷網絡中所有節點。

由本文第2 節的研究可知，節點吸引度的階數將影響DeB 算法的有效性，考慮到本文研究的寧波市公交網絡的平均最短距離為17.06 站，故本文的研究對象為節點的1～9階吸引度。

本文通過對公交網絡進行模擬蓄意攻擊，觀察網絡效率和最大連通子圖的變化情況以確定最佳吸引度階數。公交網絡的節點數量較大，若逐一移除節點，數據處理時間會較長，因此采取每次移除0.05N個節點數量，即前19 次每次移除77個節點，最后1次移除68個節點，分20次將節點完全移除的蓄意攻擊策略。

圖4 所示為1～9 階吸引度對網絡效率和最大連通子圖的影響，圖中的橫坐標為節點移除比例，縱坐標為節點移除后的網絡效率和最大連通子圖規模。表2 給出了1～9 階吸引度下累積網絡效率和累積最大連通子圖規模的數據。

表2 1～9階吸引度下累積網絡效率和累積最大連通子圖規模數據

圖4 1～9階吸引度對網絡效率和最大連通子圖的影響

由圖4 可知，不管是網絡效率還是最大連通子圖規模，1 階吸引度的曲線在大部分時間內處于圖的最下方，表2 中1 階吸引度的累積網絡效率和累積最大連通子圖規模也低于其余階數吸引度，且累積網絡效率和累積最大連通子圖規模隨節點吸引度階數的增加而呈上升趨勢。換言之，與其他階數的吸引度相比，1 階吸引度能更好地衡量公交復雜網絡節點的重要性。

3.2 DeB算法驗證

由于DeB 算法獲得的1 階吸引度對重要節點識別的準確性最高，因此研究比較網絡效率和最大連通子圖規模在基于1 階吸引度、度中心性、介數中心性三種蓄意攻擊策略下的變化情況，以驗證DeB算法的準確性。

1）網絡效率

采取每次移除0.05N個節點，直至全部節點被移除的蓄意攻擊策略，移除節點的比例和網絡效率之間的關系如圖5 所示。在1 階吸引度、度中心性、介數中心性3種蓄意攻擊策略下，1階吸引度的網絡效率下降最快，介數中心性下降相對緩和，度中心性介于二者之間。

圖5 每次移除0.05N個節點對網絡效率的影響

當節點移除比例低于0.2 時，網絡效率下降速率較快，尤其是移除了前0.05N個節點時，3種算法的網絡效率下降幅度均最大。隨著移除比例的增加，網絡效率的下降幅度變小，體現了重要節點對網絡效率的影響比其他節點大。當節點移除比例達到0.2N后，3 種算法下的網絡效率均低于0.1。

為進一步分析重要節點對網絡效率的影響，本文還采取了第2種蓄意攻擊策略，即每次移除1個節點，直至0.2N個節點被移除。該種攻擊策略下，網絡效率的變化情況如圖6所示。

圖6 每次移除1個節點直至0.2N個節點被移除對網絡效率的影響

由圖6 可知，移除前2 個節點時，介數中心性的網絡效率下降最快，然后1 階吸引度的網絡效率下降幅度超過了介數中心性，之后在部分區域與度中心性的網絡效率下降幅度相差不大，但是多數情況下1階吸引度的曲線處于圖的最下方，網絡效率下降幅度最大。

經測算，在節點移除比例由0.05 增大到1 的過程中，1 階吸引度的累積網絡效率均比其他兩種算法小，其次是度中心性，最大的是介數中心性，如表3所示。

表3 不同節點移除比例對應的累積網絡效率

2）最大連通子圖規模

與網絡效率一樣，分別采取兩種蓄意攻擊策略研究移除節點比例和最大連通子圖規模之間的關系，詳見圖7和圖8。

圖7 每次移除0.05N個節點直至節點全部移除對最大連通子圖規模的影響

圖8 每次移除1個節點直至0.2N個節點被移除對最大連通子圖規模的影響

由圖7 和圖8 可以看出，與移除節點對網絡效率的影響一致，大多數情況下1 階吸引度的曲線都處于圖的最下方，即其最大連通子圖規模變化最大，網絡的連通性最差。其中，圖8 中3 種算法均呈現最大連通子圖規模緩慢下降和突然下降交替出現的現象，即多數情況下，每移除1 個節點，最大連通子圖規模相應地減少1 個，曲線下降較為緩慢，直至被移除的節點累積到一定的數量時，最大連通子圖的規模出現斷崖式下降，隨后又恢復成緩慢下降的狀態。移除的節點重要性越高，最大連通子圖出現斷崖式下降的頻率也越快，體現了重要節點對最大連通子圖的影響更大，少部分重要節點的移除會對網絡的連通性產生嚴重的影響。

經測算，在節點移除比例由0.05 增大到1 的過程中，1 階吸引度的累積最大連通子圖規模均比其他兩種算法小，其次是度中心性，最大的是介數中心性（見表4），這與節點移除對網絡效率的影響相似。

表4 不同節點移除比例對應的累積最大連通子圖規模 單位：個

以寧波市公交系統排名靠前的節點為例，進一步比較分析節點1 階吸引度與度中心性和介數中心性對重要節點的識別情況，表5 僅列舉了3種節點重要性識別算法獲取的重要性排名前20的節點情況。研究結果表明，節點1 階吸引度是在度中心性基礎上進行優化，因此其得到的節點重要性排序與度中心性的相似度最高，前20個節點中有13個相同的節點，但是排序大不相同，且距離越靠后，排序的差別越大。不同的7個節點中，寧大附屬醫院、紅梅新村、鎮海公交、白沙路、外灘等5 個站點位于介數中心性前20，孔浦中學位于介數中心性的第31，陸家村分別位于度中心性和介數中心性的第25和53。這也說明DeB算法所獲得的1 階吸引度融合了度中心性算法和介數中心性算法二者的特性，實現了二者的優勢互補，可以識別出度中心性和介數中心性各自所忽視的部分節點的重要性。

表5 3種算法識別的重要性前20節點對比

3.3 算法性能總結

綜合來看，相較于度中心性和介數中心性，1 階吸引度能更準確地識別網絡中的重要節點。DeB 算法獲得的1 階吸引度融合了度中心性算法和介數中心性算法分別體現出的網絡局部特征和全局特征，以及客流所體現出的網絡現實特征，在寧波市公交網絡重要節點識別中表現出較好的準確性。此外，本方法還應用于青島市、株洲市等城市，為當地公交網絡運營提供了有價值的參考，進一步驗證了算法的普適性與可移植性。

4 結束語

準確識別重要公交站點，采取適當措施優化重要站點周邊的道路交通條件，對提高公交網絡運營的穩定性和韌性具有重要的現實意義。本文聚焦于連邊對重要節點的影響，采用邊介數和客流兩項指標，從網絡拓撲結構和網絡實際運行狀態兩個方面描述連邊對兩端節點的影響，進而提出了DeB 重要節點識別算法。在此基礎上，通過對寧波市等城市公交網絡的實證研究，發現該算法的節點1 階吸引度能較好地衡量公交站點的重要性。本文研究成果可為公交網絡運營、客流應急疏散等提供一定的參考。

本文是基于無向加權公交網絡的研究，僅考慮了公交網絡客流對重要節點的影響，對真實公交網絡的刻畫精確度有待提升。下一步，將根據公交發車間隔、公交運行里程和時間、乘客換乘情況等實際運營情況構建更加真實的公交網絡。此外，也可從不同時段、不同運營狀態的公交網絡重要節點入手，研究重要節點的演化過程，為優化城市公交線網布局、提高公交出行效率、提升公交網絡抗風險能力提供技術支撐。