基于Pajek的航空網(wǎng)絡(luò)特征評(píng)價(jià)與可生存性分析

劉典勇，左小五，張冰冰

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海200093)

針對(duì)航空網(wǎng)絡(luò)使用可視化工具Pajek進(jìn)行分析和模擬仿真，通過模擬對(duì)比對(duì)比國(guó)內(nèi)航空網(wǎng)絡(luò)與國(guó)外航空網(wǎng)絡(luò)的抗打擊能力，對(duì)航空網(wǎng)絡(luò)的可生存性進(jìn)行研究［1］。

1 航空網(wǎng)絡(luò)特征評(píng)價(jià)

1.1 航空網(wǎng)絡(luò)統(tǒng)計(jì)特征簡(jiǎn)介

小世界效應(yīng)是指在大尺度復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)中任意兩點(diǎn)之間存在著一條相對(duì)很短的連接路徑［2］。

網(wǎng)絡(luò)中兩個(gè)結(jié)點(diǎn)i和j之間的距離dij定義為連接這兩個(gè)結(jié)點(diǎn)的最短路徑上的邊數(shù)。網(wǎng)絡(luò)中任意兩個(gè)結(jié)點(diǎn)之間距離的最大值稱為網(wǎng)絡(luò)的直徑，記為D［3］，即

網(wǎng)絡(luò)的平均路徑長(zhǎng)度L定義為任意兩結(jié)點(diǎn)之間距離的平均值［4］，即

其中，N為網(wǎng)絡(luò)結(jié)點(diǎn)數(shù)。有時(shí)平均路徑長(zhǎng)度又稱為特征路徑長(zhǎng)度。

一般地，假設(shè)網(wǎng)絡(luò)中的一個(gè)結(jié)點(diǎn)i有ki條邊將其與其他結(jié)點(diǎn)相連，這ki個(gè)結(jié)點(diǎn)就稱為結(jié)點(diǎn)i的鄰居。顯然，在這ki個(gè)結(jié)點(diǎn)之間最多可能有ki(ki－1)/2條邊。而這ki個(gè)結(jié)點(diǎn)之間實(shí)際存在的邊數(shù)Ei和總的可能的邊數(shù)ki(ki－1)/2之比就定義為結(jié)點(diǎn)i的類聚系數(shù)Ci［5］，即

許多復(fù)雜網(wǎng)絡(luò)的度分布可用冪律形式P(k)～k－γ來更好地描述，如圖1所示。冪律分布函數(shù)具有如下無標(biāo)度性質(zhì)［6］:

考慮一個(gè)概率分布函數(shù)f(x)，若對(duì)任意給定常數(shù)a，存在常數(shù)b使得函數(shù)f(x)滿足“無標(biāo)度條件”

圖1 冪律分布(對(duì)數(shù)坐標(biāo)系)

網(wǎng)絡(luò)直徑是指復(fù)雜網(wǎng)絡(luò)中距離最遠(yuǎn)兩點(diǎn)間的距離。若在航空網(wǎng)絡(luò)真實(shí)反映出來，則是擁有最多站點(diǎn)的航線的站點(diǎn)數(shù)目。

結(jié)點(diǎn)的介數(shù)則是指網(wǎng)絡(luò)中經(jīng)過某結(jié)點(diǎn)的最短路徑數(shù)目，其側(cè)面反映了結(jié)點(diǎn)的綜合影響力，各種交通樞紐都是介數(shù)較大的結(jié)點(diǎn)。這對(duì)于在現(xiàn)實(shí)網(wǎng)絡(luò)中發(fā)現(xiàn)和保護(hù)關(guān)鍵資源具有重要意義。

1.2 航空網(wǎng)絡(luò)拓?fù)鋱D的繪制

本課題選取的是2005年的美國(guó)航空網(wǎng)絡(luò)和中國(guó)航空網(wǎng)絡(luò)，其中美國(guó)航空網(wǎng)絡(luò)由332個(gè)通航城市、2 461條直飛航線組成，中國(guó)航空網(wǎng)絡(luò)選取了2005年其中30個(gè)最主要城市作為通航城市，組成了274條直飛航線。其中所涉及到的網(wǎng)絡(luò)數(shù)據(jù)全部來源于互聯(lián)網(wǎng)［7］。

將美國(guó)和中國(guó)航空網(wǎng)絡(luò)數(shù)據(jù).net文件讀入Pajek軟件后，單擊Draw按鈕就可以得到航空網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)圖，如圖2和圖3所示。

圖2 美國(guó)航空網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖

圖3 中國(guó)航空網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖

1.3 中美航空網(wǎng)絡(luò)的統(tǒng)計(jì)特性

美國(guó)是發(fā)達(dá)國(guó)家，航空網(wǎng)絡(luò)的發(fā)展已到了一定階段且已基本成熟。而中國(guó)是發(fā)展中國(guó)家，雖然航空領(lǐng)域已經(jīng)日趨成為我國(guó)主要的交通運(yùn)輸業(yè)，但畢竟還未發(fā)展成熟，容錯(cuò)率和抗擊打能力仍不足。通過靜態(tài)統(tǒng)計(jì)特征值:度分布、平均路徑長(zhǎng)度、結(jié)點(diǎn)介數(shù)、網(wǎng)絡(luò)直徑、類聚系數(shù)等來分析兩個(gè)具有代表性的國(guó)家的航空網(wǎng)絡(luò)模型。

通過Pajek軟件對(duì)中國(guó)和美國(guó)航空網(wǎng)絡(luò)進(jìn)行關(guān)于統(tǒng)計(jì)特征的計(jì)算，得到中國(guó)航空網(wǎng)絡(luò)的基本統(tǒng)計(jì)特性，平均度:15.967，平均路徑長(zhǎng)度:1.444，網(wǎng)絡(luò)直徑:5，平均類聚系數(shù):0.472，平均結(jié)點(diǎn)介數(shù):0.325。

美國(guó)航空網(wǎng)絡(luò)的基本統(tǒng)計(jì)特性，平均度:12.808，平均路徑長(zhǎng)度:2.738，網(wǎng)絡(luò)直徑:6，平均類聚系數(shù):0.396，平均結(jié)點(diǎn)介數(shù):0.204。

對(duì)比兩國(guó)航空網(wǎng)絡(luò)模型的統(tǒng)計(jì)特征值，大體可知中國(guó)航空網(wǎng)絡(luò)具有高類聚系數(shù)，呈現(xiàn)小世界網(wǎng)絡(luò)的特征。

2 可生存性分析

2.1 隨機(jī)攻擊下的可生存性分析

隨機(jī)攻擊即以一定比例隨機(jī)移除結(jié)點(diǎn)，網(wǎng)絡(luò)在隨機(jī)破壞作用下的網(wǎng)絡(luò)生存性，主要根據(jù)Pajek的強(qiáng)大網(wǎng)絡(luò)分析能力和計(jì)算能力來評(píng)價(jià)航空網(wǎng)絡(luò)。因此，就在此基礎(chǔ)上進(jìn)行隨機(jī)性攻擊［8］。對(duì)于航空網(wǎng)絡(luò)而言，隨機(jī)攻擊主要指一些隨機(jī)因素造成一個(gè)結(jié)點(diǎn)(城市)的失效。隨機(jī)攻擊假設(shè)通常的隨機(jī)性攻擊指的是網(wǎng)絡(luò)中的結(jié)點(diǎn)以某種概率被隨機(jī)的攻擊和破壞［9－10］，以中美航空網(wǎng)絡(luò)為例，考慮到航空網(wǎng)絡(luò)中的機(jī)場(chǎng)城市數(shù)目較多，因此文中按照前0%，10%，20%，30%，40%，50%，60%的結(jié)點(diǎn)比例隨機(jī)刪除網(wǎng)絡(luò)中的結(jié)點(diǎn)，利用Pajek分別得到遭受隨機(jī)刪除結(jié)點(diǎn)后的平均長(zhǎng)度L，并得到平均長(zhǎng)度變化趨勢(shì)圖。

由圖4可知，中國(guó)航空網(wǎng)絡(luò)在遭受10%隨機(jī)打擊時(shí)，平均路徑長(zhǎng)度變?yōu)?.478，直至增加到刪除結(jié)點(diǎn)50%時(shí)，平均長(zhǎng)度變?yōu)?.67，這說明中國(guó)航空網(wǎng)絡(luò)中各個(gè)通航城市之間聯(lián)系緊密，而不會(huì)因?yàn)槟硯讉€(gè)結(jié)點(diǎn)的移除而變成網(wǎng)絡(luò)崩潰。然后隨著移除結(jié)點(diǎn)的比例逐漸增加，直到60%時(shí)，航空網(wǎng)絡(luò)之間的聯(lián)系遭到了嚴(yán)重破壞，一直到徹底崩潰。而美國(guó)航空網(wǎng)絡(luò)則在50%以內(nèi)的打擊下，網(wǎng)絡(luò)基本沒受影響，而在隨機(jī)打擊了60%的結(jié)點(diǎn)后，平均路徑長(zhǎng)度仍為2.2，各通航城市之間保持較高的連接性。

圖4 隨機(jī)攻擊下中美航空網(wǎng)絡(luò)平均長(zhǎng)度趨勢(shì)圖

在對(duì)航空網(wǎng)絡(luò)的評(píng)價(jià)分析中，移除比例分別為0%，10%，20%，30%，40%，50%，60%進(jìn)行隨機(jī)攻擊航空網(wǎng)絡(luò)，通過統(tǒng)計(jì)剩余可攻擊航線數(shù)N來表征航空網(wǎng)絡(luò)的完整性和可生存性。

分別統(tǒng)計(jì)中美航空網(wǎng)絡(luò)可攻擊航線條數(shù)N，通過Pajek強(qiáng)大的數(shù)據(jù)統(tǒng)計(jì)和分析能力，得到以下可達(dá)航線數(shù)N與移除結(jié)點(diǎn)比例的趨勢(shì)圖，如圖5所示。

圖5 隨機(jī)攻擊下中美航空網(wǎng)絡(luò)可達(dá)航線數(shù)趨勢(shì)圖

中國(guó)航空網(wǎng)絡(luò)在隨機(jī)攻擊下的可達(dá)航線數(shù)逐漸下降，即網(wǎng)絡(luò)總邊數(shù)會(huì)急劇下降，一直到40%時(shí)，網(wǎng)絡(luò)總邊數(shù)變?yōu)?，即網(wǎng)絡(luò)已遭到嚴(yán)重破壞。而美國(guó)在遭到移除60%的結(jié)點(diǎn)時(shí)仍有1 000多條航線，兩組趨勢(shì)圖均說明中國(guó)航空網(wǎng)絡(luò)在隨機(jī)攻擊下具有一定的可生存性，但其隨機(jī)打擊下的生存性不如美國(guó)。

2.2 蓄意攻擊下的可生存性分析

為得到在蓄意攻擊下，網(wǎng)絡(luò)的生存性特點(diǎn)，選擇刪除結(jié)點(diǎn)的辦法。為使這兩個(gè)網(wǎng)絡(luò)盡快的崩潰，因此選擇攻擊網(wǎng)絡(luò)中度最高的結(jié)點(diǎn)，將它們依次刪除，然后在Pajek中刪除網(wǎng)絡(luò)中指定的結(jié)點(diǎn)。

由于所選航空網(wǎng)絡(luò)模型的結(jié)點(diǎn)數(shù)比較多，因此選擇采取按百分比攻擊度排在前面的結(jié)點(diǎn)，假設(shè)選取蓄意攻擊前0%，10%，20%，30%，40%，50%，60%的結(jié)點(diǎn)，然后分別繪制出中國(guó)和美國(guó)的航空網(wǎng)絡(luò)在遭受蓄意攻擊情況下的平均路徑長(zhǎng)度和蓄意打擊總邊數(shù)等統(tǒng)計(jì)特性趨勢(shì)圖，通過對(duì)比其中的性能指標(biāo)來對(duì)比其可生存性，如圖6和圖7所示。

圖6 蓄意攻擊下中美航空網(wǎng)絡(luò)平均長(zhǎng)度趨勢(shì)圖

圖7 蓄意攻擊下中美航空網(wǎng)絡(luò)可達(dá)航線數(shù)趨勢(shì)圖

從以上兩組圖中可以看出，當(dāng)網(wǎng)絡(luò)遭受蓄意攻擊時(shí)，平均長(zhǎng)度急劇上升，當(dāng)打擊到30%結(jié)點(diǎn)或當(dāng)蓄意攻擊前40%的結(jié)點(diǎn)時(shí)，平均最短距離為0，即中國(guó)航空網(wǎng)絡(luò)之間不連通。當(dāng)攻擊10%結(jié)點(diǎn)后，中美航空網(wǎng)絡(luò)中的大部分的結(jié)點(diǎn)之間都是連通的，可相互到達(dá)。當(dāng)攻擊前40%的結(jié)點(diǎn)時(shí)，中國(guó)航空網(wǎng)絡(luò)整體結(jié)構(gòu)已遭到嚴(yán)重破壞，直至當(dāng)蓄意攻擊網(wǎng)絡(luò)中60%的結(jié)點(diǎn)時(shí)，中國(guó)航空網(wǎng)絡(luò)已經(jīng)完全斷開連接。而從圖7中可以看出，即使蓄意攻擊網(wǎng)絡(luò)中的前60%的結(jié)點(diǎn)，美國(guó)航空網(wǎng)絡(luò)中的大部分結(jié)點(diǎn)還是連通且可到達(dá)的。由此可見，美國(guó)航空網(wǎng)絡(luò)在蓄意攻擊下的可生存性遠(yuǎn)優(yōu)于中國(guó)。

說明美國(guó)航空網(wǎng)絡(luò)在蓄意攻擊下具有更好的可生存性，可見發(fā)達(dá)國(guó)家的航空網(wǎng)絡(luò)較發(fā)展中國(guó)家來說具有明顯的優(yōu)越性和穩(wěn)定性。

3 結(jié)束語

本文主要是運(yùn)用Pajek和復(fù)雜網(wǎng)絡(luò)理論的觀點(diǎn)和方法針對(duì)國(guó)內(nèi)和國(guó)際的航空網(wǎng)絡(luò)建立不同的可視化模型，以中國(guó)和美國(guó)的航空網(wǎng)絡(luò)的模型數(shù)據(jù)為例進(jìn)行分析，美國(guó)是發(fā)達(dá)國(guó)家，航空網(wǎng)絡(luò)的發(fā)展已基本成熟。而中國(guó)是發(fā)展中國(guó)家，雖航空領(lǐng)域已日趨完善，但畢竟還未發(fā)展成熟，容錯(cuò)率和抗擊打能力仍不足。研究表明，中國(guó)航空網(wǎng)絡(luò)仍是一個(gè)小世界網(wǎng)絡(luò)。

在研究航空模型的過程中引用了Pajek可視化軟件，運(yùn)用Pajek可直觀的發(fā)掘航空網(wǎng)絡(luò)的一些特征，但Pajek也有其的不足之處，例如要對(duì)網(wǎng)絡(luò)的蓄意攻擊進(jìn)行模擬時(shí)，刪除結(jié)點(diǎn)只能手動(dòng)進(jìn)行，若網(wǎng)絡(luò)中的結(jié)點(diǎn)過多時(shí)，則手動(dòng)刪除的效率就會(huì)變得較低，這功能有待優(yōu)化。且由于文中所掌握的中國(guó)國(guó)內(nèi)航空網(wǎng)絡(luò)的實(shí)時(shí)數(shù)據(jù)不足，導(dǎo)致在建立Pajek網(wǎng)絡(luò)模型時(shí)會(huì)存在誤差。若能獲得更多詳細(xì)的航空網(wǎng)絡(luò)數(shù)據(jù)，模型將得到大幅改善。

［1］ 朱冰心.中國(guó)航空網(wǎng)絡(luò)結(jié)構(gòu)及其演化分析［D］.上海:復(fù)旦大學(xué)，2007.

［2］ 黃加增，余國(guó)偉.城市公交復(fù)雜網(wǎng)絡(luò)研究［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2012，22(6):234－238.

［3］ 彭俊.復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)及傳播模型的研究［D］.西安:西安電子科技大學(xué)，2009.

［4］ 鄧雪蓮.負(fù)責(zé)網(wǎng)絡(luò)抽樣研究［D］.南寧:廣西師范大學(xué)，2008.

［5］ 安莉莉，馬杰良，邢雪.南京市公交網(wǎng)絡(luò)建模與拓?fù)涮匦苑治觯跩］.公路交通科技:應(yīng)用技術(shù)版，2009(2):181－183.

［6］ 藺志峰.復(fù)雜網(wǎng)絡(luò)的搜索策略研究［D］.石家莊:石家莊經(jīng)濟(jì)學(xué)院，2011.

［7］ 中國(guó)民用航空總局規(guī)劃發(fā)展財(cái)務(wù)司.從統(tǒng)計(jì)看民航2005［M］.北京:中國(guó)民航出版社，2005.

［8］ 熊靜.基于復(fù)雜網(wǎng)絡(luò)理論的交通網(wǎng)絡(luò)可生存性分析［D］.武漢:華中科技大學(xué)，2009.

［9］ 俞桂杰，彭語冰，褚衍昌.復(fù)雜網(wǎng)絡(luò)理論及其在航空網(wǎng)絡(luò)中的應(yīng)用［J］.復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2006，3(1):79－84.

［10］張?chǎng)?復(fù)雜網(wǎng)絡(luò)理論在航空網(wǎng)絡(luò)中的應(yīng)用研究［D］.天津:中國(guó)民航大學(xué)，2009.