基于結(jié)構(gòu)中心性的航路網(wǎng)絡(luò)關(guān)鍵節(jié)點識別

蔣一森

(中國民航大學(xué)空中交通管理學(xué)院,天津 300300)

0 引 言

新中國成立以來，尤其是經(jīng)過改革開放以來的快速建設(shè)，我國航路航線網(wǎng)絡(luò)發(fā)生了巨大變化，網(wǎng)絡(luò)總量已初具規(guī)模，網(wǎng)絡(luò)布局和結(jié)構(gòu)明顯改善，技術(shù)水平日益提高，運(yùn)輸能力顯著增強(qiáng)。從網(wǎng)絡(luò)結(jié)構(gòu)看，經(jīng)過多年發(fā)展，基本形成了點、線、面有機(jī)銜接，干支層級清晰，主次分明，四通八達(dá)的網(wǎng)絡(luò)結(jié)構(gòu)。

航路網(wǎng)絡(luò)是民用航空運(yùn)輸?shù)幕A(chǔ)性資源，是民航遠(yuǎn)距離、大容量飛行活動的關(guān)鍵紐帶。航路網(wǎng)絡(luò)關(guān)鍵節(jié)點是支撐、連接整個航路網(wǎng)絡(luò)的重要橋梁，同時對路網(wǎng)的效能發(fā)揮也起著重要的作用。要理解網(wǎng)絡(luò)結(jié)構(gòu)與網(wǎng)絡(luò)行為之間的關(guān)系，進(jìn)而考慮改善網(wǎng)絡(luò)的行為，需要對實際網(wǎng)絡(luò)的結(jié)構(gòu)特征有很好的了解。

在分析航空網(wǎng)絡(luò)結(jié)構(gòu)特性方面，Leng等[1]對公路運(yùn)輸網(wǎng)絡(luò)進(jìn)行了抵抗性分析，并對影響公路網(wǎng)絡(luò)抵抗強(qiáng)度的幾大要素進(jìn)行了敏感性分析。崔毅[2]利用復(fù)雜網(wǎng)絡(luò)理論對縣域公路網(wǎng)絡(luò)進(jìn)行了實證研究，并定義公路網(wǎng)絡(luò)魯棒性的強(qiáng)度等級，反映了公路網(wǎng)絡(luò)結(jié)構(gòu)與城市空間體系的關(guān)系。葉堃軍等[3]對中國高速鐵路網(wǎng)絡(luò)進(jìn)行了基礎(chǔ)復(fù)雜網(wǎng)絡(luò)特性分析，反映了高速鐵路網(wǎng)絡(luò)特性與城市規(guī)模、地理、經(jīng)濟(jì)等外部因素有關(guān)。目前網(wǎng)絡(luò)結(jié)構(gòu)領(lǐng)域主要針對網(wǎng)絡(luò)演化和模型構(gòu)造[4-8]，本文創(chuàng)新性地提出從航路網(wǎng)絡(luò)結(jié)構(gòu)中心性角度出發(fā)，構(gòu)建完整航路網(wǎng)路結(jié)構(gòu)和復(fù)雜拓?fù)淠Ｐ停謩e從度中心性、中介中心性和結(jié)構(gòu)中心性這3個角度分析航路網(wǎng)絡(luò)，并從中介性和緊密性角度對航路關(guān)鍵節(jié)點進(jìn)行識別，從中得出對航路網(wǎng)絡(luò)效能發(fā)揮具有重要支撐作用的航路點。

1 航路網(wǎng)絡(luò)結(jié)構(gòu)的構(gòu)建

本文研究的國內(nèi)航路網(wǎng)絡(luò)，以最近更新的國內(nèi)航路圖為基礎(chǔ)，在PAJEK中構(gòu)建航路網(wǎng)絡(luò)結(jié)構(gòu)[9]，并假設(shè)2個航段節(jié)點間有且僅有一條航段時，除這2個節(jié)點外該航段其它轉(zhuǎn)彎點不予考慮。實際運(yùn)行中若多條不同高度層航路的交叉點處無導(dǎo)航臺或強(qiáng)制報告點，在網(wǎng)絡(luò)結(jié)構(gòu)構(gòu)建過程中依然將其列為航路節(jié)點。由此得到的航路網(wǎng)絡(luò)結(jié)構(gòu)共計569條航段，567個航路節(jié)點，每條航段均考慮為雙向無序。

依照中國航路網(wǎng)絡(luò)結(jié)構(gòu)示意圖(圖1)，將航路網(wǎng)絡(luò)鄰接矩陣.net數(shù)據(jù)(圖2)導(dǎo)入PAJEK，得到圖3的基于鄰接航路點的航路復(fù)雜網(wǎng)絡(luò)拓?fù)淠Ｐ汀?/p>

圖1 中國航路網(wǎng)絡(luò)結(jié)構(gòu)示意圖

圖2 PAJEK計算航路網(wǎng)絡(luò)結(jié)構(gòu)中心性參數(shù)

圖3 基于鄰接航路點的航路復(fù)雜網(wǎng)絡(luò)模型示意圖

2 航路網(wǎng)絡(luò)結(jié)構(gòu)中心性分析

為了分析航路網(wǎng)絡(luò)靜態(tài)結(jié)構(gòu)與運(yùn)行單元之間的關(guān)系，進(jìn)而考慮改善航路網(wǎng)絡(luò)結(jié)構(gòu)，需要對實際網(wǎng)絡(luò)的結(jié)構(gòu)特征有很好的了解?；谧罱碌闹袊裼煤娇蘸铰穲D，構(gòu)建完整的靜態(tài)航路網(wǎng)絡(luò)結(jié)構(gòu)，充分保證仿真結(jié)果的時效性和應(yīng)用性，為參數(shù)計算提供最完整的數(shù)據(jù)基礎(chǔ)[10-11]。本文首次對整個國內(nèi)航路網(wǎng)絡(luò)分別從點度中心性、中介中心性和緊密中心性這3個典型中心性度量方法進(jìn)行分析。

在航路網(wǎng)絡(luò)節(jié)點中心性指標(biāo)仿真計算過程中，VOR、DME、VOR和DME合裝、NDB、強(qiáng)制報告點均列為節(jié)點計算，且航路均考慮雙向無序。

2.1 度中心性分析

作為航段網(wǎng)絡(luò)節(jié)點，度是指該節(jié)點與其它航段節(jié)點連接的邊的數(shù)量，通常節(jié)點度值大小反映了該節(jié)點的通達(dá)性和規(guī)模，節(jié)點i的度記為Ai=∑aij。網(wǎng)絡(luò)中度為k的節(jié)點數(shù)占網(wǎng)絡(luò)節(jié)點總數(shù)的比例叫度分布，記為p(A)。

度中心性方法[12]基于這樣一種思想：重要頂點是那些擁有與其它頂點有較多的連接邊數(shù)的頂點。顯然，一個圖的頂點重要性能依據(jù)它們度的大小進(jìn)行排序。

點X的度數(shù)中心度就是與點X直接相連的其他點的個數(shù)。如果一個點與許多點直接相連，就說該點具有較高的度數(shù)中心度。如果某點具有最高的度數(shù)，則稱該點居于網(wǎng)絡(luò)的中心。擁有權(quán)力在測量度數(shù)中心度的時候根據(jù)的是與該點直接相連的點數(shù)，并不考慮間接相連的點。因此，所測量出來的中心度可以稱為“局部中心度”。在有向圖中，每個點的度數(shù)可分為點入度和點出度。一個點的點入度是進(jìn)入該點的其他點的個數(shù)，即該點得到的直接關(guān)系數(shù)。一個點的點出度是該點直接發(fā)出的關(guān)系數(shù)。

航路網(wǎng)絡(luò)上任意節(jié)點,其度值反映了該航段節(jié)點直接相連接的航段節(jié)點數(shù)量,即忽略節(jié)點間連接上的權(quán)值,只關(guān)注連接本身，節(jié)點度值越大說明該節(jié)點具有較高的連通度。在實際地理空間上具有較好的交通條件[13],也可能是實際航路網(wǎng)絡(luò)中的樞紐或轉(zhuǎn)場點。從圖4中航段節(jié)點度和度分布示意圖可以看出，我國航路網(wǎng)絡(luò)節(jié)點分布大致趨于正態(tài)分布，分布較為合理。

圖4 航段節(jié)點度和度分布示意圖

2.2 中介中心性分析

中介中心性的定義是通過假設(shè)信息僅僅沿著最短路徑來傳播，如果njk是連接節(jié)點j和k之間最短路徑數(shù)目，njk(i)是連接節(jié)點j和k之間包含著節(jié)點i的最短路徑數(shù)目，那么節(jié)點i的中介中心性定義為:

其中，G為節(jié)點集，N為G中節(jié)點個數(shù)。

一般來說，如果很多人要想建立聯(lián)系必須要經(jīng)過某個人，則可以認(rèn)為此人居于重要地位，因為“處于這種位置的個人可以通過控制或者曲解信息的傳遞而影響群體”。因此，另一個刻畫行動者個體中心度的指標(biāo)是中介中心度，它測量的是行動者對資源控制的程度。具體地說，如果一個點處于許多其他點對的最短的途徑上，就說該點具有較高的中介中心度。

針對航路網(wǎng)絡(luò)，任意一個航路點的中介中心度，都是由該點擔(dān)任其它2個點直接最短路徑的橋梁的次數(shù)。一個點充當(dāng)“中介”的次數(shù)越高，它的中介中心度就越大。處于中介位置的點通過控制其它航班信息流的傳遞從而影響整個航路網(wǎng)絡(luò)的運(yùn)行，因而航路點的中介中心度是該點對整個航路網(wǎng)絡(luò)結(jié)構(gòu)資源的控制程度。

航路節(jié)點的中介中心性數(shù)值反映了節(jié)點對網(wǎng)絡(luò)中運(yùn)行流量的承載程度，與度中心性有所不同的是，中介中心性側(cè)重于衡量節(jié)點在銜接局部社團(tuán)網(wǎng)絡(luò)模塊之間的重要性。如圖5所示，對于九亭航路點而言，度值中心性在整個航路網(wǎng)絡(luò)來看并不高，但從上海管制區(qū)03號扇區(qū)來看，九亭的作用非常凸顯。假設(shè)網(wǎng)絡(luò)運(yùn)行的飛行器均在穩(wěn)定運(yùn)輸時都是采用最短路徑，那么九亭在分擔(dān)浦東以西或西南、庵東以北、南潯或無錫以東的流量的作用就十分關(guān)鍵。如若取消九亭所在位置的航路點，勢必會造成整個3號管制扇區(qū)擁堵、繞行、延誤等交通閉塞現(xiàn)象。

圖5 中國航路網(wǎng)絡(luò)結(jié)構(gòu)局部示意圖

2.3 緊密中心性分析

一個點的緊密中心度是圖中該點與其他各節(jié)點之間的短程線距離之和,其測量公式為:

其中d(ni,nj)為ni與nj之間的短程線距離。

點X的緊密中心度是一種針對不受他人控制的測度。如果這個點與網(wǎng)絡(luò)中所有其他點的“距離”都很短，則稱該點具有較高的整體中心度,又叫做緊密中心度。在圖中，這樣的點與許多其他點都“緊密”。當(dāng)人們的研究不需要對直接關(guān)系進(jìn)行考察的時候，緊密中心度就是一個有用的概念。根據(jù)緊密中心度的含義可以看出，與中心點距離最遠(yuǎn)的行動者也在信息資源、權(quán)力、聲望以及影響方面最弱。根據(jù)定義容易知道，緊密中心度的值越大，越說明該點不是網(wǎng)絡(luò)的核心點。

緊密中心度依據(jù)網(wǎng)絡(luò)中各節(jié)點之間的緊密性和距離而測量的中心度。所測量出的總距離越短,說明網(wǎng)絡(luò)的緊密中心度越高,它可表明某個航路節(jié)點跟其他節(jié)點之間多么密切，側(cè)重于節(jié)點的依賴性。航路節(jié)點緊密中心性越高，則該點到其他節(jié)點的平均最短距離越短。而平均最短距離短意味著網(wǎng)絡(luò)運(yùn)行得越快，在運(yùn)行時經(jīng)過的中途節(jié)點越少，這種航路節(jié)點一般都是交通樞紐所在。

表1 航路網(wǎng)絡(luò)結(jié)構(gòu)中心性參數(shù)統(tǒng)計分析

統(tǒng)計信息樣本個數(shù)樣本均值最大值最小值眾數(shù)度值5677.57718.0002.0008.000中介度值5670.0620.2410.0000.000緊密度值5670.0990.1430.0040.004網(wǎng)絡(luò)約束系數(shù)5670.4481.1250.1541.000聚類系數(shù)5670.3111.0000.0000.333

圖6 航路網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)分布

由表1和圖6所示，粗線為航路網(wǎng)絡(luò)緊密中心性分布，細(xì)線為中介中心性分布，為方便統(tǒng)計分析，將中介中心性參數(shù)進(jìn)行歸一化處理。緊密度值的均值為0.0994，結(jié)合航路網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)分布圖，顯然，絕大多數(shù)航路節(jié)點的緊密度值維持在0.1或0.1以下，相較于航路邊界節(jié)點0.14左右的緊密度值，整體緊密度值較小，網(wǎng)絡(luò)整體緊密中心度較高，表明多數(shù)節(jié)點在網(wǎng)絡(luò)運(yùn)輸中與其他節(jié)點聯(lián)系密切，整個航路網(wǎng)絡(luò)緊密性較好。另一方面，為了更加直觀的觀察航路網(wǎng)絡(luò)中介中心性與緊密中心性的計算結(jié)果，將航路網(wǎng)絡(luò)鄰接矩陣數(shù)據(jù)導(dǎo)入復(fù)雜網(wǎng)絡(luò)可視化平臺PAJEK，得到如圖7所示的航路網(wǎng)絡(luò)結(jié)構(gòu)中心性參數(shù)拓?fù)涫疽鈭D。

圖7所示，航路網(wǎng)絡(luò)中介中心性與緊密中心性有著明顯的不同，中介中心性側(cè)重于經(jīng)過該點的最短路徑，據(jù)此得到的拓?fù)涫疽鈭D中，節(jié)點大小有著明顯的區(qū)分，如商縣、太原、百色、通遼等，歷來屬于交通繁忙航路點，在圖中明顯有別于邊際航路點。而緊密中心性側(cè)重于該點到其他節(jié)點的最短路徑，據(jù)此圖中可以看出航路網(wǎng)絡(luò)各個節(jié)點的緊密中心性差異微弱。

圖7 基于復(fù)雜非線性網(wǎng)絡(luò)的航路網(wǎng)絡(luò)結(jié)構(gòu)中心性參數(shù)拓?fù)涫疽鈭D

3 航路網(wǎng)絡(luò)關(guān)鍵節(jié)點識別

關(guān)于網(wǎng)絡(luò)關(guān)鍵節(jié)點的定義并沒有一個統(tǒng)一的界定標(biāo)準(zhǔn)，傳統(tǒng)的關(guān)鍵節(jié)點研究主要考慮以下3個方面：1)通行能力，即將路網(wǎng)中的關(guān)鍵節(jié)點定義為那些通行能力低于交通需求的、發(fā)生交通擁堵概率較大的節(jié)點；2)從路網(wǎng)的可靠性出發(fā)，將在網(wǎng)絡(luò)節(jié)點受到攻擊時路網(wǎng)可靠性發(fā)生較大變化的節(jié)點納入關(guān)鍵節(jié)點的范圍；3)從路網(wǎng)的連通性出發(fā)，將對路網(wǎng)連通效率和通達(dá)性起到關(guān)鍵作用的節(jié)點納入關(guān)鍵節(jié)點的考慮范圍。

本文提出的基于結(jié)構(gòu)中心性的關(guān)鍵節(jié)點識別，主要依賴復(fù)雜網(wǎng)絡(luò)方面的內(nèi)容，著手點是網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)特性，點度中心性側(cè)重于一個航路點與其他航路點直接交換信息的能力，而中介中心性和緊密中心性側(cè)重于一個航路點控制路網(wǎng)中其他航路點之間交換信息的能力，它們依賴于信息發(fā)出者和網(wǎng)絡(luò)中的所有接受者之間的關(guān)系，而不僅僅是與鄰點之間的直接關(guān)系。一般來說，如果關(guān)注信息交換活動，可采用點度中心性；如果研究對信息的控制，可采用中介中心性；如果分析相對于信息傳遞的獨(dú)立性和有效性，可采用緊密中心性。這是傳統(tǒng)網(wǎng)絡(luò)關(guān)鍵節(jié)點研究中最主要的一點區(qū)別，即基于結(jié)構(gòu)中心性的關(guān)鍵節(jié)點研究側(cè)重于節(jié)點與節(jié)點之間交換信息的方式。

在將航路網(wǎng)絡(luò)鄰接矩陣導(dǎo)入PAJEK的過程中，PAJEK默認(rèn)將節(jié)點自動按矩陣元素的排列順序進(jìn)行數(shù)字標(biāo)簽化，故PAJEK計算的任何一個航路點的標(biāo)簽都與矩陣元素一一對應(yīng)，同時每個航路點在AutoCAD中都有對應(yīng)的相對坐標(biāo)(如表2所示)，即矩陣元素、節(jié)點標(biāo)簽、節(jié)點坐標(biāo)三者一一對應(yīng)?；诘?章對航路網(wǎng)絡(luò)結(jié)構(gòu)中心性的分析，將中介中心性和緊密中心性參數(shù)值由大到小進(jìn)行排列，并將前二十的航路點或強(qiáng)制報告點在AutoCAD中通過輸入坐標(biāo)進(jìn)行位置鎖定，示意圖如圖8、圖9所示。

表2 航路點相對坐標(biāo)(部分)

航路點標(biāo)簽相對坐標(biāo)X相對坐標(biāo)Y黑河3760.7173839.813海青3648.2074381.263海拉爾3542.5943368.060齊齊哈爾3399.7763678.483IKITI3233.8613520.263烏蘭浩特3269.3603569.014水泉3253.9483862.944哈爾濱3275.0563873.091牡丹江3225.4714128.831BISUN3129.5214275.460LEPNI3152.7824093.429

圖8 基于中介中心性的航路網(wǎng)絡(luò)關(guān)鍵節(jié)點識別示意圖

航路點的中介中心度表明的是該點在多大程度上控制其它點之間的信息交換。如果一個點的中介中心度為0，意味著該點不能控制任何其它點，處于網(wǎng)絡(luò)的邊緣；如果一個點的中介中心度為1，意味著該點可以百分之百地控制任何其它航路點，它處于航路網(wǎng)絡(luò)的核心，擁有很大的權(quán)力。即，中介中心度越大，該點在整個航路了網(wǎng)絡(luò)中控制周邊其它點的能力就越強(qiáng)。根據(jù)定義容易知道，緊密中心度的值越大，越說明該點不是網(wǎng)絡(luò)的核心點。

圖9 基于緊密中心性的航路網(wǎng)絡(luò)關(guān)鍵節(jié)點識別示意圖

表3 航路重要節(jié)點排序

節(jié)點重要性排序中介中心性緊密中心性1周口周口2寧岡臨汾3九亭商縣4商縣魏縣5太原河口6百色新鄭7魏縣阜陽8昆明通遼9通遼南陽10高要九亭11臨汾錫林浩特12英德恩施13平洲寧岡14貴陽TAMIX15P113DUBAG16老糧倉APUKO17合肥寧陜18來賓南陽19TEMOL太原20銀川襄樊

如表3所示，如周口導(dǎo)航臺所在航路點，歷來是航路網(wǎng)絡(luò)運(yùn)行的瓶頸點，特別是遇到雷雨、備降、改航等特殊飛行情況時，該點更是阻塞。由于側(cè)重點不同，得到的網(wǎng)絡(luò)中介中心性與緊密中心性的關(guān)鍵節(jié)點也不同，基于中介中心性的關(guān)鍵節(jié)點，例如貴陽導(dǎo)航臺所在航路點在分擔(dān)懷化以西、昆明以東的流量的作用十分關(guān)鍵，但其緊密中心性并不明顯。基于緊密中心性的關(guān)鍵節(jié)點，如九亭導(dǎo)航臺所在航路點在分擔(dān)浦東以西或西南、庵東以北、南潯或無錫以東的流量時地位十分重要，但其中介中心性不突出。周口導(dǎo)航臺所在航路點是H14航路與A461航路在鄭州管制區(qū)南扇區(qū)的交叉點，H14、A461均為主干航路，周邊又有H10、A593、R343等眾多主干航路和直線航路，周口導(dǎo)航臺航路點在銜接主主、主支、支支航路中處于核心位置，一直以來也是復(fù)雜程度較高、管制負(fù)荷較大的交叉口。由此，基于中介中心性和緊密中心性的節(jié)點識別結(jié)果與實際運(yùn)行情況趨于一致。

4 結(jié)束語

本文從航路網(wǎng)絡(luò)物理結(jié)構(gòu)角度出發(fā)，研究了在路網(wǎng)結(jié)構(gòu)中心性下識別關(guān)鍵航路節(jié)點的方法。

1)構(gòu)建完整航路網(wǎng)絡(luò)結(jié)構(gòu)。以最近更新的國內(nèi)航路圖為基礎(chǔ)，在PAJEK中構(gòu)建航路網(wǎng)絡(luò)結(jié)構(gòu)。為保證鄰接航路點矩陣數(shù)據(jù)有效性，2個航段節(jié)點間有且僅有一條航段時，除這2個節(jié)點外該航段其它轉(zhuǎn)彎點不予考慮。實際運(yùn)行中若多條不同高度層航路的交叉點處無導(dǎo)航臺或強(qiáng)制報告點，在網(wǎng)絡(luò)結(jié)構(gòu)構(gòu)建過程中依然將其列為航路節(jié)點。

2)將航路網(wǎng)絡(luò)中介中心性與緊密中心性分析結(jié)果可視化?；趶?fù)雜非線性網(wǎng)絡(luò)的航路網(wǎng)絡(luò)結(jié)構(gòu)中心性參數(shù)拓?fù)涫疽鈭D不僅可以將節(jié)點結(jié)構(gòu)中心性特征可視化，而且在比較節(jié)點結(jié)構(gòu)中心性差異時便捷迅速。

3)提出了基于結(jié)構(gòu)中心性的路網(wǎng)關(guān)鍵節(jié)點識別方法。從不同的結(jié)構(gòu)中心性角度提取路網(wǎng)關(guān)鍵節(jié)點并排序，通過AutoCAD鎖定關(guān)鍵節(jié)點并將其可視化，與現(xiàn)有實際運(yùn)行情況對比，比較一致，方法易操作、更直觀。