謝本凱,李 琴,黃龔迪,林??#钗咫p
(1.鄭州航空工業(yè)管理學(xué)院 管理工程學(xué)院,河南 鄭州 450046;2.鄭州航空工業(yè)管理學(xué)院 信息管理學(xué)院,河南 鄭州 450046;3.航空經(jīng)濟發(fā)展河南省協(xié)同創(chuàng)新中心,河南 鄭州 450000)
民航網(wǎng)絡(luò)是實現(xiàn)航空交通運輸?shù)幕A(chǔ)條件,它的穩(wěn)定性和規(guī)范化是國家在航空領(lǐng)域發(fā)展水平的一個直觀體現(xiàn),其與其它類型的交通運輸網(wǎng)絡(luò)有較大不同,無論是在科技水平、空間跨度還是推動經(jīng)濟發(fā)展方面都更加亮眼突出。我國民航業(yè)處于成長時期,民航網(wǎng)絡(luò)在工作效率和容錯度等方面還不足以滿足社會發(fā)展的需要,有明顯的可提升空間。由于各種人為因素和自然因素,無法避免和預(yù)測的不穩(wěn)定因素都可能對我國民航網(wǎng)絡(luò)帶來沖擊和考驗。怎么使我國民航網(wǎng)絡(luò)改善優(yōu)化、提高效率,從而大大提升我國民航競爭力是一個值得探討的方向。
20 世紀(jì)中期隨機圖理論被提出,為復(fù)雜網(wǎng)絡(luò)研究打開了大門。20世紀(jì)末Watts[1]和Barabasi[2]分別提出了被視為為復(fù)雜網(wǎng)絡(luò)研究掀開新篇章的小世界網(wǎng)絡(luò)模型和無標(biāo)度網(wǎng)絡(luò)模型。隨后,關(guān)于復(fù)雜網(wǎng)絡(luò)的剖析也開始漸漸深入,與此同時越來越多的學(xué)者將該理論應(yīng)用于對現(xiàn)實網(wǎng)絡(luò)的研究中。Oriol Lordan[3]等對全球民航網(wǎng)絡(luò)的統(tǒng)計參數(shù)進(jìn)行了研究,并分析了其魯棒性,結(jié)果發(fā)現(xiàn)運用介數(shù)中心性自適應(yīng)策略可以精準(zhǔn)找出重要機場;Wei[4]等利用荷蘭中壓電力網(wǎng)的數(shù)據(jù),研究了不同信息網(wǎng)拓?fù)浜蛢深惞舴绞綄﹄娏PS 連鎖故障的影響,得出小世界網(wǎng)絡(luò)的信息網(wǎng)拓?fù)淠苁乖摼W(wǎng)絡(luò)魯棒性更好;Lara-Cabrera[5]等利用復(fù)雜網(wǎng)絡(luò)的拓?fù)湫再|(zhì)分析CIG網(wǎng)絡(luò),研究了大規(guī)模結(jié)構(gòu)、增長機制和其他特征之間的協(xié)作模式。徐偉舉[6]等人分析了在動態(tài)和靜態(tài)攻擊兩種模式下美國航空網(wǎng)絡(luò)、SW 網(wǎng)絡(luò)和BA 網(wǎng)絡(luò)的抗毀性;魏震波[7]等總結(jié)歸納了在電網(wǎng)分析中應(yīng)用到的一些研究成果,并針對研究方法和成果的質(zhì)疑進(jìn)行了較全面的分析;田慶飛[8]基于復(fù)雜網(wǎng)絡(luò)理論和交通擁堵分析,對城市公交網(wǎng)絡(luò)生成與優(yōu)化的相關(guān)算法與方法進(jìn)行了研究。而本文從隨機攻擊和蓄意攻擊兩個方面,采用平均路徑長度、介數(shù)等參數(shù)分析了中國民航網(wǎng)絡(luò)的整體魯棒性。
民航網(wǎng)絡(luò)可以被描述為一個二元組G=(V,E),其中V={v1,v2,…,vn}是機場的節(jié)點集,E={e1,e2,…,em}是航線的邊集,vi代表節(jié)點,ej代表邊。用|V|表示V中的節(jié)點個數(shù),|E|表示E的邊數(shù)。在本文中,它被定義為無向無權(quán)網(wǎng)絡(luò),也就是說它的節(jié)點(va,vb)和(vb,va)表示同一條邊,并且每條邊不賦予權(quán)值。
它可以描述民航網(wǎng)絡(luò)中的平均分離程度。在所有連通節(jié)點va和vb的路徑中,節(jié)點最少的那一條被稱為兩點間的最短路徑,而最短路徑的邊數(shù)被稱為節(jié)點va與vb之間的最短距離,它是指網(wǎng)絡(luò)中所有最短距離里的最大數(shù)。而所有節(jié)點對的平均值就是平均距離L,一般計算公式為:
它是用來度量網(wǎng)絡(luò)中節(jié)點聚集情況的參數(shù),表現(xiàn)了網(wǎng)絡(luò)的簇?fù)頎顟B(tài)。通??梢杂眠@一系數(shù)來描述網(wǎng)絡(luò)局部的結(jié)構(gòu)性質(zhì)。記有ka個節(jié)點與va直接連接,則在無向網(wǎng)絡(luò)中ka個節(jié)點最多可能有ka(ka-1)/2 條邊,而真實存在的邊數(shù)記為Ma,可將節(jié)點va的聚集系數(shù)定義為:
本文研究的我國民航網(wǎng)絡(luò),機場的簇?fù)砬闆r就是節(jié)點的聚集系數(shù)。若機場的聚集系數(shù)大,說明它與其周圍所連接的機場所構(gòu)成的網(wǎng)絡(luò)比較密集。
度在復(fù)雜網(wǎng)絡(luò)中是用來描述節(jié)點特性的基礎(chǔ)參數(shù),節(jié)點Va的相鄰邊數(shù)目就是它的度。度值的大小可以說明節(jié)點在網(wǎng)絡(luò)中的重要程度。引用鄰接矩陣C去定義它,那么C的某一行或某一列非零元素個數(shù)就是節(jié)點的度,用公式表現(xiàn)如下:
其中Cab表示矩陣C中非零元素。大多數(shù)真實網(wǎng)絡(luò)節(jié)點度符合一定的概率分布,度的分布也是可以用來描述復(fù)雜網(wǎng)絡(luò)統(tǒng)計特征的重要參數(shù)。在本文中P(k)就是用來描述中國民航網(wǎng)絡(luò)中航線是k的機場占總機場數(shù)的比率,同時本文利用累計度分布表示度的分布狀況。
連通子圖是指在網(wǎng)絡(luò)中的一個子圖內(nèi),任意兩個節(jié)點間都最少存在一條連通的邊。在一個復(fù)雜網(wǎng)絡(luò)中,可能有許多相對獨立的連通子圖存在。而當(dāng)無論在該子圖中加入任何另外的節(jié)點都會影響這個子圖的連通性時,這個子圖被稱為最大連通子圖,也稱為連通分支。連通圖的連通程度就是連通度,它分為點連通度和邊連通度,一般來說連通度越好,這個網(wǎng)絡(luò)圖也就越穩(wěn)定。
小世界網(wǎng)絡(luò)是指在一個結(jié)構(gòu)很大的網(wǎng)絡(luò)中,節(jié)點之間的連接相對密切的情況,它的統(tǒng)計特點在于聚集系數(shù)大,但平均距離較?。辉趶?fù)雜網(wǎng)絡(luò)中的節(jié)點度分布如果符合冪律分布,就被稱為無標(biāo)度網(wǎng)絡(luò)。
本文以中國民航網(wǎng)絡(luò)中的機場作為節(jié)點,并將機場之間的航線作為邊進(jìn)行建模。以2017年民航機場吞吐量排名的報告中我國現(xiàn)存機場為基準(zhǔn),共216個機場節(jié)點,經(jīng)統(tǒng)計共有2 363條無向邊。
由于中國民航網(wǎng)絡(luò)的節(jié)點復(fù)雜性、結(jié)構(gòu)復(fù)雜性和運行復(fù)雜性等會導(dǎo)致各種不確定因素產(chǎn)生,本文對實際民航網(wǎng)絡(luò)做出如下設(shè)定:
(1)模型中中國民航網(wǎng)絡(luò)的邊就是民航的運行線路,并且所有邊都是無向邊;
(2)研究對象僅限于機場節(jié)點和機場之間的民航運輸線路,不考慮其他的相關(guān)對象;
(3)民航航線的拓?fù)涮匦跃嗤?,即不考慮航空效率是否不同,也不考慮機場功能參數(shù)的不同,也就是說在進(jìn)行魯棒性分析時網(wǎng)絡(luò)中的所有節(jié)點和均是無權(quán)的;
(4)對于擁有兩個或者超過兩個機場的城市均視為一個節(jié)點,即將機場合并使圖相應(yīng)簡化。
機場節(jié)點度K表示的是與它有航線的機場的數(shù)目。經(jīng)計算得出中國民航網(wǎng)絡(luò)中的總度數(shù)為4 290,那么總的平均度就約為19.86,也就是說平均每一個機場與其他節(jié)點直接連接的航線約有20條。對數(shù)據(jù)進(jìn)行統(tǒng)計分析可以得出圖1的度分布曲線圖。
圖1 度分布圖
中國民航網(wǎng)絡(luò)的平均路徑長度為2.41,這說明每兩個城市的機場之間通過約2 次的轉(zhuǎn)機就可以相互到達(dá),而明顯的是該網(wǎng)絡(luò)的聚類系數(shù)較大,表現(xiàn)出強聚集性。由這兩個特點可知其滿足小世界特性,而在度分布圖可以直觀的觀察到曲線中的最高點屬于度數(shù)較小的節(jié)點,曲線的最低點屬于度數(shù)較大的節(jié)點,說明該網(wǎng)絡(luò)中有許多邊數(shù)較少的節(jié)點和少量邊數(shù)眾多的集散節(jié)點,這明顯是無標(biāo)度網(wǎng)絡(luò)的特征。綜合而言,它具備小世界特性,但更多地體現(xiàn)無標(biāo)度特性。表1是對近些年來相關(guān)文獻(xiàn)中中國民航網(wǎng)絡(luò)的特征參數(shù)值變化情況進(jìn)行的統(tǒng)計。
表1 中國民航網(wǎng)絡(luò)統(tǒng)計參數(shù)特征比較
從表中數(shù)據(jù)對比可知,我國民航機場數(shù)不斷增加,從2005年至今已經(jīng)擴建了將近100個機場;機場的大量增加使得網(wǎng)絡(luò)中的航線也不斷擴充,每個節(jié)點的度值增大,所以網(wǎng)絡(luò)的平均度也逐漸增大;而平均路徑長度在2012年前均不斷減小,但2018年卻大幅度增加,究其原因可能是增加機場時航線設(shè)定不夠規(guī)范、合理。
網(wǎng)絡(luò)魯棒性一般指其節(jié)點或邊被破壞的時候,網(wǎng)絡(luò)能繼續(xù)工作的能力,也叫做容錯能力、抗毀性。網(wǎng)絡(luò)的魯棒性也與其規(guī)模的大小有關(guān),若網(wǎng)絡(luò)的規(guī)模越大,那么它可以替代的邊就越多,但如果規(guī)模過大,它發(fā)生意外和故障的幾率也比一般的網(wǎng)絡(luò)大得多。
本文中國民航網(wǎng)絡(luò)的魯棒性為在該網(wǎng)絡(luò)正常運轉(zhuǎn)或者受到兩類攻擊時,具有一定的抵抗能力,這種能力的強弱程度稱為魯棒程度。當(dāng)遭受不在承受能力范圍內(nèi)的意外攻擊時,網(wǎng)絡(luò)便無法保持原狀。
分析中國民航網(wǎng)絡(luò)的魯棒性時,本文基于移出網(wǎng)絡(luò)中節(jié)點從而引發(fā)故障的情況,對網(wǎng)絡(luò)整體進(jìn)行分析。當(dāng)節(jié)點突然遭受襲擊時,整個網(wǎng)絡(luò)會發(fā)生一定的變化。對于節(jié)點的攻擊分為隨機攻擊和蓄意攻擊兩種,隨機攻擊的發(fā)生可能是由于一些意外如天氣原因等,這類攻擊一般可以自我修復(fù)或重新連接以抵抗外部干擾;而蓄意攻擊的情況,一般會有很強的目的性,使沒有準(zhǔn)備好的節(jié)點受到嚴(yán)重破壞,無法正常工作,深度影響網(wǎng)絡(luò)功能并大大降低了網(wǎng)絡(luò)維持自我安全的能力,恢復(fù)工作也會進(jìn)行的很困難。本文為了更全面的分析中國民航網(wǎng)絡(luò),將從隨機和蓄意兩方面去考慮,以提高容錯能力。
本文選取平均路徑長度、最大連通度與介數(shù)作為評估指標(biāo),對中國民航網(wǎng)絡(luò)的魯棒性進(jìn)行分析。
(1)中國民航網(wǎng)絡(luò)平均路徑長度L。它是指網(wǎng)絡(luò)中任兩個不同機場節(jié)點之間的最短連接距離的平均值。用n 代表網(wǎng)絡(luò)的節(jié)點數(shù),dab表示節(jié)點a 與節(jié)點b之間的距離,則:
(2)最大連通度Gmax。這里指的是中國民航網(wǎng)絡(luò)在受到干擾以后,它所有依然連接且還能正常運轉(zhuǎn)的節(jié)點的網(wǎng)絡(luò)中,所含最多節(jié)點數(shù)的集團中節(jié)點數(shù)占有其他剩余節(jié)點的比例:
(3)介數(shù)B。它是用來反映中國民航網(wǎng)絡(luò)全局性的指標(biāo)。在網(wǎng)絡(luò)中有一些節(jié)點雖然度較小,但卻是某兩個集團的中間連接點,那么它也同樣很重要,用介數(shù)便可以定義這樣的節(jié)點。本文在進(jìn)行蓄意攻擊時,會選取介數(shù)值大的節(jié)點依次進(jìn)行攻擊,再進(jìn)行特征參數(shù)分析。
針對中國民航網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和其本身的復(fù)雜性,本節(jié)總結(jié)出了研究該網(wǎng)絡(luò)魯棒性的主要步驟,如圖2所示。
圖2 魯棒性分析仿真流程圖
在實驗中模擬隨機攻擊時,首先進(jìn)行隨機節(jié)點選取,依次將故障點數(shù)設(shè)為節(jié)點總數(shù)的5%、10%、15%,并每次進(jìn)行5 次實驗取參數(shù)平均值以得到結(jié)果;而在模擬蓄意攻擊時,先計算得出每個點的介數(shù)值,再按介數(shù)值由高到低排序,并從數(shù)值高的開始同樣依次移出節(jié)點總數(shù)的5%、10%、15%。特別說明的是,本文利用數(shù)字表示每一個城市的機場,機場間的航線用如A—B的形式表示,模擬節(jié)點遭受攻擊時便會將該節(jié)點所在的航線全部刪除。
中國民航網(wǎng)絡(luò)模型中節(jié)點總數(shù)為216,那么由216×5%、216×10%和216×15%可得出攻擊的節(jié)點數(shù)為10 個、21 個和32 個。在仿真實驗的隨機攻擊中,移除10 個節(jié)點平均有兩個孤立節(jié)點,移除21 個節(jié)點和32 個節(jié)點均平均有3 個孤立節(jié)點;而蓄意攻擊中,移除10 個節(jié)點后有12 個孤立節(jié)點出現(xiàn),移除21個節(jié)點后有18個孤立節(jié)點出現(xiàn),移除32個節(jié)點后有32個孤立節(jié)點出現(xiàn)。具體如圖3-圖5所示。
圖3 平均路徑長度變化趨勢
在未進(jìn)行兩種攻擊前,中國民航網(wǎng)絡(luò)的平均路徑長度為2.412,最大連通度為1,介數(shù)值為0.15。而在進(jìn)行仿真模擬攻擊后,每個數(shù)值都發(fā)生了一定的變化。顯而易見的是,蓄意攻擊后無論是哪一種參數(shù)增大或減小的趨勢相較于隨機攻擊都更加劇烈。
(1)平均路徑長度L。它是可以用來描述一個復(fù)雜網(wǎng)絡(luò)中節(jié)點間連接密切程度情況的統(tǒng)計參數(shù)。若平均路徑長度數(shù)值小,則說明節(jié)點之間關(guān)系密切,從某一節(jié)點到其他節(jié)點所用的時間更少,網(wǎng)絡(luò)的整體連接性較好;若平均路徑長度數(shù)值較大,則說明節(jié)點若想與某一非鄰邊節(jié)點有聯(lián)系要經(jīng)過更多的邊和節(jié)點,在這期間意外情況很可能發(fā)生,這在中國民航網(wǎng)絡(luò)中表現(xiàn)為從某機場出發(fā)要去某地的話周轉(zhuǎn)次數(shù)將變多,所要消耗的時間也更長。由上一節(jié)的仿真結(jié)果可以分析出:
圖4 最大連通度變化趨勢
圖5 介數(shù)變化趨勢
在隨機攻擊模式下,盡管移出的節(jié)點數(shù)不斷增加,該網(wǎng)絡(luò)的平均路徑長度的波動幅度卻并不大,對于整個網(wǎng)絡(luò)來說幾乎沒有什么影響;而在蓄意攻擊模式下,中國民航網(wǎng)絡(luò)的平均路徑長度隨著移除節(jié)點數(shù)變多,數(shù)值不斷變大。由此可見中國民航網(wǎng)絡(luò)在遭遇蓄意攻擊時,若網(wǎng)絡(luò)節(jié)點不斷減少,系統(tǒng)內(nèi)節(jié)點間的聯(lián)系會不斷的減弱,網(wǎng)絡(luò)會顯得更加脆弱,所以該指標(biāo)參數(shù)反映了網(wǎng)絡(luò)魯棒性的降低。不僅如此,由統(tǒng)計曲線可以看出,在蓄意攻擊模式下平均路徑長度增大的速度相比之下也較快。也就是說,當(dāng)故意移除重要性大的節(jié)點時,網(wǎng)絡(luò)中受影響的節(jié)點會不斷增多,網(wǎng)絡(luò)內(nèi)的故障會像病毒一樣傳染開來。
(2)最大連通度。這一統(tǒng)計參數(shù)可以用來反映當(dāng)網(wǎng)絡(luò)受到攻擊后,該網(wǎng)絡(luò)中依舊能正常工作的集團里包含的最多節(jié)點數(shù)。當(dāng)網(wǎng)絡(luò)的最大連通度為1時,表示網(wǎng)絡(luò)處于正常狀態(tài)。當(dāng)最大連接度不斷降低時,說明網(wǎng)絡(luò)在受到破壞后規(guī)模在不斷縮小,使得它無法將整個網(wǎng)絡(luò)的所有節(jié)點都建立起連接,節(jié)點之間的溝通力在下降,系統(tǒng)也處于魯棒性差的狀態(tài)。由上一節(jié)關(guān)于最大連通度的仿真結(jié)果可以分析出:
在隨機攻擊的模式下,盡管移出的節(jié)點在不斷增多,網(wǎng)絡(luò)的最大連通度卻變化不大,基本處于比較穩(wěn)定的狀態(tài),當(dāng)該網(wǎng)絡(luò)中某幾個節(jié)點發(fā)生意外時,對整個網(wǎng)絡(luò)的最大連通度幾乎沒有影響;在蓄意攻擊的模式下,隨著移除節(jié)點的增多,網(wǎng)絡(luò)中沒有連接的單個節(jié)點的數(shù)目也在不斷增大,網(wǎng)絡(luò)的最大連通度越來越小,這說明網(wǎng)絡(luò)在面臨蓄意攻擊時極大可能會產(chǎn)生分裂。該參數(shù)的變化曲線與平均路徑長度呈現(xiàn)相似的趨勢。
兩種情況對比來看,因為隨機攻擊中移出的多是介數(shù)偏小的節(jié)點,保留了相對重要的節(jié)點,所以對于整個網(wǎng)絡(luò)的性能影響并不明顯,依然保持較好的魯棒性。而帶有針對性的蓄意攻擊則會移出介數(shù)偏大的節(jié)點,隨之而來的與其有連接的節(jié)點都會受到干擾甚至破壞,這也導(dǎo)致了網(wǎng)絡(luò)中單個節(jié)點的出現(xiàn),使整個網(wǎng)絡(luò)魯棒性變差。
(3)介數(shù)。在設(shè)定蓄意攻擊時,便是依次移除介數(shù)值大的節(jié)點,再對整體進(jìn)行分析,研究介數(shù)對于研究整個復(fù)雜網(wǎng)絡(luò)的魯棒性來說是必不可少的一步。在網(wǎng)絡(luò)中,其他的統(tǒng)計參數(shù)會隨著介數(shù)高的節(jié)點的消失發(fā)生相對而言很大的變化。在仿真實驗中無論是哪種攻擊,在移除節(jié)點后整體網(wǎng)絡(luò)的介數(shù)都會產(chǎn)生一定變化,不過顯然蓄意攻擊情況下變化更劇烈些。在故意移除較多的介數(shù)數(shù)值高的節(jié)點時,整體介數(shù)值也變大了許多。
盡管有眾多研究復(fù)雜網(wǎng)絡(luò)魯棒性的參數(shù)和方法,依然無法將真實網(wǎng)絡(luò)的實際情況完全表現(xiàn)和擬設(shè)出來。許多實際的網(wǎng)絡(luò)在運轉(zhuǎn)的同時也在不斷地變化著,并且可能產(chǎn)生干擾的因素也是數(shù)不勝數(shù),每一個因素都會帶來無法預(yù)知的后果。所以本文僅是構(gòu)建出了簡單的中國民航網(wǎng)絡(luò)用于魯棒性的演化模型,并對其進(jìn)行兩種干擾模式下的理論數(shù)據(jù)分析,協(xié)助產(chǎn)生更規(guī)范化的民航網(wǎng)絡(luò)。
經(jīng)過上述分析,中國民航網(wǎng)絡(luò)在隨機攻擊后各項評價指標(biāo)均變化不大,但在蓄意攻擊后平均路徑長度迅速增加,最大連通度大幅度下降,并且整體介數(shù)值也發(fā)生了較大變化。也就是說,面對隨機攻擊時中國民航網(wǎng)絡(luò)表現(xiàn)出明顯的魯棒性,而當(dāng)蓄意攻擊介數(shù)值較大的節(jié)點時,網(wǎng)絡(luò)的魯棒性較差。
本文選用中國民航網(wǎng)絡(luò)為基礎(chǔ)模型,以復(fù)雜網(wǎng)絡(luò)理論為基礎(chǔ)對其進(jìn)行魯棒性分析。通過建立網(wǎng)絡(luò)模型,分析了其平均路徑長度和度分布等統(tǒng)計特性,得出其具備小世界特性、但更多地體現(xiàn)無標(biāo)度特性的結(jié)論。在確定兩種干擾措施和三個評估指標(biāo)后,進(jìn)行仿真實驗。實驗中隨機攻擊時依次隨機選取一定量的節(jié)點移除,蓄意攻擊時按介數(shù)值從大到小排序并依次移除一定量節(jié)點,最后利用統(tǒng)計參數(shù)分析中國民航網(wǎng)絡(luò)魯棒性。結(jié)果表明,隨機攻擊對網(wǎng)絡(luò)的魯棒性沒有太大影響,但蓄意攻擊某些介數(shù)大的節(jié)點時網(wǎng)絡(luò)的平均路徑長度增大,最大連通度變小,魯棒性明顯變差。
在實際運轉(zhuǎn)的過程中,需要重點保障核心機場的正常運行,防止蓄意破壞的發(fā)生影響網(wǎng)絡(luò)全局。本文實驗分析所得出的結(jié)果,可以為中國民航網(wǎng)絡(luò)的標(biāo)準(zhǔn)化和規(guī)范化提供參考,促進(jìn)民航業(yè)進(jìn)一步的發(fā)展。