基于改進(jìn)連邊刪除評(píng)估法的關(guān)鍵航路段集合識(shí)別方法*

畢可心，溫祥西，葉澤龍，劉瑜平，王 天

（1.空軍工程大學(xué)空管領(lǐng)航學(xué)院，西安 710051；2.國(guó)家空管防相撞技術(shù)重點(diǎn)實(shí)驗(yàn)室，西安 710051；3.解放軍95178 部隊(duì)，南寧 530031；4.解放軍93220 部隊(duì)，哈爾濱 150046）

0 引言

復(fù)雜網(wǎng)絡(luò)是對(duì)復(fù)雜系統(tǒng)進(jìn)行抽象和具體的主要工具，連邊代表復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)之間的聯(lián)系和相互作用，但這些相互作用對(duì)網(wǎng)絡(luò)整體的影響往往是不同的。想要尋求復(fù)雜系統(tǒng)的本質(zhì)，需要把握住這些系統(tǒng)中重要的聯(lián)系，即對(duì)于網(wǎng)絡(luò)中的關(guān)鍵連邊，需要通過(guò)一定的方法和手段進(jìn)行識(shí)別。國(guó)內(nèi)外學(xué)者在進(jìn)行這方面的研究過(guò)程中主要形成了兩種具有代表性的方法，基于邊介數(shù)的評(píng)估方法和連邊刪除評(píng)估法。前者是從復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)上，對(duì)網(wǎng)絡(luò)連邊的重要性進(jìn)行評(píng)價(jià)，連邊的介數(shù)越高，其在網(wǎng)絡(luò)中的中心程度越高，關(guān)鍵性也越強(qiáng)；后者則是以連邊自身對(duì)網(wǎng)絡(luò)性能的影響來(lái)評(píng)價(jià)其對(duì)于網(wǎng)絡(luò)整體的重要性，計(jì)算移除連邊后引起的網(wǎng)絡(luò)性能變化，變化幅度越大，連邊在網(wǎng)絡(luò)中的重要性就越高。后者的評(píng)估方式對(duì)實(shí)際網(wǎng)絡(luò)而言更有意義。

文獻(xiàn)［4］將連邊刪除評(píng)估法用于進(jìn)行通信網(wǎng)絡(luò)中重要鏈路的識(shí)別和保護(hù)；文獻(xiàn)［5］將其用于研究城市群復(fù)合交通網(wǎng)絡(luò)脆弱性，文獻(xiàn)［6］提出了一種單條航路失效，利用級(jí)聯(lián)失效理論確定關(guān)鍵航路的方法，通過(guò)對(duì)關(guān)鍵線路的加強(qiáng)防護(hù)，可以進(jìn)一步降低城市交通和空中交通網(wǎng)絡(luò)的脆弱性，減小交通大范圍癱瘓的風(fēng)險(xiǎn)。文獻(xiàn)［7］依據(jù)連邊刪除評(píng)估法，提出了基于最小連通支配集的復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)與連邊集合識(shí)別方法，可以同時(shí)對(duì)復(fù)雜網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)和連邊進(jìn)行識(shí)別；文獻(xiàn)［8］用連邊刪除評(píng)估法進(jìn)行網(wǎng)絡(luò)魯棒性的評(píng)估；文獻(xiàn)［9］將連邊刪除評(píng)估法用于網(wǎng)絡(luò)中社團(tuán)的區(qū)分。以上方法雖然通過(guò)連邊刪除法識(shí)別出了網(wǎng)絡(luò)中的關(guān)鍵連邊，但其普遍沒(méi)能避免傳統(tǒng)連邊刪除評(píng)估方法在識(shí)別關(guān)鍵連邊集合時(shí)，識(shí)別結(jié)果靜態(tài)，整體重要性減弱的問(wèn)題。

綜上，本文針對(duì)傳統(tǒng)的連邊刪除評(píng)估法只能識(shí)別出單條連邊的重要性，對(duì)關(guān)鍵連邊集合的識(shí)別不夠準(zhǔn)確的問(wèn)題，以航路網(wǎng)絡(luò)為例，采用“不放回”的方式刪除連邊集合，通過(guò)多屬性決策方法綜合評(píng)估網(wǎng)絡(luò)性能變化幅度，確定改航規(guī)劃中的關(guān)鍵航路段集合，并與傳統(tǒng)的連邊刪除評(píng)估法進(jìn)行對(duì)比。

1 改進(jìn)連邊刪除評(píng)估法

1.1 復(fù)雜網(wǎng)絡(luò)模型

復(fù)雜網(wǎng)絡(luò)模型，通常由節(jié)點(diǎn)、連邊、權(quán)重等要素構(gòu)成，其結(jié)構(gòu)可表示為：={，，}。其中，表示整個(gè)網(wǎng)絡(luò)，表示網(wǎng)絡(luò)中節(jié)點(diǎn)的集合，表示連邊的集合，表示權(quán)重的集合。

在航路網(wǎng)絡(luò)中，網(wǎng)絡(luò)的節(jié)點(diǎn)集={，，…，v}代表民航的機(jī)場(chǎng)、導(dǎo)航臺(tái)等；網(wǎng)絡(luò)中的邊集={，，…，e}表示機(jī)場(chǎng)之間的通行關(guān)系，若兩機(jī)場(chǎng)之間存在固定的航班，則認(rèn)為其對(duì)應(yīng)節(jié)點(diǎn)之間存在連邊；={，，…，w}代表網(wǎng)絡(luò)中的邊權(quán)。

1.2 連邊刪除評(píng)估法

連邊刪除評(píng)估法是用于識(shí)別航路網(wǎng)絡(luò)中關(guān)鍵航路段的基本算法。它通過(guò)評(píng)價(jià)特定連邊在移除之后對(duì)網(wǎng)絡(luò)性能造成的影響，得到此連邊在網(wǎng)絡(luò)中的重要度d。移除連邊后網(wǎng)絡(luò)性能下降幅度越大，則連邊重要度越高。

傳統(tǒng)連邊刪除評(píng)估法采用的是“放回式”的思想，每次只剔除一條連邊后分析剩余連邊網(wǎng)絡(luò)性能變化，再將其放回原網(wǎng)絡(luò)中，以此建立連邊的關(guān)鍵性排序。定義重要度矩陣D（d），d為刪去與的連邊后，網(wǎng)絡(luò)性能的變化值。d為連邊的重要度，R為初始網(wǎng)絡(luò)初始性能。

但由于識(shí)別一組關(guān)鍵的航路段集合，并不是一個(gè)簡(jiǎn)單的靜態(tài)過(guò)程。傳統(tǒng)連邊刪除評(píng)估法忽略了網(wǎng)絡(luò)的動(dòng)態(tài)變化過(guò)程，所得到的關(guān)鍵連邊只是相對(duì)于網(wǎng)絡(luò)的全拓?fù)浣Y(jié)構(gòu)這一狀態(tài)而言的，因此，該方法在用于對(duì)航路網(wǎng)路影響重大的航路段集合進(jìn)行評(píng)估時(shí)，所得結(jié)果并不是最優(yōu)的。

1.3 改進(jìn)流程

本文采用“不放回”的思路對(duì)連邊刪除評(píng)估法進(jìn)行改進(jìn)。假設(shè)航路網(wǎng)絡(luò)中有條連邊，需要識(shí)別出條關(guān)鍵航路段，其具體步驟如圖1 所示。

圖1 改進(jìn)連邊刪除評(píng)估法步驟

Step 1：刪除航路段，基于多屬性決策方法對(duì)航路網(wǎng)絡(luò)性能評(píng)估，計(jì)算得到網(wǎng)絡(luò)性能變化值；

Step 2：將航路段放回網(wǎng)絡(luò)，+1，逐次計(jì)算出全部航路段對(duì)應(yīng)的網(wǎng)絡(luò)性能變化值集合{}；

Step 3：按照關(guān)閉航路后引起航路網(wǎng)絡(luò)性能的變化程度對(duì)航路重要度進(jìn)行排序，得到航路重要度序列{，，，…，e}。值越大，航路e在重要度序列中的排名越靠前；

Step 4：剔除航路重要度序列{，，，…，e}中此時(shí)排序?yàn)榈? 的航路段，得到新的網(wǎng)絡(luò)G。

Step 5：輸入G，=+1，=-1 等新的參數(shù)，跳轉(zhuǎn)回到Step1，重復(fù)Step1～Step4 的操作，直至，滿足終止條件，得到被刪除的關(guān)鍵航路段集合E。

2 網(wǎng)絡(luò)性能評(píng)估

2.1 多屬性決策分析

本文用多屬性決策評(píng)價(jià)方法對(duì)網(wǎng)絡(luò)性能進(jìn)行評(píng)估。網(wǎng)絡(luò)性能評(píng)估的對(duì)象是刪除一組航路后的航路網(wǎng)絡(luò)，可以將其看做一種方案，而航路網(wǎng)絡(luò)的性能評(píng)估指標(biāo)最大連通子圖尺寸SS、網(wǎng)絡(luò)效率等則可以視為方案的屬性。如此，可將網(wǎng)絡(luò)性能評(píng)估問(wèn)題轉(zhuǎn)化為多屬性決策問(wèn)題。

如此，可定義航路網(wǎng)絡(luò)G中的第個(gè)指標(biāo)為G（S）（1，2，…，；1，2，3，4，5），構(gòu)成決策矩陣X：

之后，對(duì)矩陣指標(biāo)進(jìn)行標(biāo)準(zhǔn)化處理：

利用TOPSIS 方法，通過(guò)矩陣Y 可以確定正理想方案，為各可行方案中各指標(biāo)值最大者，即剔除航路段集合后，航路網(wǎng)絡(luò)性能值變化最小的方案：

之后，計(jì)算任一方案G到正理想方案的距離：

D越大，方案G到正理想方案的距離越遠(yuǎn)，也就說(shuō)明移除航路段集合后的網(wǎng)絡(luò)G綜合性能下降越多，即這一航路段集合關(guān)鍵性越強(qiáng)。

2.2 指標(biāo)及其權(quán)重

為了對(duì)網(wǎng)絡(luò)性能進(jìn)行更好地評(píng)估，本文選取5個(gè)性能評(píng)估指標(biāo)，分別從連通性、穩(wěn)定性、負(fù)載能力、網(wǎng)絡(luò)聚集程度對(duì)網(wǎng)絡(luò)性能進(jìn)行評(píng)價(jià)。

1）最大連通子圖尺寸。航路網(wǎng)絡(luò)是用于提供客運(yùn)、貨運(yùn)服務(wù)的運(yùn)輸網(wǎng)絡(luò)，網(wǎng)絡(luò)中的節(jié)點(diǎn)以航路段進(jìn)行連接，節(jié)點(diǎn)只有與其他節(jié)點(diǎn)相互可達(dá)時(shí)，才能在網(wǎng)絡(luò)中發(fā)揮其作用。因此，最大連通子圖尺寸是一個(gè)評(píng)價(jià)網(wǎng)絡(luò)連通性和運(yùn)輸能力的重要指標(biāo)，尺寸是最大連通子圖中節(jié)點(diǎn)的個(gè)數(shù)，越大，網(wǎng)絡(luò)連通性越好。

如圖2 所示，網(wǎng)絡(luò)中共有20 個(gè)節(jié)點(diǎn)，其中節(jié)點(diǎn)3，4，11，16 為孤立點(diǎn)，因此，這個(gè)網(wǎng)絡(luò)不是完全連通的，其最大連通子圖尺寸為16 個(gè)節(jié)點(diǎn)。

圖2 最大連通子圖示意圖

2）網(wǎng)絡(luò)平均最短路徑的倒數(shù)。平均最短路徑的定義是為網(wǎng)絡(luò)中任意兩點(diǎn)之間最短路徑之和占網(wǎng)絡(luò)中可能存在的最多邊數(shù)的比重。取其倒數(shù)來(lái)描述網(wǎng)絡(luò)的脆弱性和抗毀能力，其計(jì)算如公式（8）：

在復(fù)雜網(wǎng)絡(luò)中，越大，平均最短路徑越短，說(shuō)明網(wǎng)絡(luò)中的節(jié)點(diǎn)相互可達(dá)的中轉(zhuǎn)次數(shù)就越少，這意味著航班流量在機(jī)場(chǎng)、導(dǎo)航臺(tái)等節(jié)點(diǎn)運(yùn)行更加暢快，網(wǎng)絡(luò)連通性更好，網(wǎng)絡(luò)風(fēng)險(xiǎn)值也更小，中轉(zhuǎn)成本越低，業(yè)務(wù)往來(lái)更加快捷。

如圖3 中所示，經(jīng)計(jì)算平均最短路徑為2.977 0，值為0.335 9。其中，節(jié)點(diǎn)3 節(jié)點(diǎn)15 的最短路徑最長(zhǎng)，其路徑為“3-4-5-13-28-24-15”。

圖3 平均最短路徑示意圖

3）網(wǎng)絡(luò)平均聚類系數(shù)。單獨(dú)一個(gè)節(jié)點(diǎn)的聚類系數(shù)是用來(lái)描述節(jié)點(diǎn)之間聚集成團(tuán)的程度，整個(gè)網(wǎng)絡(luò)的平均聚類系數(shù)則可以描述全局的聚集程度。單個(gè)節(jié)點(diǎn)的加權(quán)集群系數(shù)的計(jì)算如式（9）所示：

4）網(wǎng)絡(luò)魯棒性。本文以網(wǎng)絡(luò)點(diǎn)權(quán)分布的均勻程度作為網(wǎng)絡(luò)的魯棒性，其計(jì)算如式（10）所示：

5）網(wǎng)絡(luò)負(fù)載能力。本文以航路網(wǎng)絡(luò)中各邊權(quán)值之和為的值。航路網(wǎng)絡(luò)的邊權(quán)值一般取流量或者航路段距離。流量邊權(quán)直觀地用流量衡量了負(fù)載能力。而距離邊權(quán)同樣也可以反映負(fù)載能力，為了保證飛行安全，同條航路上的飛行器通常留有一定飛行間隔，在管制技術(shù)水平相同的條件下，可以認(rèn)為一條航路段上的飛行容量與航路段的長(zhǎng)度成正比。因此，在基于距離邊權(quán)的航路網(wǎng)絡(luò)中，值取網(wǎng)絡(luò)中所有航路段上的航路距離之和，其計(jì)算如式（11）所示：

為了綜合評(píng)估網(wǎng)絡(luò)的性能，需要對(duì)以上5 個(gè)指標(biāo)進(jìn)行加權(quán)處理。本文使用層次分析法（The Analytic Hierarchy Process，AHP）計(jì)算指標(biāo)的權(quán)重。網(wǎng)絡(luò)負(fù)載能力在網(wǎng)絡(luò)整體性能中最重要，最大連通子圖尺寸次之，和的重要性相當(dāng)，魯棒性的重要程度最弱。綜上，5 個(gè)指標(biāo)的重要度排序?yàn)?。通過(guò)AHP 計(jì)算，其權(quán)重向量如下：

3 實(shí)驗(yàn)分析

通過(guò)對(duì)昆明管制區(qū)的機(jī)場(chǎng)、導(dǎo)航臺(tái)、航路信息進(jìn)行搜集與處理，本文建立了62 個(gè)節(jié)點(diǎn)、80 條邊的昆明航路網(wǎng)絡(luò)，其網(wǎng)絡(luò)結(jié)構(gòu)如圖4 所示。以該網(wǎng)絡(luò)為對(duì)象，進(jìn)行關(guān)鍵航路集合的識(shí)別。

圖4 昆明管制區(qū)航路網(wǎng)絡(luò)示意圖

首先使用傳統(tǒng)“放回式”方法對(duì)關(guān)鍵航路進(jìn)行識(shí)別，依次移除各條航路，計(jì)算其移除后引起的網(wǎng)絡(luò)性能變化值，可得到航路重要度排序表如下頁(yè)表1 所示。

表1 傳統(tǒng)識(shí)別方法得到的航路重要度排序

在移除不同數(shù)量的航路段時(shí)，通過(guò)本文提出的改進(jìn)連邊刪除評(píng)估法，移除相應(yīng)的關(guān)鍵航路集合，引起的航路網(wǎng)絡(luò)性能變化如下頁(yè)圖5 中紅色曲線所示。同時(shí)，按照傳統(tǒng)連邊刪除評(píng)估法得到航路重要度排序表，在求取不同航路段數(shù)量的關(guān)鍵航路時(shí)，按重要度剔除相應(yīng)數(shù)量的航路段，其引起的航路網(wǎng)絡(luò)性能變化如圖5 中藍(lán)色曲線所示。

從圖5 中可以看出，改進(jìn)的連邊刪除評(píng)估法識(shí)別出的航路段集合關(guān)鍵性更高，對(duì)網(wǎng)絡(luò)性能的影響更為顯著。這是由于航路網(wǎng)絡(luò)結(jié)構(gòu)的特殊性造成的，在關(guān)鍵航路段數(shù)目為1 時(shí)，兩種方法得到的最關(guān)鍵航路段相同，均為航路段“MEPAN-耿馬VOR（GMA）”，剔除后航路網(wǎng)絡(luò)性能由初始的0.812 0 下降為0.774 6，在識(shí)別單條航路關(guān)鍵性時(shí)，兩種方法的優(yōu)越性一致。但隨著關(guān)鍵航路數(shù)目的增加，關(guān)鍵航路集合識(shí)別方法的優(yōu)越性表現(xiàn)明顯，移除10 條航路段時(shí)，航路網(wǎng)絡(luò)的性能就已經(jīng)下降到了0.289 8，而傳統(tǒng)連邊刪除評(píng)估法的網(wǎng)絡(luò)性能依舊維持在0.620 7，差距明顯。這進(jìn)一步說(shuō)明了傳統(tǒng)算法對(duì)關(guān)鍵航路的識(shí)別是靜態(tài)的，它所識(shí)別出的是單條航路段自身對(duì)整個(gè)網(wǎng)絡(luò)的影響程度，以此得到的關(guān)鍵性排序?qū)嶋H是靜態(tài)的，隨著所尋找的航路段數(shù)目的增加，一些自身重要度不強(qiáng)的航路段在這一動(dòng)態(tài)過(guò)程中體現(xiàn)出了更為關(guān)鍵的作用。在剔除一定數(shù)量的子網(wǎng)絡(luò)中，航路段只有存在于的最大連通子圖之內(nèi)才能發(fā)揮作用，孤立的航路段對(duì)航路網(wǎng)絡(luò)而言沒(méi)有意義。綜上，本文提出的關(guān)鍵航路識(shí)別算法能夠識(shí)別出對(duì)網(wǎng)絡(luò)性能發(fā)揮起到關(guān)鍵性作用的航路網(wǎng)絡(luò)集合，與傳統(tǒng)連邊刪除評(píng)估法相比，能夠反映網(wǎng)絡(luò)結(jié)構(gòu)變化的動(dòng)態(tài)過(guò)程，識(shí)別出更為關(guān)鍵的航路段集合。

圖5 兩種方法的航路網(wǎng)絡(luò)總性能變化

其他具體網(wǎng)絡(luò)性能指標(biāo)隨著關(guān)鍵航路段識(shí)別數(shù)目的變化如圖6 所示。

圖6 5 項(xiàng)網(wǎng)路性能指標(biāo)變化

從圖6 中可以看出，和值下降趨勢(shì)與總性能的趨勢(shì)相近似，在剔除1 條關(guān)鍵航路段后，這2項(xiàng)指標(biāo)都基本下降了60%以上。值不斷上升，是由于隨著網(wǎng)絡(luò)最小連通子圖尺寸的不斷減小，剔除了孤立的節(jié)點(diǎn)以后，僅計(jì)算最大連通子圖的穩(wěn)定性和魯棒性，反而上升，此時(shí)值僅用于評(píng)估網(wǎng)絡(luò)健康程度。隨著網(wǎng)絡(luò)規(guī)模的減小，值也逐漸下降；而隨著剔除的航路段數(shù)目增加，網(wǎng)絡(luò)趨于消解，孤立點(diǎn)越來(lái)越點(diǎn)，聚集程度也逐漸下降。這5 項(xiàng)指標(biāo)的變化符合預(yù)期。

利用改進(jìn)的連邊刪除評(píng)估法對(duì)昆明管制區(qū)航路網(wǎng)絡(luò)數(shù)目為11、18 的關(guān)鍵航路段集合進(jìn)行識(shí)別，識(shí)別結(jié)果如圖7 所示。

圖7 昆明航路網(wǎng)絡(luò)中的關(guān)鍵航路段集合示意圖

如圖6（a）所示，剔除這11 條航路后，航路網(wǎng)絡(luò)的總性能下降為0.250 1，剩余網(wǎng)絡(luò)的平均最短路徑為2.989 5，即任意節(jié)點(diǎn)之間相互到達(dá)平均需要中轉(zhuǎn)1.989 5 次；=0.261 3，剩余網(wǎng)絡(luò)的航路段總距離為4 330 km；網(wǎng)絡(luò)平均聚類系數(shù)為0.124 7，聚集程度與原網(wǎng)絡(luò)變化不大；最大聯(lián)通子圖尺寸為20 個(gè)，網(wǎng)絡(luò)連通性大幅下降；網(wǎng)絡(luò)魯棒性上升為0.038 4，這是網(wǎng)絡(luò)結(jié)構(gòu)縮小的緣故，使得剩余網(wǎng)絡(luò)反而更為穩(wěn)定。分析不同數(shù)目下的關(guān)鍵航路段集合發(fā)現(xiàn)，改進(jìn)連邊刪除評(píng)估法得到的關(guān)鍵航路段集合之間沒(méi)有明顯的繼承關(guān)系，在識(shí)別11 條關(guān)鍵航路段時(shí)識(shí)別出了邊“43-24”，但在識(shí)別18 條時(shí)則沒(méi)有這條邊。

4 結(jié)論

本文提出了一種改進(jìn)的連邊刪除評(píng)估法，該方法采用“不放回”的方式剔除網(wǎng)絡(luò)中的連邊，通過(guò)多屬性決策方法對(duì)剔除連邊后的網(wǎng)絡(luò)進(jìn)行綜合性能評(píng)估，根據(jù)性能的下降幅度可以準(zhǔn)確識(shí)別出網(wǎng)絡(luò)中不同規(guī)模的關(guān)鍵連邊集合。最后，以對(duì)昆明管制區(qū)航路網(wǎng)絡(luò)為實(shí)驗(yàn)平臺(tái)，進(jìn)行實(shí)驗(yàn)分析，結(jié)果顯示，改進(jìn)后的連邊刪除評(píng)估法對(duì)關(guān)鍵航路段集合的識(shí)別效果更好，可以在識(shí)別過(guò)程中反映航路網(wǎng)絡(luò)結(jié)構(gòu)變化的動(dòng)態(tài)過(guò)程，迅速發(fā)掘出潛在的關(guān)鍵航路段。