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

（1.空軍工程大學空管領航學院，西安 710051；2.國家空管防相撞技術重點實驗室，西安 710051；3.解放軍95178 部隊，南寧 530031；4.解放軍93220 部隊，哈爾濱 150046）

0 引言

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

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

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

1 改進連邊刪除評估法

1.1 復雜網(wǎng)絡模型

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

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

1.2 連邊刪除評估法

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

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

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

1.3 改進流程

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

圖1 改進連邊刪除評估法步驟

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

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

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

Step 4：剔除航路重要度序列{，，，…，e}中此時排序為第1 的航路段，得到新的網(wǎng)絡G。

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

2 網(wǎng)絡性能評估

2.1 多屬性決策分析

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

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

之后，對矩陣指標進行標準化處理：

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

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

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

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

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

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

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

圖2 最大連通子圖示意圖

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

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

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

圖3 平均最短路徑示意圖

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

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

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

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

3 實驗分析

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

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

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

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

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

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

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

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

圖6 5 項網(wǎng)路性能指標變化

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

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

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

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

4 結(jié)論

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