畢京浩　張瑞　馬夏夏

摘要：利用多層復(fù)雜網(wǎng)絡(luò)理論和方法，構(gòu)建多層航空網(wǎng)絡(luò)，說明其結(jié)構(gòu)特性。將多層網(wǎng)絡(luò)中心度應(yīng)用于航空網(wǎng)絡(luò)的研究，找出多層航空網(wǎng)絡(luò)的多層中心節(jié)點(diǎn)。

關(guān)鍵詞：多層網(wǎng)絡(luò)；多層中心度；航空網(wǎng)絡(luò)

一、引言

近年來，對(duì)于復(fù)雜網(wǎng)絡(luò)的研究已經(jīng)深入到各個(gè)領(lǐng)域，復(fù)雜網(wǎng)絡(luò)理論在交通、電力、計(jì)算機(jī)、生物等領(lǐng)域應(yīng)用廣泛。國(guó)內(nèi)對(duì)于復(fù)雜網(wǎng)絡(luò)的研究多集中在單層的網(wǎng)絡(luò)中，隨著對(duì)于復(fù)雜網(wǎng)絡(luò)理論研究的深入，國(guó)外學(xué)者開始關(guān)注多層復(fù)雜網(wǎng)絡(luò)的研究。

多層網(wǎng)絡(luò)是由多個(gè)網(wǎng)絡(luò)或者交互的多個(gè)不同實(shí)體之間的復(fù)雜系統(tǒng)構(gòu)成[1]。多層網(wǎng)絡(luò)的每一層是不同行為、不同屬性的抽象，它是復(fù)雜網(wǎng)絡(luò)的延伸，它可以用來解決單層網(wǎng)絡(luò)中不同網(wǎng)絡(luò)或不同實(shí)體之間復(fù)雜的連接關(guān)系，使網(wǎng)絡(luò)中的關(guān)系更加清晰可見。

單層網(wǎng)絡(luò)用度、平均路徑長(zhǎng)度和介數(shù)等指標(biāo)來描述單層網(wǎng)絡(luò)的統(tǒng)計(jì)特性，多層網(wǎng)絡(luò)也需要相應(yīng)的指標(biāo)來描述和衡量。Bródka P最先提出了多層網(wǎng)絡(luò)中心度這個(gè)指標(biāo)，并將它應(yīng)用于多層社會(huì)網(wǎng)絡(luò)的研究[2]。文中通過分析Web社交網(wǎng)絡(luò)中的真實(shí)數(shù)據(jù)，將網(wǎng)絡(luò)分為10層，并找出了社交網(wǎng)絡(luò)的中心。本文擬將多層網(wǎng)絡(luò)中心度應(yīng)用于多層航空網(wǎng)絡(luò)的研究，分析多層航空網(wǎng)絡(luò)的鄰居節(jié)點(diǎn)，并找出多層航空網(wǎng)絡(luò)的中心。

二、多層航空網(wǎng)絡(luò)的構(gòu)建

1.航空網(wǎng)絡(luò)的特征描述

航空網(wǎng)絡(luò)是指在一定區(qū)域內(nèi)由若干條航線按照某種方式連接組成的復(fù)雜系統(tǒng)，包括機(jī)場(chǎng)、航線和飛機(jī)等要素[3]。多層航空網(wǎng)絡(luò)將機(jī)場(chǎng)看作節(jié)點(diǎn)，將機(jī)場(chǎng)之間的航線看作邊，將不同的航空公司看作層，由于只考慮機(jī)場(chǎng)之間的連接關(guān)系，所以把多層航空網(wǎng)絡(luò)抽象為多層非加權(quán)網(wǎng)絡(luò)。

2.多層航空網(wǎng)絡(luò)的構(gòu)建

定義：定義多層航空網(wǎng)絡(luò)為一個(gè)元組。V是一個(gè)非空節(jié)點(diǎn)集，每個(gè)節(jié)點(diǎn)代表一個(gè)機(jī)場(chǎng)；E是邊集，它也是一個(gè)元組，對(duì)于兩個(gè)元組，如果，那么它們位于不同的層，即；L是層集，每一層代表一個(gè)航空公司。

每個(gè)元組是在l層由節(jié)點(diǎn)x到節(jié)點(diǎn)y連接的一條邊，即機(jī)場(chǎng)x和y之間的一條航線，任意兩個(gè)節(jié)點(diǎn)之間只有一條邊。由于機(jī)場(chǎng)間的航線是互通的，所以多層航空網(wǎng)絡(luò)是一個(gè)無向網(wǎng)絡(luò)，因此。

對(duì)于某一層l的節(jié)點(diǎn)集V和邊集E，構(gòu)成了一個(gè)簡(jiǎn)單的單層網(wǎng)絡(luò)。

一個(gè)多層航空網(wǎng)絡(luò)可以有一個(gè)多層圖來表示。圖1是代表一個(gè)三層的航空網(wǎng)絡(luò)。圖中有5個(gè)節(jié)點(diǎn)，在層和中，它們相互連接。對(duì)于層來說，存在5個(gè)連接關(guān)系：

圖1多層航空網(wǎng)絡(luò)示例

3.主要統(tǒng)計(jì)量

（1）鄰居節(jié)點(diǎn)。多層網(wǎng)絡(luò)是由多個(gè)單層網(wǎng)絡(luò)組成，因此可以定義為兩個(gè)不同鄰居節(jié)點(diǎn)集。

a.單層鄰居節(jié)點(diǎn)。只考慮多層航空網(wǎng)絡(luò)中的一層，可以看作為單層網(wǎng)絡(luò)，對(duì)應(yīng)的即單層鄰居節(jié)點(diǎn)。

Nx，1=y：x，y，l∈E

x是位于l層的一個(gè)節(jié)點(diǎn)，x∈V，l∈L。

b.多層鄰居節(jié)點(diǎn)。多層鄰居節(jié)點(diǎn)是在a1≤a≤L層與給定節(jié)點(diǎn)x相連接的節(jié)點(diǎn)集。

MNx，a=y：1：x，y，1∈E≥a

在圖1中，節(jié)點(diǎn)x的多層鄰居節(jié)點(diǎn)為：

MNx，1=y，z

MNx，2=y，u

MNx，3=z

（2）多層中心度。中心度代表著節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性。多層中心度可以定義為節(jié)點(diǎn)x與對(duì)應(yīng)的多層鄰居節(jié)點(diǎn)之間的權(quán)重總和與層的數(shù)量和多層網(wǎng)絡(luò)所有節(jié)點(diǎn)數(shù)的比值。

MCDx，a=y∈MNx，awx，y，lm-1L

wx，y，l是邊x，y，l的權(quán)重，對(duì)于本文來講，權(quán)重為1。

三、實(shí)證分析

1.多層航空網(wǎng)絡(luò)特征描述。

本文選取的數(shù)據(jù)為歐洲四家航空公司的航線數(shù)據(jù)[4，5]。將位于不同城市的機(jī)場(chǎng)作為一個(gè)節(jié)點(diǎn)，機(jī)場(chǎng)之間的航線作為邊，構(gòu)造了一個(gè)多層無向非加權(quán)的航空網(wǎng)絡(luò)。

多層航空網(wǎng)絡(luò)中共有335個(gè)機(jī)場(chǎng)節(jié)點(diǎn)，974條邊，如表1所示。其中，如果不考慮層的不同，共有207個(gè)節(jié)點(diǎn)。其中，有128個(gè)節(jié)點(diǎn)是重復(fù)的，重復(fù)的節(jié)點(diǎn)意味著不同的航空公司在同一城市均有機(jī)場(chǎng)。Lufthansa和Ryanair公司的機(jī)場(chǎng)數(shù)超過100，也擁有更多的航線。

表1每一層的節(jié)點(diǎn)數(shù)和邊數(shù)

2.多層鄰居節(jié)點(diǎn)

圖2是層1的多層鄰居節(jié)點(diǎn)分布圖。從圖中可以看到，大部分的節(jié)點(diǎn)含有較少的多層鄰居節(jié)點(diǎn)，多層鄰居節(jié)點(diǎn)的數(shù)量超過12的節(jié)點(diǎn)數(shù)量平均為1～2個(gè)，說明Lufthansa公司所在機(jī)場(chǎng)的航線只有少數(shù)是比較密集的。如圖3所示，超過70%的節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)少于10，超過30個(gè)鄰居節(jié)點(diǎn)的節(jié)點(diǎn)不到10%。多層鄰居節(jié)點(diǎn)的分布體現(xiàn)了多層航空網(wǎng)絡(luò)的無標(biāo)度性。

圖2多層鄰居節(jié)點(diǎn)圖（）

圖3多層鄰居節(jié)點(diǎn)分布統(tǒng)計(jì)（）

圖4為各層的鄰居節(jié)點(diǎn)分布圖，層1和層2分布相似，它們均含有較多的節(jié)點(diǎn)和邊。每個(gè)層的鄰居節(jié)點(diǎn)分布都符合無標(biāo)度網(wǎng)絡(luò)的性質(zhì)。

圖4多層鄰居節(jié)點(diǎn)圖（）

圖5為多層鄰居節(jié)點(diǎn)條形圖，鄰居節(jié)點(diǎn)的數(shù)量以10個(gè)單位為分割。從圖中可以看出，隨著范圍的遞進(jìn)，每層中的節(jié)點(diǎn)數(shù)量逐步在減少，在鄰居節(jié)點(diǎn)數(shù)達(dá)到（21，30）的范圍之后對(duì)應(yīng)的節(jié)點(diǎn)數(shù)明顯減少。統(tǒng)計(jì)結(jié)果顯示，每一層的節(jié)點(diǎn)數(shù)在不同范圍內(nèi)呈現(xiàn)出相同的下降趨勢(shì)，側(cè)面反映出每個(gè)航空公司對(duì)于機(jī)場(chǎng)和航線的拓?fù)浣Y(jié)構(gòu)相似。

圖5多層鄰居節(jié)點(diǎn)條形圖

3.多層中心度

多層中心度MCDx，a取決于多層鄰居節(jié)點(diǎn)MNx，a，當(dāng)MNx，a>0，MCDx，a>0。圖6是第一層中各節(jié)點(diǎn)的多層中心度分布，從圖中可以看出，節(jié)點(diǎn)多集中在多層中心度為0.02以下的區(qū)域，高于0.04的節(jié)點(diǎn)較少。節(jié)點(diǎn)中心度表明節(jié)點(diǎn)在多層網(wǎng)絡(luò)中的重要程度。從圖中可以看出，在第一層中只有少數(shù)的節(jié)點(diǎn)在多層航空網(wǎng)絡(luò)中作用很大。

圖6多層中心度分布圖（）

圖7是各層節(jié)點(diǎn)的多層分布圖，每一層的分布與第一層的分布類似。圖中多個(gè)圖形重疊的節(jié)點(diǎn)代表不同航空公司在該城市均有機(jī)場(chǎng)。從圖中可以找出多層中心度較高的幾個(gè)關(guān)鍵節(jié)點(diǎn)。表2是每一層節(jié)點(diǎn)的多層中心度的變化范圍。

圖7多層中心度分布圖（a=1，2，3，4）

表2多層中心度范圍

層號(hào)1234

最小值1.21E-31.21E-31.21E-31.21E-3

最大值9.59E-21.06E-11.06E-16.55E-2

表3給出了節(jié)點(diǎn)中心度大于0.5的幾個(gè)節(jié)點(diǎn)的多層中心度。通過表3可以直觀的看出多層中心度最大的為節(jié)點(diǎn)12，總共有8個(gè)節(jié)點(diǎn)的多層中心度大于0.5。結(jié)合多層航空網(wǎng)絡(luò)，這8個(gè)節(jié)點(diǎn)對(duì)應(yīng)的機(jī)場(chǎng)就相當(dāng)于航空網(wǎng)絡(luò)中幾個(gè)重要的機(jī)場(chǎng)，節(jié)點(diǎn)12對(duì)應(yīng)的機(jī)場(chǎng)即要找的多層航空網(wǎng)絡(luò)的中心。

表3部分節(jié)點(diǎn)的多層中心度

節(jié)點(diǎn)多層中心度

1660.052

110.053

400.064

710.065

1080.067

20.096

380.096

120.106

四、結(jié)論與展望

通過分析多層航空網(wǎng)絡(luò)的各節(jié)點(diǎn)的多層中心度，找出了多層航空網(wǎng)絡(luò)的中心節(jié)點(diǎn)。未來的主要工作是結(jié)合實(shí)際情況研究該中心節(jié)點(diǎn)的實(shí)際意義，可從以下幾個(gè)方面進(jìn)行：

（1）在航空公司布局機(jī)場(chǎng)時(shí)，可優(yōu)先考慮多層中心節(jié)點(diǎn)的布局，同時(shí)考慮多層中心度較大的其他節(jié)點(diǎn)，以便更好地發(fā)展業(yè)務(wù)；或者在已經(jīng)布局了多層中心節(jié)點(diǎn)時(shí)，可提供更優(yōu)質(zhì)的服務(wù)來增強(qiáng)競(jìng)爭(zhēng)力。

（2）對(duì)于航空網(wǎng)絡(luò)脆弱性研究方面，優(yōu)先考慮對(duì)多層中心節(jié)點(diǎn)提供保護(hù)措施。

（3）可以將多層中心度拓展應(yīng)用于其他多層網(wǎng)絡(luò)的計(jì)算。

（4）可以將現(xiàn)有算法進(jìn)行優(yōu)化，提高計(jì)算效率。（作者單位：濟(jì)南大學(xué)管理學(xué)院）

參考文獻(xiàn)：

[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]俞桂杰， 彭語(yǔ)冰， 褚衍昌. 復(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.