多層網(wǎng)絡(luò)中心度在航空網(wǎng)絡(luò)中的應(yīng)用研究
2015-05-30 10:33:13畢京浩張瑞馬夏夏
商 2015年3期
畢京浩 張瑞 馬夏夏
摘要：利用多層復(fù)雜網(wǎng)絡(luò)理論和方法，構(gòu)建多層航空網(wǎng)絡(luò)，說明其結(jié)構(gòu)特性。將多層網(wǎng)絡(luò)中心度應(yīng)用于航空網(wǎng)絡(luò)的研究，找出多層航空網(wǎng)絡(luò)的多層中心節(jié)點。
關(guān)鍵詞：多層網(wǎng)絡(luò)；多層中心度；航空網(wǎng)絡(luò)
一、引言
近年來，對于復(fù)雜網(wǎng)絡(luò)的研究已經(jīng)深入到各個領(lǐng)域，復(fù)雜網(wǎng)絡(luò)理論在交通、電力、計算機、生物等領(lǐng)域應(yīng)用廣泛。國內(nèi)對于復(fù)雜網(wǎng)絡(luò)的研究多集中在單層的網(wǎng)絡(luò)中，隨著對于復(fù)雜網(wǎng)絡(luò)理論研究的深入，國外學(xué)者開始關(guān)注多層復(fù)雜網(wǎng)絡(luò)的研究。
多層網(wǎng)絡(luò)是由多個網(wǎng)絡(luò)或者交互的多個不同實體之間的復(fù)雜系統(tǒng)構(gòu)成[1]。多層網(wǎng)絡(luò)的每一層是不同行為、不同屬性的抽象，它是復(fù)雜網(wǎng)絡(luò)的延伸，它可以用來解決單層網(wǎng)絡(luò)中不同網(wǎng)絡(luò)或不同實體之間復(fù)雜的連接關(guān)系，使網(wǎng)絡(luò)中的關(guān)系更加清晰可見。
單層網(wǎng)絡(luò)用度、平均路徑長度和介數(shù)等指標(biāo)來描述單層網(wǎng)絡(luò)的統(tǒng)計特性，多層網(wǎng)絡(luò)也需要相應(yīng)的指標(biāo)來描述和衡量。Bródka P最先提出了多層網(wǎng)絡(luò)中心度這個指標(biāo)，并將它應(yīng)用于多層社會網(wǎng)絡(luò)的研究[2]。文中通過分析Web社交網(wǎng)絡(luò)中的真實數(shù)據(jù)，將網(wǎng)絡(luò)分為10層，并找出了社交網(wǎng)絡(luò)的中心。本文擬將多層網(wǎng)絡(luò)中心度應(yīng)用于多層航空網(wǎng)絡(luò)的研究，分析多層航空網(wǎng)絡(luò)的鄰居節(jié)點，并找出多層航空網(wǎng)絡(luò)的中心。
二、多層航空網(wǎng)絡(luò)的構(gòu)建
1.航空網(wǎng)絡(luò)的特征描述
航空網(wǎng)絡(luò)是指在一定區(qū)域內(nèi)由若干條航線按照某種方式連接組成的復(fù)雜系統(tǒng)，包括機場、航線和飛機等要素[3]。多層航空網(wǎng)絡(luò)將機場看作節(jié)點，將機場之間的航線看作邊，將不同的航空公司看作層，由于只考慮機場之間的連接關(guān)系，所以把多層航空網(wǎng)絡(luò)抽象為多層非加權(quán)網(wǎng)絡(luò)。
2.多層航空網(wǎng)絡(luò)的構(gòu)建
定義：定義多層航空網(wǎng)絡(luò)為一個元組。V是一個非空節(jié)點集，每個節(jié)點代表一個機場；E是邊集，它也是一個元組，對于兩個元組，如果，那么它們位于不同的層，即；L是層集，每一層代表一個航空公司。
每個元組是在l層由節(jié)點x到節(jié)點y連接的一條邊，即機場x和y之間的一條航線，任意兩個節(jié)點之間只有一條邊。由于機場間的航線是互通的，所以多層航空網(wǎng)絡(luò)是一個無向網(wǎng)絡(luò)，因此。
對于某一層l的節(jié)點集V和邊集E，構(gòu)成了一個簡單的單層網(wǎng)絡(luò)。
一個多層航空網(wǎng)絡(luò)可以有一個多層圖來表示。圖1是代表一個三層的航空網(wǎng)絡(luò)。圖中有5個節(jié)點，在層和中，它們相互連接。對于層來說，存在5個連接關(guān)系：
圖1多層航空網(wǎng)絡(luò)示例
3.主要統(tǒng)計量
（1）鄰居節(jié)點。多層網(wǎng)絡(luò)是由多個單層網(wǎng)絡(luò)組成，因此可以定義為兩個不同鄰居節(jié)點集。
a.單層鄰居節(jié)點。只考慮多層航空網(wǎng)絡(luò)中的一層，可以看作為單層網(wǎng)絡(luò)，對應(yīng)的即單層鄰居節(jié)點。
Nx，1=y：x，y，l∈E
x是位于l層的一個節(jié)點，x∈V，l∈L。
b.多層鄰居節(jié)點。多層鄰居節(jié)點是在a1≤a≤L層與給定節(jié)點x相連接的節(jié)點集。
MNx，a=y：1：x，y，1∈E≥a
在圖1中，節(jié)點x的多層鄰居節(jié)點為：
MNx，1=y，z
MNx，2=y，u
MNx，3=z
（2）多層中心度。中心度代表著節(jié)點在網(wǎng)絡(luò)中的重要性。多層中心度可以定義為節(jié)點x與對應(yīng)的多層鄰居節(jié)點之間的權(quán)重總和與層的數(shù)量和多層網(wǎng)絡(luò)所有節(jié)點數(shù)的比值。
MCDx，a=y∈MNx，awx，y，lm-1L
wx，y，l是邊x，y，l的權(quán)重，對于本文來講，權(quán)重為1。
三、實證分析
1.多層航空網(wǎng)絡(luò)特征描述。
本文選取的數(shù)據(jù)為歐洲四家航空公司的航線數(shù)據(jù)[4，5]。將位于不同城市的機場作為一個節(jié)點，機場之間的航線作為邊，構(gòu)造了一個多層無向非加權(quán)的航空網(wǎng)絡(luò)。
多層航空網(wǎng)絡(luò)中共有335個機場節(jié)點，974條邊，如表1所示。其中，如果不考慮層的不同，共有207個節(jié)點。其中，有128個節(jié)點是重復(fù)的，重復(fù)的節(jié)點意味著不同的航空公司在同一城市均有機場。Lufthansa和Ryanair公司的機場數(shù)超過100，也擁有更多的航線。
表1每一層的節(jié)點數(shù)和邊數(shù)
2.多層鄰居節(jié)點
圖2是層1的多層鄰居節(jié)點分布圖。從圖中可以看到，大部分的節(jié)點含有較少的多層鄰居節(jié)點，多層鄰居節(jié)點的數(shù)量超過12的節(jié)點數(shù)量平均為1～2個，說明Lufthansa公司所在機場的航線只有少數(shù)是比較密集的。如圖3所示，超過70%的節(jié)點的鄰居節(jié)點數(shù)少于10，超過30個鄰居節(jié)點的節(jié)點不到10%。多層鄰居節(jié)點的分布體現(xiàn)了多層航空網(wǎng)絡(luò)的無標(biāo)度性。
圖2多層鄰居節(jié)點圖（）
圖3多層鄰居節(jié)點分布統(tǒng)計（）
圖4為各層的鄰居節(jié)點分布圖，層1和層2分布相似，它們均含有較多的節(jié)點和邊。每個層的鄰居節(jié)點分布都符合無標(biāo)度網(wǎng)絡(luò)的性質(zhì)。
圖4多層鄰居節(jié)點圖（）
圖5為多層鄰居節(jié)點條形圖，鄰居節(jié)點的數(shù)量以10個單位為分割。從圖中可以看出，隨著范圍的遞進，每層中的節(jié)點數(shù)量逐步在減少，在鄰居節(jié)點數(shù)達到（21，30）的范圍之后對應(yīng)的節(jié)點數(shù)明顯減少。統(tǒng)計結(jié)果顯示，每一層的節(jié)點數(shù)在不同范圍內(nèi)呈現(xiàn)出相同的下降趨勢，側(cè)面反映出每個航空公司對于機場和航線的拓?fù)浣Y(jié)構(gòu)相似。
圖5多層鄰居節(jié)點條形圖
3.多層中心度
多層中心度MCDx，a取決于多層鄰居節(jié)點MNx，a，當(dāng)MNx，a>0，MCDx，a>0。圖6是第一層中各節(jié)點的多層中心度分布，從圖中可以看出，節(jié)點多集中在多層中心度為0.02以下的區(qū)域，高于0.04的節(jié)點較少。節(jié)點中心度表明節(jié)點在多層網(wǎng)絡(luò)中的重要程度。從圖中可以看出，在第一層中只有少數(shù)的節(jié)點在多層航空網(wǎng)絡(luò)中作用很大。
圖6多層中心度分布圖（）
圖7是各層節(jié)點的多層分布圖，每一層的分布與第一層的分布類似。圖中多個圖形重疊的節(jié)點代表不同航空公司在該城市均有機場。從圖中可以找出多層中心度較高的幾個關(guān)鍵節(jié)點。表2是每一層節(jié)點的多層中心度的變化范圍。
圖7多層中心度分布圖（a=1，2，3，4）
表2多層中心度范圍
層號1234
最小值1.21E-31.21E-31.21E-31.21E-3
最大值9.59E-21.06E-11.06E-16.55E-2
表3給出了節(jié)點中心度大于0.5的幾個節(jié)點的多層中心度。通過表3可以直觀的看出多層中心度最大的為節(jié)點12，總共有8個節(jié)點的多層中心度大于0.5。結(jié)合多層航空網(wǎng)絡(luò)，這8個節(jié)點對應(yīng)的機場就相當(dāng)于航空網(wǎng)絡(luò)中幾個重要的機場，節(jié)點12對應(yīng)的機場即要找的多層航空網(wǎng)絡(luò)的中心。
表3部分節(jié)點的多層中心度
節(jié)點多層中心度
1660.052
110.053
400.064
710.065
1080.067
20.096
380.096
120.106
四、結(jié)論與展望
通過分析多層航空網(wǎng)絡(luò)的各節(jié)點的多層中心度，找出了多層航空網(wǎng)絡(luò)的中心節(jié)點。未來的主要工作是結(jié)合實際情況研究該中心節(jié)點的實際意義，可從以下幾個方面進行：
（1）在航空公司布局機場時，可優(yōu)先考慮多層中心節(jié)點的布局，同時考慮多層中心度較大的其他節(jié)點，以便更好地發(fā)展業(yè)務(wù)；或者在已經(jīng)布局了多層中心節(jié)點時，可提供更優(yōu)質(zhì)的服務(wù)來增強競爭力。
（2）對于航空網(wǎng)絡(luò)脆弱性研究方面，優(yōu)先考慮對多層中心節(jié)點提供保護措施。
（3）可以將多層中心度拓展應(yīng)用于其他多層網(wǎng)絡(luò)的計算。
（4）可以將現(xiàn)有算法進行優(yōu)化，提高計算效率。（作者單位：濟南大學(xué)管理學(xué)院）
參考文獻：
[1]Kivel M， Arenas A， Barthelemy M， et al. Multilayer networks[J]. Journal of Complex Networks， 2014， 2（3）： 203-271.
[2]Bródka P， Skibicki K， Kazienko P， et al. A degree centrality in multi-layered social network[C]//Computational Aspects of Social Networks （CASoN）， 2011 International Conference on. IEEE， 2011： 237-242.
[3]俞桂杰， 彭語冰， 褚衍昌. 復(fù)雜網(wǎng)絡(luò)理論及其在航空網(wǎng)絡(luò)中的應(yīng)用 [J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)， 2006， 3（1）： 79-84.
[4]Stark C， Breitkreutz B J， Reguly T， et al. BioGRID： a general repository for interaction datasets[J]. Nucleic acids research， 2006， 34（suppl 1）： D535-D539.
[5]De Domenico M， Porter M A， Arenas A. MuxViz： a tool for multilayer analysis and visualization of networks[J]. Journal of Complex Networks， 2014： cnu038.
