航空網絡關鍵節(jié)點辨識的核極限學習機算法研究

牛軍鋒，甘旭升，孫靜娟，涂從良

(1.西京學院 管理技術系, 西安 710123) (2.空軍工程大學 空管領航學院, 西安 710051)

0 引 言

隨著國際國內機場、航路航線數(shù)量的指數(shù)式爆炸增長，以城市機場為節(jié)點、航線為連邊的航空網絡逐漸形成。航空網絡的發(fā)展水平反映了國家的社會和經濟狀況，是國家實力的一種象征。在平時，航空網絡為社會各產業(yè)提供了交流和輸出平臺，促進了經濟發(fā)展。在戰(zhàn)時，航空網絡擔負著戰(zhàn)斗物資轉移與戰(zhàn)斗支援任務，直接影響戰(zhàn)爭進程。

當前，辨識航空網絡關鍵節(jié)點的理論研究已成為熱點。以往的關鍵節(jié)點辨識方法存在的不足主要體現(xiàn)在兩個方面：其一，重視網絡拓撲性質及其節(jié)點相互關系，沒有考量網絡邊權。例如，H.W.Corley等通過研究刪除節(jié)點后的最短路徑來評估刪除節(jié)點的重要性；D.Gomezb等比較了接近中心性、介數(shù)中心性和度數(shù)中心性指標，并引入博弈論評估了網絡節(jié)點的重要性；He Nan等根據節(jié)點度、效率研究了復雜網絡節(jié)點的重要排序問題；譚躍進等在定義凝聚度基礎上提出了一種評估節(jié)點重要度的節(jié)點收縮方法，將收縮后網絡凝聚度最大的節(jié)點視為最重要的節(jié)點。上述研究主要適用于不帶權網絡，但基本沒有考慮航空網絡中航線流量的影響。其二，方法過于單一，一般僅考慮節(jié)點的某一性質。例如，謝鳳宏等根據復雜網絡關鍵節(jié)點辨識算法的缺點，提出了一種基于加權聚類系數(shù)的復雜網絡節(jié)點重要度排序方法；Chen Duanbing等根據每種中心性度量自身缺點，將幾種不同的中心性度量多屬性化，并采用層次分析法對多屬性進行聚合，得到各節(jié)點的影響評估值；王建偉等依據網絡中節(jié)點的局域特征，提出了一種基于近鄰節(jié)點度節(jié)點重要性的度量方法。上述研究簡便高效，不足之處是機場節(jié)點的重要性影響因素十分復雜，僅考慮個別性質往往難以獲得準確結論。

通常采用接近中心度、介數(shù)、網絡連接密度以及網絡效率來綜合評估節(jié)點的重要性。然而在實際計算中，上述指標通常涉及最短路徑等復雜度高的運算，導致評估過程耗時過長，進而影響關鍵節(jié)點的辨識效果。因此，本文以節(jié)點度值、點強和

K

-shell值等簡單指標作為輸入，以由復雜指標得到的綜合重要度作為輸出，選取少量節(jié)點訓練改進型極限學習機(Extreme Learning Machine，簡稱ELM)模型，對航空網絡關鍵節(jié)點進行辨識，并以中美兩國航空網絡為例進行仿真驗證。

1 節(jié)點簡單指標

航空網絡對關鍵機場的研究主要是指標分析，指標較少時評估準確度不夠理想，指標較全面時計算的時間復雜度又很高。

簡單指標值為訓練知識數(shù)據庫，本文選取節(jié)點度值、點強、

K

-shell值作為簡單指標。

節(jié)點度值：反映網絡中單個節(jié)點與相鄰節(jié)點間連接次數(shù)的指標，定義為節(jié)點的直接連邊數(shù)。

(1)

式中：

a

為兩節(jié)點間的連邊狀況。若節(jié)點

v

和

v

不存在直接連邊，則

a

=0；否則，

a

=1。點強：主要指航空網絡中的邊權，即航線流量。點強

S

的表達式為

(2)

式中：

w

為與節(jié)點

v

直接連邊的權值；

N

為節(jié)點

v

的相鄰節(jié)點集合。

周圍機場與該機場節(jié)點聯(lián)系越緊密，連邊權值就越大。

K

-shell：

K

-shell法是節(jié)點排序的代表性算法，根據節(jié)點度或其他指標，將處在網絡外殼的節(jié)點一層一層剝離，剝離越晚的節(jié)點就越重要，如圖1所示。其具體步驟是：搜索網絡中度為1的節(jié)點，刪除此類節(jié)點及其連邊；刪掉這些節(jié)點后，網絡結構出現(xiàn)變化，將此時度是1的節(jié)點及其連邊刪除，依此過程，繼續(xù)刪除節(jié)點，直至網絡中不包含度為1的節(jié)點。將刪掉的節(jié)點組成的殼作為1-殼(即

Ks

=1)。同理，繼續(xù)去除節(jié)點度為2的節(jié)點，作為2-殼，以此類推，直至刪完所有節(jié)點。這種方法對節(jié)點進行的是粗粒化排序，雖然精度不高，但反映了節(jié)點的全局性質。

圖1 K-shell方法示意

對于節(jié)點

v

，其

K

-shell值為

Ks

，該值越大，節(jié)點越重要。簡單指標的優(yōu)缺點對比如表1所示，這三個指標比較有代表性，且都具有較低時間復雜度。

表1 三個簡單指標的相關信息

對簡單指標進行歸一化：

對于節(jié)點

v

的度值

(3)

對于節(jié)點

v

的點強

S

和

K

-shell值

Ks

，做同樣的處理。綜上所述，

n

個節(jié)點可以組成一個簡單的指標值矩陣

(4)

式中：為

n

個節(jié)點的度值、點強和

K

-shell值矩陣。

2 節(jié)點復雜指標

在復雜網絡領域，辨識關鍵節(jié)點的方法主要包括社會網絡分析方法和系統(tǒng)科學分析方法。

對于社會網絡分析方法，可選取接近中心性與介數(shù)中心性作為評估指標。

接近中心性(

CC

)：計算網絡中節(jié)點

v

與剩余節(jié)點的距離平均值，解決特殊值問題。若

v

與其他節(jié)點的距離比節(jié)點

v

小，則認為

v

的

CC

比

v

大。通常，最靠近中心的節(jié)點具有信息流的最佳視野。設網絡包含

n

個節(jié)點，則

v

到網絡中剩余節(jié)點的最短距離平均值：

(5)

若

d

較小，則說明

v

比較接近網絡的剩余節(jié)點。

d

的倒數(shù)可定義為節(jié)點

v

的

CC

：

(6)

CC

(

i

)越大，

v

越接近網絡中心，位置越重要，重要性也越大。節(jié)點度和接近度方法效果對比如圖2所示，可以看出：接近度比節(jié)點度更能精確區(qū)分節(jié)點重要性。

(a) 節(jié)點度 (b)接近度

介數(shù)中心性(

BC

)：在整體網絡中反映節(jié)點的中心程度，節(jié)點

v

的介數(shù)

BC

(

k

)是指經過節(jié)點

v

的網絡中全部節(jié)點對間的最短路徑數(shù)占總最短路徑數(shù)的比重。

(7)

式中：

σ

(

k

)為

v

與

v

間經由

v

的最短路徑數(shù)目；

σ

為

v

與

v

間最短路徑的數(shù)目。

對于系統(tǒng)科學分析方法，可采用節(jié)點刪除法。節(jié)點刪除法的思想是，刪除某個節(jié)點后，計算網絡性能，并與原網絡比較，網絡性能變化越大，節(jié)點就越重要。對于網絡性能，采用網絡連接密度與網絡效率來衡量。

網絡連接密度(

LD

)：在無權網絡中，連接密度指網絡中現(xiàn)有連邊與可能存在的連邊的比值。對于航空網絡，可定義加權連接密度：

(8)

式中：

n

為當前網絡節(jié)點總數(shù)；若

v

與

v

直接相連，

a

=1，否則，

a

=0；

w

為節(jié)點連邊的權值。

LD

越大，整體的異質性越高，網絡流量越大，網絡綜合性能越好。網絡效率(

NE

)為所有節(jié)點之間的距離倒數(shù)和的平均值。

(9)

式中：

N

為網絡中節(jié)點總數(shù)。

NE

反映了網絡信息傳輸?shù)碾y易程度，

NE

越大，信息傳遞越順暢，抗毀性越強。

四個復雜指標的優(yōu)缺點與時間復雜度對比如表2所示。

表2 四個復雜指標的相關信息

從表2可以看出：除了連接密度外，其余三個指標的計算時間復雜度均為

O

(

N

)。雖然綜合上述四個指標能夠較為全面地反映節(jié)點的重要性，但這樣耗費時間較長，不適合復雜的大型網絡。

3 核極限學習機(KELM)

考慮到航空網絡節(jié)點訓練樣本集的復雜指標計算復雜度較高，提出采用基于核函數(shù)的ELM (Kernel ELM,簡稱KELM) 來學習簡單指標與綜合重要度之間的映射關系，以期耗費較少的計算時間和資源，實現(xiàn)航空網絡節(jié)點重要度的準確評估，進而辨識出關鍵節(jié)點。

3.1 核函數(shù)理論

對于模式識別問題，當樣本在低維空間線性不可分時，可通過某非線性函數(shù)映射到高維特征空間，能夠實現(xiàn)線性可分。核函數(shù)基本原理：通過某非線性函數(shù)，將輸入空間樣本映射到高維特征空間，在高維特征空間進行數(shù)據的處理。其關鍵在于，引入核函數(shù)后，能夠將高維特征空間的內積運算轉化為輸入空間內的運算。

設

x

與

x

為輸入空間中的樣本點，原始輸入空間到高維特征空間的映射函數(shù)為

Φ

，則核函數(shù)方法可描述為實現(xiàn)內積變換(

x

·

x

)→

K

(

x

,

x

)= <

Φ

(

x

),

Φ

(

x

)>

(10)

式中：

K

(

x

,

x

)為核函數(shù)；<

Φ

(

x

),

Φ

(

x

)>為內積。在式 (10) 中，輸入空間的核函數(shù)與高維特征空間的內積是等價的，非線性變換函數(shù)

Φ

的內積運算較為復雜，而核函數(shù)

K

(

x

,

x

)的運算則相對簡單，因此，為了降低運算復雜性，可用輸入空間的核函數(shù)運算替代高維特征空間的內積運算。此外，在使用核函數(shù)時，無需明確

Φ

的具體形式和參數(shù)，極大地方便了運算。核函數(shù)的映射過程如圖3所示。

圖3 核函數(shù)的映射過程

3.2 基于核函數(shù)的ELM

(11)

則ELM的輸出函數(shù)為

(12)

對于訓練樣本(,)，且=[

x

1,

x

2,…,

x

]∈

R

與=[

t

1,

t

2,…,

t

]∈

R

，

g

()為激勵函數(shù)，

L

為隱層節(jié)點個數(shù)(

L

≤

N

)。則ELM算法計算步驟：(1) 隨機初始化輸入層與隱層的權值向量和隱層節(jié)點偏置值

b

；(2) 構建隱層輸出矩陣=[

g

(),…,

g

()]；

其中，=[

x

,

x

,…,

x

]，為

N

個樣本；

g

()表示ELM網絡隱層節(jié)點的輸出函數(shù)，根據核函數(shù)理論，通過非線性函數(shù)將輸入空間的樣本點映射入特征空間，并由核函數(shù)代替特征空間的內積運算。假設隱層特征映射函數(shù)

g

()形式未知，則可用核函數(shù)代替其內積形式。ELM可通過核矩陣形式來描述

Ω

=∶

Ω

ELM,=

g

()·

g

()=

K

(,)

(13)

此時，基于核函數(shù)的ELM (KELM) 輸出函數(shù)為

(14)

不難理解，在KELM算法中，無需了解

g

()的具體形式，僅需明確具體核函數(shù)

K

(,)，就可計算輸出函數(shù)的值。需要說明的是，核函數(shù)為內積形式，在計算式 (12) 時，不需要確定網絡隱層節(jié)點的個數(shù)。

4 節(jié)點重要度評估流程

本文提出采用KELM對航空網絡節(jié)點重要度進行評估的流程如圖4所示。

圖4 節(jié)點重要性評估流程

具體可劃分為以下四個步驟：

(1) 構造訓練樣本。從網絡中隨機生成部分節(jié)點，計算度值、點強和

K

-shell值等簡單節(jié)點指標值；同時，確定接近中心性、介數(shù)中心性、網絡連接密度和網絡效率等復雜指標值。(2) 確定綜合重要度。通過層次分析法(AHP)計算得出各復雜指標的權重：

W

=0.578 9;

W

=0.205 5;

W

=0.159 2;

W

=0.056 5，進而通過公式

Y

=0.578 9

BC

+0.205 5

NE

+0.159 2

CC

+0.056 5

LD

計算以上隨機節(jié)點的綜合重要度=[

Y

,

Y

,…,

Y

]。(3) 訓練評估模型。以為輸入，以為輸出，訓練KELM評估模型，以學習其內在關系。(4) 執(zhí)行評估過程。對于網絡中除訓練樣本的新節(jié)點，僅需計算新節(jié)點的簡單指標，并輸入KELM評估模型，就能計算出新節(jié)點的綜合重要度，進而完成關鍵節(jié)點的辨識。此外，KELM訓練時對參數(shù)變化反應比較敏感，當

c

值比較小，而

σ

值比較大時，模型的訓練精度非常高，而測試精度卻不理想，說明此時參數(shù)對訓練的數(shù)據擬合程度非常高，但對新樣本的預測能力卻非常低，即出現(xiàn)通常所說的“過學習”現(xiàn)象。因此，在選取參數(shù)

c

和參數(shù)

σ

時，可引入交叉驗證思想，計算出測試精度較高時所對應的最優(yōu)參數(shù)組合。

5 仿真分析

為了驗證本文所提方法的可行性，首先對隨機網絡進行測試，然后分別對中美兩國航空網絡進行測試，并對測試結果進行分析。

5.1 隨機網絡測試

考慮一隨機網絡

G

={

V

,

E

,

W

}，該網絡含有600個節(jié)點，6 000條連邊，實驗目的是檢驗KELM關鍵節(jié)點辨識方法的有效性，也即判斷KELM能夠準確學習簡單指標與綜合重要度之間的關系。按照關鍵節(jié)點識別算法步驟，先隨機選擇60個節(jié)點作為KELM訓練樣本，通過AHP得出復雜指標

CC

、

BC

、

LD

和

NE

的權重分別為0.159 2,0.578 9,0.056 5,0.205 5，計算復雜指標加權，其和為綜合重要度值

Y

，然后計算對應簡單指標值

X

。KELM訓練前，利用交叉驗證法在log

c

∈[-10,10]與log

σ

∈[-10,10]內自動搜索最佳的參數(shù)

c

和參數(shù)

σ

，參數(shù)尋優(yōu)過程如圖5所示。圖中，復雜指標重要度的實際值和預測值的均方根誤差

RMSE

為

(15)

圖5 對隨機網絡的參數(shù)尋優(yōu)過程

從圖5可以看出：網格圖底部較平緩，說明在很大取值范圍內的兩個參數(shù)都可以使

RMSE

最小，因此，能夠較容易地找出最佳參數(shù)

c

和

σ

。進行訓練后，隨機選擇除訓練樣本之外的60個節(jié)點作為測試節(jié)點，計算得到其簡單指標

X

，并輸入KELM重要度評估模型，得到測試結果

Y

，與其原來復雜指標值評估得到的重要度

Y

進行比較，效果如圖6所示。

圖6 測試結果與實際值對比(隨機網絡)

從圖6可以看出：KELM輸出的結果與原來的重要度值非常接近，說明本文方法是準確、可行的。由表2可知，使用復雜指標對節(jié)點重要度評估所需時間復雜度為

O

(

N

)，而KELM評估僅需

O

(

N

)，其中，

N

為訓練樣本數(shù)。因此，采用這種方法，可以通過簡單、耗時少的指標快速得到節(jié)點的綜合重要度。

5.2 航空網絡測試

對于美國航空網絡，做同樣測試，實驗數(shù)據集包含332個機場節(jié)點、2 126條連邊(直飛航線)以及連邊的權重，美國航空網絡的拓撲圖如圖7所示。數(shù)據來源詳見文獻[14]。

圖7 美國航空網絡拓撲

根據本文方法，通過交叉驗證法確定參數(shù)，如圖8所示。在節(jié)點重要度評估過程中，耗時最長的是知識數(shù)據庫的建立(用復雜指標評估節(jié)點重要度)，如果選擇網絡中大部分節(jié)點作為訓練樣本，評估方法就失去了時間復雜度低的優(yōu)勢，變得沒有意義。因此，本文測試KELM是否僅需要很少一部分節(jié)點就能準確評估節(jié)點重要度，分別隨機選擇20、40、60、80個節(jié)點作為訓練樣本，然后比較測試結果與原來的重要度值，如圖9所示。

圖8 對美國航空網絡的參數(shù)尋優(yōu)過程

(a) 20個訓練樣本

(b) 40個訓練樣本

(c) 60個訓練樣本

(d) 80個訓練樣本

從圖9可看出：選擇20個訓練樣本時，測試結果與原值的擬合效果較差，當選擇40個訓練樣本時，擬合效果明顯改善，選擇60、80個節(jié)點時，擬合效果無明顯提升。因此，在美國航空網絡中，僅需計算40個節(jié)點的復雜指標值，如此將大幅降低原來的運算量，提高辨識關鍵節(jié)點的效率。

選擇40個節(jié)點作為訓練樣本，對所有節(jié)點進行測試，得到測試結果后對節(jié)點進行排序，并與原復雜指標評估重要度排序、ACI排序進行比較，如表3所示。其中，ACI指國際機場委員會對美國各機場的綜合排名。

表3 美國機場節(jié)點重要度排序

從表3可以看出：測試結果(簡單指標評估結果)排名前16的機場節(jié)點與ACI僅有3個不同，說明本文方法比較符合現(xiàn)實情況，具有一定的準確性。再將測試結果與復雜指標評估結果作比較，發(fā)現(xiàn)兩種方法的結果幾乎一致，在前幾名中，只有San Francisco與G.Bush對調了順序，后幾名略有差異，說明KELM的學習效果較好，具有準確預測數(shù)據的能力。

為了驗證算法的通用性，把本文方法應用于中國的航空網絡。將國內2016年199個具有定期航班的通航城市作為目標節(jié)點，爬取和收集網頁數(shù)據，構建我國航空網絡模型，并對我國航空網絡進行關鍵節(jié)點識別。參數(shù)尋優(yōu)過程如圖10所示，檢驗測試結果的準確性如圖11所示，可以看出：測試結果在趨勢上與實際值總體保持一致。

圖10 對中國航空網絡的參數(shù)尋優(yōu)過程

圖11 測試結果與原值對比(中國航空網絡)

6 結 論

(1) 基于接近中心性、介數(shù)中心性、網絡連接密度對節(jié)點進行綜合重要度評估，克服了以往復雜網絡研究領域未考慮航線流量、機場位置等影響節(jié)點重要性的航空網絡具體因素的不足。

(2) 采用KELM學習綜合重要度值與簡單指標的映射關系。對于剩余大部分節(jié)點，只需求出其簡單指標，便可以求得其綜合重要度和節(jié)點排序。解決了傳統(tǒng)指標單一、未考慮邊權的問題，提高了節(jié)點排序的準確性，同時降低了計算復雜度，節(jié)省了大量時間，實例驗證了其有效性和可行性。

(3) 鑒于數(shù)據獲取和時間問題，本文僅研究了民用機場構成的航空網絡，在未來的研究中可以繼續(xù)拓展，獲取更加充實的數(shù)據，構建軍航或者軍民聯(lián)合航空網絡，以用于航空網絡的平戰(zhàn)轉換機制研究。