基于接近度與評價矩陣的關(guān)鍵機場節(jié)點識別*

涂從良，吳明功，溫祥西

（空軍工程大學(xué)空管領(lǐng)航學(xué)院，西安 710051）

基于接近度與評價矩陣的關(guān)鍵機場節(jié)點識別*

涂從良，吳明功，溫祥西

（空軍工程大學(xué)空管領(lǐng)航學(xué)院，西安 710051）

針對目前關(guān)鍵節(jié)點識別方法單一、難以適應(yīng)航空網(wǎng)絡(luò)的特點，提出了一種基于接近度與重要度評價矩陣的識別算法。利用改進的接近度算法反映節(jié)點在網(wǎng)絡(luò)中的位置信息，考慮網(wǎng)絡(luò)邊權(quán)即航線流量，構(gòu)建重要度評價矩陣，最后進行計算得到節(jié)點重要度排序結(jié)果。在建立我國航空網(wǎng)絡(luò)模型的基礎(chǔ)上通過實驗得出：北、上、廣以及位于網(wǎng)絡(luò)幾何中心且流量較大的西安等機場為關(guān)鍵節(jié)點。排序結(jié)果表明該算法能有效結(jié)合我國航空網(wǎng)絡(luò)實際特點，準確地反映各個機場節(jié)點的重要性程度。

航空網(wǎng)絡(luò)，關(guān)鍵節(jié)點，接近度，評價矩陣

0 引言

隨著航空運輸業(yè)的快速發(fā)展以及航空流量的增加，我國的航空網(wǎng)絡(luò)已形成并不斷擴張。航空網(wǎng)絡(luò)作為交通命脈，與國家政治、經(jīng)濟、科技的發(fā)展有著緊密聯(lián)系。而關(guān)鍵節(jié)點又在航空網(wǎng)絡(luò)中扮演著重要的角色，如果關(guān)鍵機場節(jié)點發(fā)生擁塞、失效等情況，就很可能造成整個網(wǎng)絡(luò)的癱瘓，從而嚴重影響社會穩(wěn)定。因此，研究航空網(wǎng)絡(luò)的關(guān)鍵節(jié)點識別具有重要的理論價值和現(xiàn)實意義。

航空網(wǎng)絡(luò)是典型的復(fù)雜網(wǎng)絡(luò)［1］，具有復(fù)雜網(wǎng)絡(luò)的特征和性質(zhì)。目前，對復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點識別的理論性研究已成為一個重要課題。以往的關(guān)鍵節(jié)點識別方法存在的不足主要有兩點：一是側(cè)重節(jié)點相互關(guān)系以及網(wǎng)絡(luò)拓撲性質(zhì)，忽略了網(wǎng)絡(luò)邊權(quán)的重要性。如文獻［2］提出的最短路徑破壞網(wǎng)絡(luò)算法；文獻［3］提出的通過對度數(shù)、介數(shù)、中心度等指標進行比較，再用博弈論分析節(jié)點重要性的方法；文獻［4］提出的基于節(jié)點度、效率排序方法；文獻［5］提出的節(jié)點收縮識別法。這些方法對不帶權(quán)網(wǎng)絡(luò)的效果較為理想，但在航空網(wǎng)絡(luò)中，由于未考慮航線流量這一反映機場與航線地位作用的重要指標，所得結(jié)論往往會與實際不符。二是方法單一片面，通常只考慮節(jié)點的某一性質(zhì)。如文獻［6］提出的基于加權(quán)聚類系數(shù)的節(jié)點重要度排序方法；文獻［7］提出的基于度中心性的節(jié)點關(guān)鍵性測度法；文獻［8］提出的基于鄰居節(jié)點度的網(wǎng)絡(luò)節(jié)點識別方法。這些方法簡單且效率高，但機場節(jié)點的重要性影響因素復(fù)雜多樣，僅考慮個別性質(zhì)往往難以取得準確的結(jié)論?；谝酝椒ǖ牟蛔?，運用改進的帶權(quán)接近度算法［9］，并參考重要度評價矩陣［10］，提出一種新型的航空網(wǎng)絡(luò)關(guān)鍵節(jié)點識別算法。接近度算法反映節(jié)點在網(wǎng)絡(luò)中的位置信息，但難以區(qū)分距離相近的節(jié)點，因此，設(shè)置帶權(quán)函數(shù)，增強對節(jié)點的辨識力；重要度評價矩陣體現(xiàn)了節(jié)點在網(wǎng)絡(luò)運輸中所起的作用以及相鄰節(jié)點的重要度貢獻，但未涉及航線流量即邊權(quán)，因此對其作出改進，將節(jié)點邊權(quán)作為評價指標。該算法彌補了傳統(tǒng)方法的缺陷，既考慮到節(jié)點的位置信息，又能夠結(jié)合航線流量考慮節(jié)點對網(wǎng)絡(luò)的影響，對于全面準確識別關(guān)鍵節(jié)點具有一定可行性。

1 基本理論

假設(shè)存在一個無向無自環(huán)的聯(lián)通復(fù)雜網(wǎng)絡(luò)G=（V，L），其中，V={v1，v2，…，vn}為網(wǎng)絡(luò)節(jié)點集合，E={e1，e2，…，em}為網(wǎng)絡(luò)中邊的集合。用A=（aij）n×n表示G的邊權(quán)矩陣，用wij表示節(jié)點vi和節(jié)點vj之間邊eij的權(quán)值，當(dāng)節(jié)點vi和節(jié)點vj存在邊eij時，aij=wij，否則aij=0。

最短路徑是指從節(jié)點v到v′存在路徑 P=（v1，v2，…，vn）（當(dāng) v1=v，vn=v′時）使得最小。從一個機場到指定機場需要中轉(zhuǎn)最少次數(shù)的路徑稱為航空網(wǎng)絡(luò)的最短路徑，這個路徑上的邊ei的數(shù)量為最短距離。

節(jié)點接近度是指節(jié)點v對局部社區(qū)C的接近程度。機場節(jié)點接近度反映了機場在某一區(qū)域航空網(wǎng)絡(luò)中的相對位置，以及機場對整個航空網(wǎng)絡(luò)的影響。

2 關(guān)鍵節(jié)點識別模型構(gòu)建

2.1 航空網(wǎng)絡(luò)模型假定

通過網(wǎng)頁爬取得到全國航班數(shù)據(jù)，將兩兩之間有航班的機場連線，得到中國航空網(wǎng)絡(luò)示意圖，如圖1所示。

圖1 中國航空網(wǎng)絡(luò)圖（港、澳、臺除外）

考慮到航空數(shù)據(jù)的特性和達到簡化計算過程的目的，對實際航空系統(tǒng)作如下假定：

①拓撲模型中的節(jié)點vi表示全國所有具有運輸能力的通用機場，確定為集合 V={v1，v2，…，vn}，其數(shù)量為N=|V|。②邊ej表示機場與機場之間的運輸關(guān)系即航空線路。若兩機場存在航線，則認為有邊相連，否則無邊。兩個機場之間最多存在一條邊相連，且無向。集合 E={e1，e2，…，eM}為邊的集合，其數(shù)量為M=|E|。③假定航線的拓撲特性相同，即不考慮傳輸效率和傳輸線特性的不同，將航線流量作為網(wǎng)絡(luò)中的邊權(quán)。

2.2 帶權(quán)重的接近度計算

航空網(wǎng)絡(luò)節(jié)點的位置與其重要程度有著緊密的聯(lián)系，節(jié)點越趨向于網(wǎng)絡(luò)中心，它是關(guān)鍵節(jié)點的可能性就越大；節(jié)點越趨向網(wǎng)絡(luò)邊緣，它的重要性程度就越低。接近度可以衡量航空網(wǎng)絡(luò)中從指定節(jié)點到達任意節(jié)點的難易程度，即反映節(jié)點的位置及其與剩余節(jié)點的距離，從而對航空網(wǎng)絡(luò)節(jié)點進行關(guān)鍵性評估。傳統(tǒng)的接近度可由式（1）計算：

CLi表示節(jié)點i與其他節(jié)點距離和的倒數(shù)，N表示網(wǎng)絡(luò)中機場數(shù)量，dij表示機場i到機場j的最少中轉(zhuǎn)次數(shù)。

圖2 某一區(qū)域航空網(wǎng)絡(luò)兩種方法識別效果對比

然而傳統(tǒng)的接近度算法不能針對不同網(wǎng)絡(luò)特性進行相應(yīng)的調(diào)整，只能不加區(qū)別地將某一節(jié)點與剩余節(jié)點的最短距離簡單相加。而我國航空網(wǎng)絡(luò)節(jié)點間的最短距離dij非常相近，最大值均不超過3，因此，這種接近度算法的識別效果并不明顯。

針對我國航空網(wǎng)絡(luò)的特點，提出用帶權(quán)的接近度算法來突出節(jié)點之間的路徑距離對識別結(jié)果的影響。于是，在這里為最短路徑設(shè)置一個權(quán)重函數(shù)f（x），改進的接近度計算公式如下：

其中，f（dij）為對數(shù)函數(shù)，當(dāng)dij在較小范圍內(nèi)變化時，f（dij）變化較大；當(dāng)dij增大到一定程度時，f（dij）變化會越來越小。這樣做是為了增加相鄰航空網(wǎng)絡(luò)節(jié)點對其接近度的影響，減小距離遠的節(jié)點的影響。

2.3 評價矩陣確立

在識別航空網(wǎng)絡(luò)關(guān)鍵節(jié)點的過程中，除了考慮機場節(jié)點位置的重要性，還要考慮途徑機場節(jié)點的航線流量，即邊權(quán)。重要度評價矩陣能充分結(jié)合機場節(jié)點位置和航班流量，反映實際航空網(wǎng)絡(luò)中機場相對其他機場的重要度，以及機場對整個交通運行的影響程度。在重要度評價矩陣中，用度來構(gòu)成節(jié)點間的重要度關(guān)聯(lián)，用邊權(quán)和接近度作為評價參數(shù)。

在上一節(jié)的航空網(wǎng)絡(luò)模型中，節(jié)點數(shù)量為N=|V|，設(shè)機場節(jié)點vi的度為Di。其中，a為航空網(wǎng)絡(luò)的鄰接矩陣。按照自身重要度的Di/k2為比例，vi對其每一個相鄰節(jié)點輸出重要度。計算所有節(jié)點v1，v2，…，vn對其相鄰節(jié)點的輸出重要度比例值，于是得到相鄰節(jié)點重要度輸出矩陣，記為HIC：

矩陣中，δij為貢獻分配參數(shù)，若兩個節(jié)點相連則取值為1，否則取值為0；對角線上的元素為1，意味著節(jié)點對節(jié)點自身的貢獻輸出比例為1。k為節(jié)點平均度，

為了能夠體現(xiàn)機場節(jié)點在航線網(wǎng)絡(luò)運輸過程中所起的作用，結(jié)合航班流量，計算每個機場節(jié)點的權(quán) Si，即：

其中Ni是節(jié)點i的鄰居節(jié)點集，wij是與節(jié)點i直接相連邊的權(quán)重。權(quán)值越大，說明該機場節(jié)點與周圍機場聯(lián)系越緊密。

融合節(jié)點的接近度值，并用節(jié)點的重要度貢獻值來代替HIC的重要度貢獻比例值，就可以得到節(jié)點重要度評價矩陣HE：

式中，HEij表示節(jié)點j對節(jié)點i的重要度貢獻值?？梢钥闯觯粋€機場節(jié)點對其相鄰機場的重要度貢獻值與節(jié)點接近度、度和途經(jīng)航線的流量有關(guān)。節(jié)點的接近度值越高、度值越高、航線流量越大，則它對相鄰節(jié)點的重要度貢獻越大。

2.4 重要度計算

機場節(jié)點重要度計算從兩方面進行，一方面是接近度，另一方面是邊權(quán)。接近度作為識別航空網(wǎng)絡(luò)節(jié)點的一種方法，能夠判定機場位置對其重要性程度的影響。這里采用對數(shù)函數(shù)進行加權(quán)，放大了鄰近節(jié)點的影響，對實際航空網(wǎng)絡(luò)更具有針對性。邊權(quán)的設(shè)置考慮了航線流量，比以往方法更能貼近實際。為了融合這兩方面的優(yōu)勢，使節(jié)點識別算法既準確又高效，定義節(jié)點i的重要度Ci：

式中，Ci表示所有與機場i相鄰的機場對其重要度貢獻的求和，即文中要計算的最終排序重要度值。

2.5 識別算法步驟

下面給出評估節(jié)點重要度的算法流程：

輸入：復(fù)雜網(wǎng)絡(luò)鄰接矩陣A=（aij）n×n，邊權(quán)wi輸出：節(jié)點i的重要度Ci以及排序如下頁圖3流程圖所示，算法的幾個主要步驟為：1）用Floyd算法［11］計算所有節(jié)點對之間的最短距離矩陣Dis=［dij］；2）計算每個節(jié)點的接近度（初始值為0）；3）計算節(jié)點關(guān)鍵性貢獻矩陣HIC；4）確定關(guān)鍵性評價矩陣HE；5）計算每個節(jié)點的重要度。

3 仿真實驗

3.1 算法驗證

為了驗證算法的有效性，這里采用隨機生成網(wǎng)絡(luò)，對邊進行賦權(quán)，作為關(guān)鍵節(jié)點識別算例，下頁圖4為網(wǎng)絡(luò)拓撲圖。運用文章提出的識別算法，得到重要度結(jié)果，并與傳統(tǒng)方法作比較，如表1。

圖3 關(guān)鍵節(jié)點識別算法流程圖

圖4 隨機生成加權(quán)網(wǎng)絡(luò)拓撲

從3種方法的排序結(jié)果可以看出，本算法得到的區(qū)分效果明顯優(yōu)于另外兩種方法。以節(jié)點2、節(jié)點3為例，節(jié)點在網(wǎng)絡(luò)中地位相近，但邊權(quán)相差較大，用接近度算法和重要度評價矩陣算法得到的結(jié)果相似度很高，而本算法能很好地體現(xiàn)邊權(quán)差異，得到的結(jié)果表明2號節(jié)點的重要度明顯高于3號節(jié)點。以節(jié)點3、節(jié)點12為例，經(jīng)過兩節(jié)點的流量相近，但12號節(jié)點更接近網(wǎng)絡(luò)中心，本算法得到的結(jié)果反映了這種差異，而另外兩種方法效果則不明顯。

表1 網(wǎng)絡(luò)節(jié)點重要度及排序

3.2 算法應(yīng)用

在實驗中，對2016年5月全國199個通航機場一周內(nèi)飛行班次進行統(tǒng)計。如表2，得到關(guān)于機場與機場之間航班數(shù)矩陣M=（aij）199×199，這里只取前6個城市。當(dāng)機場i與機場j之間航班數(shù)不等于0時，aij取值為1，否則取0，從而得到關(guān)于中國航空網(wǎng)絡(luò)的鄰接矩陣A=（aij）n×n。

根據(jù)算法模型，輸入鄰接矩陣A=（aij）n×n，根據(jù)佛洛依德算法得到機場節(jié)點之間的最短距離矩陣Dis=［dij］，根據(jù)式（6）得到各個節(jié)點的重要度 Ci以及排序如下頁表3。

根據(jù)關(guān)鍵節(jié)點識別算法得到的各個城市機場節(jié)點，得到以下結(jié)論：

表2 飛行班次統(tǒng)計（周）

①北京、上海、廣州的重要度Ci分別為2.07556，2.025 213，1.340 661，位列前三，與現(xiàn)實符合，驗證了算法的準確性。②西安排在了第4，它是中國地理位置的中心，是貫通東西的交通樞紐，相比用節(jié)點度排序時西安排在第6，算法得到的結(jié)果更具合理性，表明算法充分考慮了節(jié)點的位置信息。③緊接著的還有成都、昆明、重慶、深圳等城市，這些城市都是區(qū)域的中心，說明算法對這些網(wǎng)絡(luò)局部影響較大的節(jié)點具有較強的識別能力。④排在最后幾位的安康、阿拉善右旗等城市，大多地處幾何邊緣地帶，且航空流量小，再次說明算法能夠準確判斷它們的

表3 節(jié)點重要度及排序

位置信息和邊權(quán)信息。

4 結(jié)論

通過改進接近度算法與重要度評價矩陣對我國航空網(wǎng)絡(luò)進行了關(guān)鍵節(jié)點識別。仿真實驗證明，提出的算法對不同節(jié)點的識別區(qū)分度比較明顯，改進了傳統(tǒng)方法的不足，能夠結(jié)合航線流量和機場位置較全面地反映各個機場節(jié)點的重要性，對于重點機場節(jié)點目標保障具有重要意義。下一步的研究重點是國內(nèi)外的軍民航機場關(guān)鍵節(jié)點識別。

［1］鄭金連，狄增加.復(fù)雜網(wǎng)絡(luò)研究與復(fù)雜現(xiàn)象［J］.系統(tǒng)辯證學(xué)學(xué)報，2005，13（4）：8-13.

［2］CORLEY H W，SHA D Y.Most vital links and nodes in weighted networks［J］.Operation Research Letters，1982，1（4）：157-160.

［3］GOMEZB D，ENRIQUE G A.Centrality and power in social networks：a game theoretic approach［J］.Mathematical Social Sciences，2003，46（1）：27-54.

［4］HE N，LI D Y，GAN W Y，et al.Mining vital nodes in complex networks［J］.Computer Science，2007，34（12）：1-5.

［5］譚躍進，吳俊，鄧宏鐘.復(fù)雜網(wǎng)絡(luò)中節(jié)點重要度評估的節(jié)點收縮方法［J］.系統(tǒng)工程理論與實踐，2006，26（11）：79-83.

［6］謝鳳宏，張大為，黃丹，等.基于加權(quán)復(fù)雜網(wǎng)絡(luò)的文本關(guān)鍵 詞 提 取 ［J］. 系 統(tǒng) 科 學(xué) 與 數(shù) 學(xué) ，2010，30（11）：1592-1596.

［7］CHEN D B，LYU L，SHANG M S.Identifying influential nodes in complex networks［J］.Physica A，2012，391（4）：1777-1787.

［8］王建偉，榮莉莉，郭天柱.一種基于局部特征的網(wǎng)絡(luò)節(jié)點重要性度量方法［J］. 大連理工大學(xué)學(xué)報，2010，50（5）：822-826.

［9］方平，李芝棠，涂浩，等.復(fù)雜網(wǎng)絡(luò)局部社區(qū)挖掘的節(jié)點接近度算法 ［J］. 計算機工程與應(yīng)用，2013，49（17）：38-42.

［10］傅子昊，孫磊，林振智，等.基于節(jié)點重要度評價矩陣的網(wǎng)絡(luò)重構(gòu)雙層優(yōu)化策略［J］.電力自動化設(shè)備，2016，36（5）：37-42.

［11］蘇競秀，龍陳鋒.Floyd算法與RAD算法性能分析［J］.計算機應(yīng)用與軟件，2015，32（2）：116-119.

［12］司曉靜.復(fù)雜網(wǎng)絡(luò)中節(jié)點重要性排序的研究［D］.西安：西安電子科技大學(xué)，2012.

［13］周旋，張鳳鳴，李克武.利用重要度評價矩陣確定復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點［J］.物理學(xué)報，2012，61（5）：11-16.

Identification of Key Airport Nodes Based on Closeness Sorting Algorithm and Evaluation Matrix

TU Cong-liang，WU Ming-gong，WEN Xiang-xi
（School of Air Traffic Control and Navigation，Air Force Engineering University，Xi’an 710051，China）

A key airport recognition algorithm is proposed according to the characteristics of China’s aviation network.Due to the incomprehensiveness and neglect of traffic flow of previous methods，the proposed algorithm combines importance evaluation matrix and closeness sorting algorithm.On the basis of the air network model，the distance weight function is set up and the closeness sorting algorithm is used to reflect the position of the airport.Then the closeness sorting algorithm and evaluation matrix are integrated，and the evaluation matrix is constructed considering edge weight which is air traffic flow in reality，meantime，the importance degree of each airport is calculated.As the results show，this algorithm is capable of employing air traffic flow as well as other properties of China’s aviation network，and reflects the importance of each airport accurately.

aviation network，key nodes，closeness degree，evaluation matrix

1002-0640（2017）10-0172-05

V37；TP393

A

10.3969/j.issn.1002-0640.2017.10.036

2016-08-05

2016-09-07

國家空管科研基金資助項目（GKG201410001）

涂從良（1991- ），男，浙江湖州人，碩士。研究方向：空域規(guī)劃與安全管理。