文 軍，羅心雨，鐘佳軒，徐志航

(中國民用航空飛行學院 機場工程與運輸管理學院，四川 廣漢 618307)

分形幾何學(fractal geometry)于20世紀70年代中期由美籍數(shù)學家Benoit B. Mandelbrot提出，至今不過40余年。分形理論是在此基礎上形成的研究分形性質(zhì)及其應用的學科。其最基本特點是用分形維度的方法和視角對客觀事物進行研究，更加符合客觀事物的復雜性與多樣性，更加趨近復雜系統(tǒng)的真實狀態(tài)與真實屬性。

隨著學者們對復雜系統(tǒng)深入研究發(fā)現(xiàn)，大量不同拓撲結(jié)構(gòu)的真實網(wǎng)絡具有3大特征：無標度特征、小世界特征、分形特征。而在研究初期，研究人員并未意識到復雜網(wǎng)絡會存在自相似結(jié)構(gòu)，表現(xiàn)出分形特征。Song等[1]將重整化理論及分形理論中的盒維數(shù)法推廣應用于復雜網(wǎng)絡的研究，揭示了大量真實網(wǎng)絡具有自相似結(jié)構(gòu)，表現(xiàn)出分形特征，為研究復雜網(wǎng)絡提供新角度。分形特征作為大多數(shù)復雜網(wǎng)絡的共性這才真正被認識。張明君[2]將復雜網(wǎng)絡的3大特征兩兩比較后發(fā)現(xiàn)，分形特征與無標度特征互相依存，分形特征與小世界特征此消彼長，分形占主導的網(wǎng)絡更具有魯棒性。分形維數(shù)不僅可以定量刻畫網(wǎng)絡的分形特征，同時也可用于度量分形網(wǎng)絡的魯棒性[3]。

航空網(wǎng)絡是一類典型的復雜網(wǎng)絡，其作為航空運輸實現(xiàn)的載體，一度成為航空運輸領域中熱門的研究對象之一。已有文獻中，對于中國航空網(wǎng)絡拓撲特性的研究大多基于復雜網(wǎng)絡理論。國內(nèi)大量學者證實了中國國內(nèi)航空網(wǎng)絡具有小世界特性，其度分布服從雙段冪律分布。牟建紅等[4]基于航班時刻表，首次將時間信息引入中國航空網(wǎng)絡拓撲結(jié)構(gòu)中，實驗結(jié)果與已有研究相比，其數(shù)據(jù)集中新增機場和航線使網(wǎng)絡呈現(xiàn)出更加顯著的無標度特性和小世界現(xiàn)象。楊麗等[5]對中國航空貨運網(wǎng)絡結(jié)構(gòu)進行分析，證實其呈現(xiàn)出小世界特性，且不存在明顯的社團結(jié)構(gòu)。王興隆等[6]分析結(jié)果表明，多層航線聚合網(wǎng)絡是具有無標度特征的小世界網(wǎng)絡。

大量的研究證實了中國航空網(wǎng)絡的小世界特征和無標度特征，但現(xiàn)有文獻中鮮有研究中國航空網(wǎng)絡的分形特征，對這一特性的研究有助于深入理解網(wǎng)絡結(jié)構(gòu)的復雜性。本文首先采用復雜網(wǎng)絡的拓撲指標對中國航空網(wǎng)絡的基本統(tǒng)計特征進行描述；之后對其度度相關性進行研究，以分析網(wǎng)絡節(jié)點間的連接偏好；最后基于分形理論，分別測算其在無權(quán)和加權(quán)條件下的分形維數(shù)，對中國航空網(wǎng)絡的分形特性進行分析。運用分形理論研究航空網(wǎng)絡的分形特性不僅拓寬了分形理論的應用范圍，也從新的角度研究航空網(wǎng)絡的拓撲特性，為提升航空網(wǎng)絡的魯棒性、抗毀性提供一種新思路，同時也為中國航空網(wǎng)絡布局規(guī)劃提供有力支撐。

1 數(shù)據(jù)與方法

1.1 航空網(wǎng)絡拓撲建模

本文所采用數(shù)據(jù)來源于2015年和2019年夏秋國內(nèi)航空公司國內(nèi)航班正班計劃，涉及國航、東航、南航等45家航空公司。按以下規(guī)則將數(shù)據(jù)進行簡化。

1) 以通航城市作為節(jié)點，將擁有兩個及以上機場的城市的數(shù)據(jù)進行合并。

2) 所統(tǒng)計的機場及航線數(shù)據(jù)不含港澳臺地區(qū)。

3) 對有經(jīng)停機場的航線進行分解，將其分解為起飛機場-經(jīng)停機場和經(jīng)停機場-目的機場兩條航線，并將直飛航線和經(jīng)停航線進行合并。

基于上述簡化規(guī)則，去除各航空公司航線疊加過程中的重復項，分別構(gòu)建中國航空無權(quán)網(wǎng)絡和中國航空加權(quán)網(wǎng)絡。其中，中國航空無權(quán)網(wǎng)絡拓撲模型最終用一個對稱無向圖G=(V,E)表 示，V代表點集合，E代表邊集合；中國航空加權(quán)網(wǎng)絡以航空公司國內(nèi)航班正班計劃中航線一周的總航班量為邊的權(quán)重，用圖G′=(V,E,W)來 表示，W={w1,w2,···,wm}表示網(wǎng)絡權(quán)重的集合。

1.2 研究方法

1.2.1 貪心著色盒覆蓋算法

盒覆蓋法是最早運用于歐氏空間中計算傳統(tǒng)分形體維度的方法，該方法既能用來判斷分形特征，還能求出在歐幾里得空間中圖形的分形維數(shù)，分形維數(shù)被用來定量表征復雜物體的特性，是對事物的粗糙度、不規(guī)則度、復雜性的一種測度。

Song等[7]在基礎的盒覆蓋算法上提出改進的盒子定義，即定義覆蓋復雜網(wǎng)絡節(jié)點的盒子長度lB為盒子覆蓋的節(jié)點中，任意兩點i、j之 間的距離dij都小于lB，對于給定盒子長度，統(tǒng)計出覆蓋整個網(wǎng)絡所需的最少盒子數(shù)，記為NB(l) ， 其度量盒子數(shù)NB與盒子尺寸lB滿足

文獻[8]給出計算復雜網(wǎng)絡的分形維數(shù)的具體算法：緊湊盒子燃燒算法、貪心著色盒覆蓋算法以及最大排除質(zhì)量燃燒算法。

在尋找最小盒子數(shù)時，用到了貪心著色算法，具體步驟如下。

1) 給定網(wǎng)絡G，隨機對G中節(jié)點按照1到n進 行編號；

2) 確定盒子尺寸lB大小，賦值節(jié)點1顏色值為“0”；

3) 設定lB=1， 計算di j(j＜i)， 即節(jié)點i和 節(jié)點j的距離；

4) 如果di j≥lB， 則選擇節(jié)點j的一種顏色值賦給節(jié)點i；

5)i++， 重復步驟3)、4)，直到i=n；

6)lB++， 重復2)、3)、4)，直到lB大于或等于網(wǎng)絡直徑。

圖1為當lB=3時的貪心著色覆蓋算法示意圖。

圖1 lB=3時貪心著色盒覆蓋法演示圖Figure 1 Demonstration of greedy coloring box covering method at lB =3

Song提出的貪心著色盒覆蓋算法依賴于節(jié)點的初始序列，計算過程帶有隨機性，只能盡可能找到最優(yōu)解，且是一種窮舉法，因此存在較高的復雜度。

1.2.2 無權(quán)網(wǎng)絡盒覆蓋算法

姚燦中等[9]利用Welch Powell法對文獻[7]的貪心著色盒覆蓋法算法進行改進，其步驟如下。

1) 將圖G→G2進行交換，變換后得圖G2的節(jié)點按照度序列遞減次序排列；

2)G2→G3，把第1個節(jié)點放進第1個盒子，并依排列次序，將不鄰接節(jié)點1的點全放進第1個盒子；

3) 在未入盒的節(jié)點中，選取度最大的節(jié)點重復2) ，處理完第2個盒子；

4) 重復3) ，直到G2所有節(jié)點全部入盒。

姚燦中等用實驗結(jié)果證實了Powell改進盒覆蓋算法 (box covering improved algorithm with Powell,P-BC) 的有效性，并指出該算法近似不存在隨機性因素。P-BC法的實質(zhì)也是貪心著色盒覆蓋算法，利用Welch Powell法進行改進后能有效降低隨機性和復雜度，在計算實際網(wǎng)絡的分形維數(shù)方面具有更大的優(yōu)越性。

1.2.3 加權(quán)網(wǎng)絡盒覆蓋算法

Wei等[10]摒棄了經(jīng)典盒覆蓋法中盒子長度為整數(shù)的想法，改變了傳統(tǒng)盒子尺寸賦值規(guī)則中逐次加1的習慣，修正了盒覆蓋法中盒子的尺度，提出了適用于加權(quán)網(wǎng)絡的BCANw (box-covering algorithm for weighted networks，加權(quán)網(wǎng)絡盒覆蓋法) 。

具體步驟如下。

1) 計算網(wǎng)絡中直接相連的節(jié)點間的距離值，并按從小到大的距離排序為d1,d2,···,dn；

2) 從1到n隨機對節(jié)點進行編號，確定lB大小，賦值1號節(jié)點顏色為“0”；

3) 設定lB=d1， 對于i號 節(jié)點，計算節(jié)點j與節(jié)點i的 距離di j(j＜i)；

4) 若di j≥lB， 則選擇不同于i號節(jié)點的顏色值賦給j號節(jié)點；

5)lB=d1+d2， 重復步驟3)、4)，直到i=n；

6)lB=d1+d2+···+dn，重復步驟2)、3)、4)，直到lB不小于網(wǎng)絡直徑；

7) 擬合l nNB～lnlB，考察其對應的直線斜率。

若加權(quán)網(wǎng)絡具有分形特征，那么盒子長度與相應的最少盒子數(shù)目應該滿足關系式

2 中國航空網(wǎng)絡分形實證研究

分別根據(jù)2015年和2019年夏秋航季國內(nèi)航空公司國內(nèi)航班計劃表數(shù)據(jù)，利用Gephi軟件進行繪圖，生成中國航空網(wǎng)絡可視化拓撲圖，如圖2所示。

2015年中國航空網(wǎng)絡由196個通航城市和1 598條邊構(gòu)成；2019年中國航空網(wǎng)絡增長到229個通航城市和2 808條邊。從圖2中可以看出，其呈現(xiàn)出層級結(jié)構(gòu)，且頂層結(jié)構(gòu)清晰。核心層的樞紐通航城市與較多節(jié)點相連，節(jié)點度值較大，而邊緣層度值則相對較小。其中，相比于2015年只有北京和上海兩座通航城市節(jié)點度值大于100，至2019年，北京、西安、成都、上海、重慶、昆明、深圳、廣州等主要城市節(jié)點度值已大于100，見表1。

表1 中國航空網(wǎng)絡通航城市節(jié)點度值(前10)Table 1 The node degree of navigable cities in Chinese airline network (Top 10)

圖2 中國航空網(wǎng)絡拓撲結(jié)構(gòu)圖Figure 2 Chinese airline network topology diagram

2.1 網(wǎng)絡的基本統(tǒng)計特征

2.1.1 度及度分布

通航城市作為網(wǎng)絡節(jié)點，其度指與該節(jié)點直接連接的邊 (通航航線) 的數(shù)量。節(jié)點i的度記為

式中，ai j表 示節(jié)點i與 節(jié)點j連通情況，若節(jié)點i與 節(jié)點j之間有直飛航線，則ai j為1；反之，為0。節(jié)點度的大小與節(jié)點的重要性成正比，在航空網(wǎng)絡中，節(jié)點度值的大小通常反映該通航城市的通達性和在整個網(wǎng)絡中的重要性。

其中，n為網(wǎng)絡節(jié)點數(shù)。

中國航空網(wǎng)絡2015年和2019年的平均度分別為16.306和24.524，增長了1.504倍，即2015年平均每個通航城市約與其他16個通航城市有直接的航線連接，到2019年增長至與25個通航城市有直接的航線連接。圖3、4描述了中國航空網(wǎng)絡通航城市節(jié)點度分布及度值的概率分布，反映出中國航空網(wǎng)絡節(jié)點度值整體上呈冪律分布。

圖3 節(jié)點度分布圖Figure 3 Degree distribution

2.1.2 平均路徑長度

將節(jié)點i和j之間的距離di j定義為連接這兩個節(jié)點的最短路徑上的邊的數(shù)目。網(wǎng)絡中任意兩個節(jié)點(不包括自身到自身)之間距離的平均值即平均路徑長度。

2015年網(wǎng)絡的平均路徑長度L1=2.202， 2019年L2=2.111，均意味著任意兩個通航城市之間可通過不到2次轉(zhuǎn)機就能到達。網(wǎng)絡直徑為4，即兩個通航城市之間最多3次轉(zhuǎn)機。網(wǎng)絡的平均路徑長度下降也表明通達性在增強。

2.1.3 聚類系數(shù)

圖4 中國航空網(wǎng)絡節(jié)點度概率分布圖Figure 4 Probabilistic distribution of node degree in Chinese airline network

聚類特性是大多數(shù)實際網(wǎng)絡的共性。某個通航城市節(jié)點的聚類系數(shù)反映該通航城市與其他鄰接通航城市疏密程度，平均聚類系數(shù)反映整個航空網(wǎng)絡中所有通航城市聯(lián)系的疏密程度[11]。運用Matlab計算出中國航空網(wǎng)絡的平均聚類系數(shù)由2015年的0.753到下降至2019年的0.693，表現(xiàn)出很強的聚集性，聚集系數(shù)的下降則表明網(wǎng)絡中樞層級結(jié)構(gòu)在提高。中國航空網(wǎng)絡基本統(tǒng)計指標見表2。

表2 中國航空網(wǎng)絡基本統(tǒng)計指標Table 2 The indicators of network's basic characteristics

通過對網(wǎng)絡基本統(tǒng)計特征的分析，證實了中國航空網(wǎng)絡具有較高的聚類系數(shù)和較短的平均路徑長度，同時度服從冪律分布，表明該網(wǎng)絡具有小世界特征和無標度特征，即盡管網(wǎng)絡本身很大，但網(wǎng)絡中任意兩節(jié)點間存在相對較短的路徑。

2.2 網(wǎng)絡的異配性分析

度度相關性是網(wǎng)絡的一個重要統(tǒng)計特征，它描述了網(wǎng)絡中節(jié)點根據(jù)度值相互選擇連接的偏好特性。對于度為k的節(jié)點i與 其所有鄰節(jié)近點j的鄰點平均度值記為

式中，M為網(wǎng)絡中邊的數(shù)目；kz和kz′分別為第z條邊兩個節(jié)點的度數(shù)，z=1,···,M， -1≤r≤1。若r＞0， 則節(jié)點度具有正相關性；若r＜0，則節(jié)點度具有負相關性；若r=0，網(wǎng)絡無相關性。

如圖5所示，中國航空網(wǎng)絡在2015年當k＞6時和2019年當k＞7時呈現(xiàn)明顯的度負相關，以及計算出2015年和2019年中國航空網(wǎng)絡的Pearson相關系數(shù)r均為負。這說明度大的節(jié)點偏好與度小的節(jié)點相連接，各節(jié)點的度與其所有直接聯(lián)系的鄰節(jié)點的平均度整體表現(xiàn)為負相關。節(jié)點的度值越高，其鄰節(jié)點的平均度越低。隨著度值的增加，這種特征表現(xiàn)越明顯，網(wǎng)絡為異配的。

圖5 中國航空網(wǎng)絡節(jié)點鄰點平均度knn與度值k的分布關系Figure 5 Distribution of nodal knn-degree correlation in Chinese airline network

2.3 無權(quán)網(wǎng)絡盒維數(shù)計算

本節(jié)采用Powell改進盒覆蓋算法，測算中國航空無權(quán)網(wǎng)絡G的盒維數(shù)，對其分形特征進行分析。在2.1節(jié)已計算出模型G的網(wǎng)絡直徑為4，則給定盒子尺寸lB分別為1、2、3、4對中國航空無權(quán)網(wǎng)絡進行覆蓋，運用Matlab編程計算出其對應的最小盒子數(shù)，得到一組(lB,NB)點列 ，見表3。

表3 中國航空無權(quán)網(wǎng)絡覆蓋最小盒子數(shù)NBTable 3 The minimum number of boxes NB in Chinese airline network without weight

對其做雙自然對數(shù)圖，并通過最小二乘法進行擬合，回歸方程如圖6所示，擬合優(yōu)度R2分別為0.995 97、0.999 98，趨近1，線性關系顯著，即2015年和2019年的中國航空無權(quán)網(wǎng)絡皆具有分形特征，其分形盒維數(shù)分別為5.065、5.079。

圖6 中國航空無權(quán)網(wǎng)絡雙對數(shù)坐標圖Figure 6 The ln-ln plots on Chinese airline network without weight

2.4 加權(quán)網(wǎng)絡盒維數(shù)計算

中國航空加權(quán)網(wǎng)絡以國內(nèi)航空公司國內(nèi)航班正班計劃中航線一周的總航班量為權(quán)重，顯然，該權(quán)重為相似權(quán)，即權(quán)重值越大，距離越短，兩通航城市聯(lián)系越密切。定義節(jié)點i與 節(jié)點j之間的距離為

采用式 (11) 計算網(wǎng)絡節(jié)點間距離后得到2015年和2019年的網(wǎng)絡直徑分別為0.426、0.334，均小于1。若運用P-BC法，覆蓋整個網(wǎng)絡只需要一個盒子，無法利用盒維數(shù)分析該網(wǎng)絡的分形特征。因此，本節(jié)采用BCANw法對中國航空加權(quán)網(wǎng)絡分形盒維數(shù)進行測算。

根據(jù)2015年和2019年中國航空加權(quán)網(wǎng)絡的網(wǎng)絡直徑，分別給定了95和99個盒子尺寸對中國航空加權(quán)網(wǎng)絡進行覆蓋，并計算出對應的最小盒子數(shù)，將計算結(jié)果進行雙對數(shù)線性回歸擬合。如圖7所示，擬合后得到圖像在一定尺度內(nèi)呈線性相關 (擬合優(yōu)度R2分別為0.946 82、0.945 70，趨近1)，擬合直線斜率的絕對值分別為2.164、2.262，即2015年中國航空加權(quán)網(wǎng)絡的盒維數(shù)為2.164，2019年網(wǎng)絡的加權(quán)盒維數(shù)為2.262，均表現(xiàn)出分形特征。

圖7 中國航空加權(quán)網(wǎng)絡雙對數(shù)坐標圖Figure 7 The ln-ln plots on Chinese airline network without weight

在利用盒覆蓋法計算中國航空網(wǎng)絡分形結(jié)構(gòu)特征時，通航城市之間的連接深度可以通過盒子大小來體現(xiàn)。假設某個盒子長度中整個網(wǎng)絡需要更多的盒子來進行覆蓋，則該航空網(wǎng)絡中通航城市間的連接關系更復雜，航空網(wǎng)絡覆蓋程度越高，其拓撲結(jié)構(gòu)愈加完善，分形維數(shù)越大。

2015年至2019年，在無權(quán)和加權(quán)條件下，中國航空網(wǎng)絡隨著網(wǎng)絡節(jié)點和航線的增加與結(jié)構(gòu)的完善，分形維數(shù)呈增長趨勢，其變化確切地表征了航空網(wǎng)絡復雜度的演化與發(fā)展。

中國航空網(wǎng)絡呈現(xiàn)出小世界特性，網(wǎng)絡中兩點通過盡量少的連接就能夠到達，集群程度高，運輸深度小，使得運輸快速便捷。然而，純粹的小世界網(wǎng)絡由于集群點傾向于與其他的集群點相連，Hub與Hub間強烈吸引，因此在面對對Hub的目標攻擊時極度脆弱，抗毀性差。分形網(wǎng)絡集群節(jié)點則更傾向于與更少連通度的節(jié)點相連，即Hub之間連接的非同源匹配性導致了網(wǎng)絡分形結(jié)構(gòu)的產(chǎn)生，正是這種非同源匹配性能夠增強網(wǎng)絡的魯棒性[15]。

3 結(jié)論

從分形視角對中國航空網(wǎng)絡的拓撲特性進行實證研究。通過對度及度分布、平均路徑長度、聚類系數(shù)的測算，驗證了已有文獻的結(jié)論：中國航空網(wǎng)絡具有無標度特征和小世界特征。對網(wǎng)絡度度相關性進行分析表明，中國航空網(wǎng)絡為異配網(wǎng)絡，度大的節(jié)點偏好于連接度小的節(jié)點?；诜中卫碚摚謩e在無權(quán)和以一周的航班量為權(quán)重的加權(quán)條件下對中國航空網(wǎng)絡的盒維數(shù)進行測算。實驗結(jié)果證實了在一定尺度內(nèi)，中國航空網(wǎng)絡具有分形特征，表明其具有一定的內(nèi)在魯棒性效能。網(wǎng)絡的分形特征在2015年 ～ 2019年間演化速率雖較為緩慢，但是一種正向的演化。

本文只是對中國航空網(wǎng)絡的分形特征進行初步分析，網(wǎng)絡中小世界特征和分形特征誰更占主導地位，以及不同邊權(quán)對中國航空加權(quán)網(wǎng)絡分形特征的影響，仍有待于進一步的研究探索。