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

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

0 引言

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

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

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

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

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

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

1.1 重要節(jié)點(diǎn)識(shí)別方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3）環(huán)形線路以內(nèi)環(huán)線的停靠站點(diǎn)為準(zhǔn)；支線與主線視為兩條線路；上行線路與下行線路走向不一致時(shí)，以上行線路的停靠站點(diǎn)為準(zhǔn)。

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

2 DeB節(jié)點(diǎn)重要性識(shí)別算法

2.1 算法原理

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

圖1 公交出行上下車(chē)站點(diǎn)選擇及其出行路徑

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

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

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

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

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

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

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

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

2.2 算法有效性評(píng)價(jià)指標(biāo)

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

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

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

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

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

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

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

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

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

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

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

2.3 算例分析

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

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

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

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

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

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

3 實(shí)證分析

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

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

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

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

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

圖4 所示為1～9 階吸引度對(duì)網(wǎng)絡(luò)效率和最大連通子圖的影響，圖中的橫坐標(biāo)為節(jié)點(diǎn)移除比例，縱坐標(biāo)為節(jié)點(diǎn)移除后的網(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階吸引度對(duì)網(wǎng)絡(luò)效率和最大連通子圖的影響

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

3.2 DeB算法驗(yàn)證

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表5 3種算法識(shí)別的重要性前20節(jié)點(diǎn)對(duì)比

3.3 算法性能總結(jié)

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

4 結(jié)束語(yǔ)

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

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