考慮節(jié)點相互影響的公交網(wǎng)絡(luò)節(jié)點重要性識別算法

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

（1.交科院技術(shù)咨詢（北京）有限公司，北京 100029；2.交通運(yùn)輸部科學(xué)研究院，北京 100029）

0 引言

《國務(wù)院關(guān)于印發(fā)“十四五”現(xiàn)代綜合交通運(yùn)輸體系發(fā)展規(guī)劃的通知》（國發(fā)〔2021〕27號）[1]指出，要提高交通網(wǎng)絡(luò)抗風(fēng)險能力，增強(qiáng)交通運(yùn)輸網(wǎng)絡(luò)韌性。其中，城市公交網(wǎng)絡(luò)的抗風(fēng)險性、可靠性是兩個重要方面。在城市公交網(wǎng)絡(luò)中，重要公交站點對維持網(wǎng)絡(luò)的結(jié)構(gòu)完善和功能正常運(yùn)轉(zhuǎn)有著重要的作用，因此準(zhǔn)確識別公交網(wǎng)絡(luò)的重要站點，進(jìn)而采取適當(dāng)?shù)墓芸卮胧﹥?yōu)化站點的通行條件和服務(wù)能力，對增強(qiáng)城市公交網(wǎng)絡(luò)穩(wěn)定性，保障公交安全高效運(yùn)營具有重要意義。

重要節(jié)點是指對網(wǎng)絡(luò)結(jié)構(gòu)或功能具有較大影響的節(jié)點，識別復(fù)雜網(wǎng)絡(luò)重要節(jié)點是當(dāng)前的研究熱點。經(jīng)典的節(jié)點重要性算法有度中心性[2]、半局部中心性[3]、介數(shù)中心性[4]、緊密度中心性[5]、k-殼分解法[6]等。有些學(xué)者在此基礎(chǔ)上進(jìn)行了優(yōu)化，如王清晨[7]、任卓明等[8]、阮逸潤等[9]、胡鋼等[10]、Xu 等[11]、朱敬成等[12]用度、集聚系數(shù)、拓?fù)渲睾隙鹊韧負(fù)涮匦悦枋龉?jié)點和鄰居節(jié)點間的聯(lián)系，提出各自的節(jié)點重要性算法，但只考慮了網(wǎng)絡(luò)的局部結(jié)構(gòu)。部分學(xué)者提出的算法綜合考慮了網(wǎng)絡(luò)的局部結(jié)構(gòu)和全局結(jié)構(gòu)，對重要節(jié)點的識別具有不錯的效果，如Yang 等[13]、Li 等[14]結(jié)合鄰居節(jié)點信息和路徑信息，分別提出基于重力中心性的k 殼算法（K-shell Based on Gravity Centrality,KSGC）、基于度和k 殼的重力模型算法（DKBased Gravity Model,DKGM）算法；盧鵬麗等[15]結(jié)合節(jié)點的介數(shù)中心性和鄰居節(jié)點的度中心性，提出用介度熵來衡量節(jié)點重要性；Ullah 等[16]提出考慮節(jié)點自身影響和全局影響的全局結(jié)構(gòu)模型（Global Structure Model,GSM）算法；劉書磊等[17]和周漩等[18]考慮了邊對節(jié)點的影響，但僅關(guān)注邊的局部信息，未考慮邊對網(wǎng)絡(luò)全局的影響。

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

1 復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論

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

復(fù)雜網(wǎng)絡(luò)的數(shù)學(xué)表現(xiàn)形式為節(jié)點構(gòu)成的集合V和連邊構(gòu)成的集合E組成的圖G=(V,E)，網(wǎng)絡(luò)節(jié)點數(shù)量N=|V|，連邊數(shù)量M=|E|。

1.1 重要節(jié)點識別方法

1.1.1 節(jié)點度和度中心性

節(jié)點度ki表示與節(jié)點i直接連通的節(jié)點的數(shù)量，即網(wǎng)絡(luò)中以節(jié)點i為端點的邊的數(shù)量[2]，其計算公式為：

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

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

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

式（2）中：N為網(wǎng)絡(luò)中節(jié)點的數(shù)量。

度中心性是最早用于識別重要節(jié)點的算法，具有計算速度較快、應(yīng)用范圍較廣的優(yōu)勢，但其僅關(guān)注網(wǎng)絡(luò)的局部特征，具有較大的片面性。

1.1.2 節(jié)點介數(shù)和介數(shù)中心性

介數(shù)Bi表示網(wǎng)絡(luò)中經(jīng)過節(jié)點i的最短路徑的數(shù)量與網(wǎng)絡(luò)中所有最短路徑數(shù)量總和的比值[4]，其計算公式為：

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

介數(shù)中心性B(i)認(rèn)為網(wǎng)絡(luò)中所有節(jié)點對的最短路徑中經(jīng)過節(jié)點i的次數(shù)越多，節(jié)點越重要[4]。對無向網(wǎng)絡(luò)來說，B(i)計算公式為：

介數(shù)中心性考慮了節(jié)點之間的最短路徑，節(jié)點介數(shù)越高，表明途經(jīng)該節(jié)點的最短路徑越多、節(jié)點的重要性越高，是容易造成網(wǎng)絡(luò)擁堵的瓶頸點。

1.2 網(wǎng)絡(luò)建模方法

復(fù)雜網(wǎng)絡(luò)由節(jié)點和邊組成，網(wǎng)絡(luò)建模是將現(xiàn)實網(wǎng)絡(luò)抽象成適合進(jìn)行復(fù)雜網(wǎng)絡(luò)分析的過程。本文針對公交網(wǎng)絡(luò)進(jìn)行建模，與其他建模方法相比，L空間法更能體現(xiàn)公交網(wǎng)絡(luò)站點與站點之間、站點與線路之間的拓?fù)潢P(guān)系，側(cè)重于公交基礎(chǔ)設(shè)施的連接，反映網(wǎng)絡(luò)自然連接的狀態(tài)，便于分析網(wǎng)絡(luò)最基本的特征和形態(tài)。因此，本文采用L 空間法，將公交網(wǎng)絡(luò)構(gòu)造成由站點和線路構(gòu)成的復(fù)雜網(wǎng)絡(luò)，考慮站點間的連接情況和客流情況，將公交系統(tǒng)中的站點當(dāng)作網(wǎng)絡(luò)節(jié)點，站點間的關(guān)系當(dāng)作節(jié)點的連邊。按照以下原則構(gòu)建無向加權(quán)復(fù)雜公交網(wǎng)絡(luò)。

1）公交停靠站點為網(wǎng)絡(luò)節(jié)點，若兩站點是某條線路中相鄰的停靠站，則兩節(jié)點間有邊相連，否則兩節(jié)點不相連；兩節(jié)點之間至多只能存在一條邊。

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

3）環(huán)形線路以內(nèi)環(huán)線的?？空军c為準(zhǔn)；支線與主線視為兩條線路；上行線路與下行線路走向不一致時，以上行線路的?？空军c為準(zhǔn)。

4）節(jié)點間連邊的權(quán)重為途經(jīng)節(jié)點的客流情況。

2 DeB節(jié)點重要性識別算法

2.1 算法原理

現(xiàn)實公交網(wǎng)絡(luò)中，相鄰的兩個公交站點之間往往相距不遠(yuǎn)，特別是在城市中心區(qū)域，干線和支線公交線路的平均站距一般分別為0.5～0.8 km和0.3～0.5 km[19]，因此經(jīng)常出現(xiàn)乘客在搭乘同方向公交線路時，在不同公交站點上、下車的現(xiàn)象。如圖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 公交出行上下車站點選擇及其出行路徑

站點的距離越近，各條路徑出行時間相差不大的可能性越大，站點間客流的相互影響也越大。該影響力的大小與途經(jīng)站點的線路數(shù)量、發(fā)車間隔、客流大小有關(guān)，也與站點之間的路徑在整個網(wǎng)絡(luò)中的位置有關(guān)。由此，本文認(rèn)為在復(fù)雜公交網(wǎng)絡(luò)中，節(jié)點的重要性不僅與節(jié)點及其鄰居節(jié)點的度值有關(guān)，也與該節(jié)點及其鄰居節(jié)點間的相互影響有關(guān)。鑒于此，本文提出基于節(jié)點度、鄰居節(jié)點度、邊介數(shù)和節(jié)點間客流的DeB 重要節(jié)點識別算法，邊介數(shù)和節(jié)點間客流是連邊的重要屬性，也分別作為網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特征和網(wǎng)絡(luò)運(yùn)營特征，在DeB 算法中表現(xiàn)為節(jié)點連邊對兩端節(jié)點影響力的大小。

同節(jié)點介數(shù)一樣，邊介數(shù)Beij是指網(wǎng)絡(luò)中所有節(jié)點對的最短路徑中經(jīng)過邊eij的數(shù)量占最短路徑總數(shù)的比例[4]，其計算公式為：

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

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

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

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

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

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

2.2 算法有效性評價指標(biāo)

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

1）網(wǎng)絡(luò)效率和累積網(wǎng)絡(luò)效率

網(wǎng)絡(luò)效率E[20]是指網(wǎng)絡(luò)中所有節(jié)點對距離倒數(shù)之和的平均值，計算公式為：

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

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

累積網(wǎng)絡(luò)效率Ec[21]是指節(jié)點移除的過程中，得到的所有網(wǎng)絡(luò)效率之和，其計算公式為：

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

按照不同序列移除節(jié)點所得到的Ec不同，Ec越小表示該序列對網(wǎng)絡(luò)效率的影響越大。

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

最大連通子圖是體現(xiàn)網(wǎng)絡(luò)連通性的度量指標(biāo)，連通圖的最大連通子圖就是其本身，非連通圖的最大連通子圖是指連接節(jié)點數(shù)量最多的連通子圖[22]。節(jié)點移除后，連通圖可能變成非連通圖，并形成多個節(jié)點數(shù)量不同的連通子圖，最大連通子圖的規(guī)模Nmax越大，其最大限度保持正常通行的能力就越強(qiáng)。Nmax計算公式為：

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

2.3 算例分析

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

表1 算例網(wǎng)絡(luò)的重要節(jié)點序列

圖2 算例網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖

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

DeB 算法得到不同階數(shù)的節(jié)點吸引度不同，其節(jié)點重要性排序也不同，當(dāng)階數(shù)n=6 時，節(jié)點9 的吸引度比節(jié)點2 和節(jié)點4 的高，節(jié)點8 與節(jié)點2 和4 的吸引度相接近，這與節(jié)點移除后對網(wǎng)絡(luò)結(jié)構(gòu)和功能的影響表現(xiàn)不一致（見圖3）。因此，為提高DeB 算法對重要節(jié)點識別的準(zhǔn)確性，需針對不同的網(wǎng)絡(luò)確定節(jié)點吸引度最佳階數(shù)。

圖3 移除節(jié)點8或節(jié)點2后算例網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖

3 實證分析

本文以寧波市公交系統(tǒng)為例，按照上文描述的建模方法構(gòu)建無向加權(quán)的復(fù)雜公交網(wǎng)絡(luò)。網(wǎng)絡(luò)包含1 531 個節(jié)點、2 231 條邊，平均節(jié)點度為2.91，平均最短距離為17.06站。

3.1 節(jié)點吸引度最佳階數(shù)

節(jié)點i的n階吸引度，是n-1 階吸引度與節(jié)點通過連邊的邊介數(shù)向其鄰居節(jié)點中吸引而來的吸收值之和。該吸收值與邊介數(shù)、鄰居節(jié)點的n-1 階吸引度有關(guān)，而鄰居節(jié)點的n-1 階吸引度與其鄰居節(jié)點的n-2 階吸引度有關(guān)，由此推之，當(dāng)n達(dá)到一定值時，節(jié)點吸引度將遍歷網(wǎng)絡(luò)中所有節(jié)點。

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

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

圖4 所示為1～9 階吸引度對網(wǎng)絡(luò)效率和最大連通子圖的影響，圖中的橫坐標(biāo)為節(jié)點移除比例，縱坐標(biāo)為節(jié)點移除后的網(wǎng)絡(luò)效率和最大連通子圖規(guī)模。表2 給出了1～9 階吸引度下累積網(wǎng)絡(luò)效率和累積最大連通子圖規(guī)模的數(shù)據(jù)。

表2 1～9階吸引度下累積網(wǎng)絡(luò)效率和累積最大連通子圖規(guī)模數(shù)據(jù)

圖4 1～9階吸引度對網(wǎng)絡(luò)效率和最大連通子圖的影響

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

3.2 DeB算法驗證

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

1）網(wǎng)絡(luò)效率

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

圖5 每次移除0.05N個節(jié)點對網(wǎng)絡(luò)效率的影響

當(dāng)節(jié)點移除比例低于0.2 時，網(wǎng)絡(luò)效率下降速率較快，尤其是移除了前0.05N個節(jié)點時，3種算法的網(wǎng)絡(luò)效率下降幅度均最大。隨著移除比例的增加，網(wǎng)絡(luò)效率的下降幅度變小，體現(xiàn)了重要節(jié)點對網(wǎng)絡(luò)效率的影響比其他節(jié)點大。當(dāng)節(jié)點移除比例達(dá)到0.2N后，3 種算法下的網(wǎng)絡(luò)效率均低于0.1。

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

圖6 每次移除1個節(jié)點直至0.2N個節(jié)點被移除對網(wǎng)絡(luò)效率的影響

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

經(jīng)測算，在節(jié)點移除比例由0.05 增大到1 的過程中，1 階吸引度的累積網(wǎng)絡(luò)效率均比其他兩種算法小，其次是度中心性，最大的是介數(shù)中心性，如表3所示。

表3 不同節(jié)點移除比例對應(yīng)的累積網(wǎng)絡(luò)效率

2）最大連通子圖規(guī)模

與網(wǎng)絡(luò)效率一樣，分別采取兩種蓄意攻擊策略研究移除節(jié)點比例和最大連通子圖規(guī)模之間的關(guān)系，詳見圖7和圖8。

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

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

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

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

表4 不同節(jié)點移除比例對應(yīng)的累積最大連通子圖規(guī)模 單位：個

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

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

3.3 算法性能總結(jié)

綜合來看，相較于度中心性和介數(shù)中心性，1 階吸引度能更準(zhǔn)確地識別網(wǎng)絡(luò)中的重要節(jié)點。DeB 算法獲得的1 階吸引度融合了度中心性算法和介數(shù)中心性算法分別體現(xiàn)出的網(wǎng)絡(luò)局部特征和全局特征，以及客流所體現(xiàn)出的網(wǎng)絡(luò)現(xiàn)實特征，在寧波市公交網(wǎng)絡(luò)重要節(jié)點識別中表現(xiàn)出較好的準(zhǔn)確性。此外，本方法還應(yīng)用于青島市、株洲市等城市，為當(dāng)?shù)毓痪W(wǎng)絡(luò)運(yùn)營提供了有價值的參考，進(jìn)一步驗證了算法的普適性與可移植性。

4 結(jié)束語

準(zhǔn)確識別重要公交站點，采取適當(dāng)措施優(yōu)化重要站點周邊的道路交通條件，對提高公交網(wǎng)絡(luò)運(yùn)營的穩(wěn)定性和韌性具有重要的現(xiàn)實意義。本文聚焦于連邊對重要節(jié)點的影響，采用邊介數(shù)和客流兩項指標(biāo)，從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和網(wǎng)絡(luò)實際運(yùn)行狀態(tài)兩個方面描述連邊對兩端節(jié)點的影響，進(jìn)而提出了DeB 重要節(jié)點識別算法。在此基礎(chǔ)上，通過對寧波市等城市公交網(wǎng)絡(luò)的實證研究，發(fā)現(xiàn)該算法的節(jié)點1 階吸引度能較好地衡量公交站點的重要性。本文研究成果可為公交網(wǎng)絡(luò)運(yùn)營、客流應(yīng)急疏散等提供一定的參考。

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