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

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

0 引言

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

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

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

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

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

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

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

1.2 連邊刪除評估法

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

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

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

1.3 改進(jìn)流程

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

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

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

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

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

Step 4：剔除航路重要度序列{，，，…，e}中此時排序?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ò)性能評估

2.1 多屬性決策分析

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

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

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

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

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

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

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

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

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á)時，才能在網(wǎng)絡(luò)中發(fā)揮其作用。因此，最大連通子圖尺寸是一個評價網(wǎng)絡(luò)連通性和運(yùn)輸能力的重要指標(biāo)，尺寸是最大連通子圖中節(jié)點(diǎn)的個數(shù)，越大，網(wǎng)絡(luò)連通性越好。

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

圖2 最大連通子圖示意圖

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

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

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

圖3 平均最短路徑示意圖

3）網(wǎng)絡(luò)平均聚類系數(shù)。單獨(dú)一個節(jié)點(diǎn)的聚類系數(shù)是用來描述節(jié)點(diǎn)之間聚集成團(tuán)的程度，整個網(wǎng)絡(luò)的平均聚類系數(shù)則可以描述全局的聚集程度。單個節(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)為一條航路段上的飛行容量與航路段的長度成正比。因此，在基于距離邊權(quán)的航路網(wǎng)絡(luò)中，值取網(wǎng)絡(luò)中所有航路段上的航路距離之和，其計(jì)算如式（11）所示：

為了綜合評估網(wǎng)絡(luò)的性能，需要對以上5 個指標(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 個指標(biāo)的重要度排序?yàn)?。通過AHP 計(jì)算，其權(quán)重向量如下：

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

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

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

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

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

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

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

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

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

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

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

利用改進(jìn)的連邊刪除評估法對昆明管制區(qū)航路網(wǎng)絡(luò)數(shù)目為11、18 的關(guān)鍵航路段集合進(jìn)行識別，識別結(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 個，網(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)連邊刪除評估法得到的關(guān)鍵航路段集合之間沒有明顯的繼承關(guān)系，在識別11 條關(guān)鍵航路段時識別出了邊“43-24”，但在識別18 條時則沒有這條邊。

4 結(jié)論

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