基于度和聚類系數的中國航空網絡重要性節點分析

閆玲玲，陳增強,，張青

(1.南開大學 計算機與控制工程學院，天津 300350； 2.南開大學 智能機器人技術天津市重點實驗室，天津 300350; 3.中國民航大學 理學院, 天津 300300)

?

基于度和聚類系數的中國航空網絡重要性節點分析

閆玲玲1,2，陳增強1,2,3，張青3

(1.南開大學 計算機與控制工程學院，天津 300350； 2.南開大學 智能機器人技術天津市重點實驗室，天津 300350; 3.中國民航大學 理學院, 天津 300300)

運用度中心性、接近中心性、介數中心性、特征向量中心性和半局部中心性5種方法，對中國航空網絡進行節點重要性排序；對重要節點分別進行蓄意攻擊和隨機攻擊，采用脆弱性指標驗證排序方法的有效性，仿真結果表明介數中心性能夠更準確地刻畫中國航空網絡中節點的重要性；在航空網絡的背景下,將節點的直接影響力和節點鄰居之間連接的緊密程度結合起來，提出了一種基于度和聚類系數的新指標，經中國航空網絡實例驗證,該指標的評價準確性僅次于介數中心性，但是其時間復雜度比介數中心性低很多。

航空網絡；節點重要性；度；聚類系數；復雜網絡

自20世紀初飛機問世以來，航空運輸系統飛速發展。與其他運輸方式相比，航空運輸具有及時、高效、靈活的優勢，尤其是在長距離運輸和國際客運方面的重要作用日益凸顯[1]。航空運輸系統是一個易受環境影響的開放的復雜系統，隨著系統規模的不斷擴大，它在帶給人們便利的同時也帶來了一系列的問題。航班延誤已經成為人們司空見慣的現象，于是，在自然災害或人為因素導致航班不能正常起降的突發情況下，航空運輸系統能夠保持其魯棒性，成為人們越來越關注的問題。

劉宏鯤等[2]研究表明，中國城市航空網絡具有較大的聚類系數和較短的平均路徑長度，其度分布服從雙段冪律分布，是一個具有小世界網絡特性的無標度網絡； 姚紅光等[3]通過仿真實驗得出，中國航空網絡在面對隨機干擾時魯棒性較強，而在蓄意攻擊下魯棒性較差；不同的城市節點對于網絡魯棒性的貢獻程度不同，目前有40余個核心城市在中國航空網絡中占有舉足輕重的地位。

航空網絡中，準確地評估和度量節點的重要性在提高網絡的可靠性與抗毀性方面扮演著非常重要的角色。在由城市節點和通航城市間的直飛航線所構成的航空網絡中, 如果受突發事件的影響，某城市節點陷入癱瘓，那么這就意味著同時取消了與該城市節點相連的所有的航線，從而有可能引發網絡中其他通航城市之間的一些運輸路徑中斷[4]。例如，2015年7月11日，超強臺風“燦鴻”逼近上海，受臺風“燦鴻”影響，上海機場終端區的通行能力下降50%左右，共計取消航班300多個架次。因此，準確評估航空網絡中的重要節點，并針對其可能發生的突發狀況提前制定完備的候選方案和補救措施，可以有效避免網絡因受到外界干擾而造成航班大面積延誤，從而保證航空運輸安全高效地運營。

1 理論基礎

將航空網絡抽象為一個由點集V=[v1v2…vn]和邊集E=[e1e2…em]組成的無向圖G=[VE]，頂點數記為N=|V|，邊數記為M=|E|。圖的鄰接矩陣記為An×n=(aij)，當且僅當節點vi與vj之間有連邊時aij=1，否則aij=0。

定義1無向網絡中節點vi的度ki是指與節點直接相連的邊的數目。它與節點的重要程度有很大的關系。一般而言，ki的值越大，節點就越重要。其表達形式為

定義2節點距離定義為連接這兩個節點的最短路徑上的邊的數目，用dij表示。

定義3網絡的平均路徑長度L定義為任意兩個節點之間距離的平均值，即

定義4網絡中一個度為ki的節點vi的聚類系數C(i)定義為

式中：Ei是節點vi的ki個鄰節點之間實際存在的邊數，即節點vi的ki個鄰節點之間實際存在的鄰居對的數目。聚類系數表征在網絡中某一節點的兩個相鄰節點也相鄰的概率，反映的是網絡的集聚化程度。

2 無向網絡節點重要性指標

在復雜網絡領域里評價節點重要性的方法有很多，本質上都是源于圖論和基于圖的數據挖掘，主要分為以下3類：社會網絡分析、系統科學分析、信息搜索領域分析[5]。其本質上都是源于圖論以及基于圖的數據挖掘，主要從網絡拓撲結構入手進行分析。

社會網絡分析方法起始于20世紀40年代末，在評價節點重要性的研究領域中是比較常見的。它主要基于這樣一種假設：“重要性等價于顯著性”，即節點的重要性等價于該節點與其他節點的連接而使其具有的顯著性[6]。該方法主要以網絡的拓撲結構為切入點，在不破壞網絡連通性的前提下對重要節點進行研究，并且通常不考慮節點集的重要性[7]。通過分析網絡中的某種有用信息來區分不同節點的重要性差異，其主要的分析指標包括節點的度(degree)、接近度(closeness)、介數(betweenness)、特征向量(eigenvector)等。

2.1 度中心性

度中心性(degree centrality)[8]，就是按照度值的大小對節點進行排列。它是網絡中刻畫節點重要性最簡單而又非常重要的指標。具有相同度值的節點在不同規模的網絡中的重要程度是不同的，因此為了便于比較，將節點的度中心性進行歸一化處理：

顯然，度中心性描述的是節點對于其鄰居節點的直接影響力，它認為一個節點的度值越大，與之有直接聯系的鄰居就越多，也就越重要[9]。這種方法簡單直觀，計算的復雜度低，但是它僅僅考慮了節點的最局部的信息，具有非常大的片面性，沒有辦法準確地刻畫網絡中節點的重要程度。例如，“橋節點”雖然只有兩條邊相連，但是在網絡中處于重要的核心地位。

2.2 接近中心性

接近中心性(closeness centrality)[10]反映的是節點在網絡中居于中心的程度。它的基本思想是如果一個節點能很容易地與所有其他節點進行互動，那么它就處在網絡的中心位置，也就是說它到其他所有節點的距離要足夠短。因此，接近中心性可以用最短距離來刻畫。假設節點vi和vj之間的最短距離記為dij，則可以計算任意一個節點vi到網絡中其他節點的平均最短距離：

于是節點vi的接近中心性定義為di的倒數，即：

該定義只能在連通的網絡中使用，因此文獻[11]對上式進行了改進，使其能夠用于非連通網絡中，即：

如果節點vi和vj之間沒有路徑可達，則定義dij=，即1/dij=0。

由上式可知，節點的接近中心性越大，表明該節點越接近網絡的中心位置，那么它在網絡中就越重要。這一類節點與其他節點的聯系并非最多，但是與網絡中其他節點的距離總和最短，也就是該節點在網絡中具有最佳視野，可以察知網絡中所發生的事情以及信息的流通方向。與前面的度中心性相比，接近中心性更能反映網絡的全局結構，但是這種方法的計算復雜度較高，并且對網絡的拓撲結構具有依賴性，例如它可以準確地發現星形網絡結構的中心節點，但是并不適用于隨機網絡。

2.3 介數中心性

介數中心性[12](betweenness centrality)一般是指最短路徑介數中心性(shortest path BC)。簡單地講，它刻畫了節點對網絡中沿最短路徑傳輸的網絡流的控制力，很好地描述了網絡中節點可能需要承載的流量。

節點vi的介數定義為

節點的介數值越高，表明流經它的網絡流越多，那么這個節點就越有影響力。與此同時，這也意味著該節點更容易發生擁塞，成為網絡的瓶頸。介數中心性能夠非常準確地找到網絡中“流量”大的節點，但是它的時間復雜度為O(N3)，計算效率低，對于大型的網絡并不適用。

2.4 特征向量中心性

特征向量中心性(eigenvector centrality)[8]是評價網絡中節點重要性的一個重要指標。前面介紹的幾種方法把周圍的鄰居節點視為同等重要，僅僅從鄰居節點的數量上來考慮節點的重要性。而特征向量中心性同時兼顧了鄰居節點的數量和質量對節點重要性的影響，認為一個節點的重要性不僅取決于該節點鄰居的數量, 而且取決于每個鄰居節點的重要程度。特征向量中心性指標是指網絡鄰接矩陣對應其最大特征值的特征向量，即：

式中：λ為鄰接矩陣A的最大特征值，e=[e1e2…en]T為鄰接矩陣A的最大特征值λ對應的特征向量。

2.5 半局部中心性

在以上提出的幾種方法中，度中心性雖然簡單直觀，計算的復雜度低，但只考慮了局部信息，并不能準確刻畫節點的重要程度。介數中心性和接近中心性等基于全局信息的指標，雖然能夠準確的定義重要節點，但是由于其計算的復雜性，不能應用于大規模的復雜網絡。為了兼顧算法的準確度和計算效率，Chen[13]等選取網絡中節點的四階鄰居信息，提出了基于半局部信息的節點重要性排序方法，稱為半局部中心性(semi-local centrality)。

半局部中心性μSLC(i)定義為

式中：Γ(j)表示節點vj的一階鄰居節點的集合，N(w)指從vw出發兩步內可以到達的鄰居的數目，稱為節點vw的兩層鄰居度。

相比于度中心性的一階鄰居信息，半局部中心性考慮了節點的四階鄰居信息，因此其準確性比度中心性更好。于此同時，計算N(w)只需要遍歷節點vw的兩層鄰居節點，因此其計算的復雜度相較于介數中心性和接近中心性更低。

3 中國航空網絡重要性節點分析

3.1 網絡構建與結構特性

以中國民用航空局官方網站公布的夏秋航季客運航線相關數據為樣本構建中國航空網絡模型，其中機場所在的城市為網絡節點，通航城市之間的直飛航線為網絡的邊。這樣形成了148個節點，1 153條無向邊(2 306條航線)的中國航空網絡(見圖1)。將中國航空網絡用一個148×148的鄰接矩陣A表示，如果節點vi和vj之間有可達的航班，則aij=1；反之aij=0，于是得到一個對稱矩陣。

圖1 中國航空網絡結構圖

在此需要說明的是：

1)網絡中所選的航線均為往返航線，因此在后期運算過程中不需要考慮航線的方向問題；

2)對于擁有兩個及以上機場的城市，將其數據進行合并，如上海的浦東機場和虹橋機場的數據可統一合并成到城市節點“上海”中。

節點的度、平均路徑長度和聚類系數是描述復雜網絡拓撲結構最基本的特征參量。本文使用的中國航空網絡樣本，平均度為15.58，也就是說平均每個城市機場約與其他16個城市有直接的航空聯系；Pearson相關系數[14]r=-0.384 3，說明中國航空網絡是度—度負相關的，度值大的節點更傾向于和度值小的節點相連接。平均路徑長度為2.216 5，意味著任意兩個城市機場通過不到2次轉機就可以相互連通；聚類系數為0.687 7，表現出較強集聚性，說明中國航空網絡各節點城市之間更傾向于形成短距離的聯系[15]。由此可見，中國航空網絡具有較大的聚類系數和較小的平均路徑長度，表現出了小世界網絡特性。而圖2表明，中國航空網絡服從雙冪律分布，具有無標度特性。

中國航空網絡城市節點度與聚類系數相關性如圖3所示。可以看出，隨著節點度值k的不斷增加，聚類系數C(k)的數值是不斷下降的，也就是說節點的度和聚類系數呈負相關。這說明在中國航空網絡中，度值小的城市節點比度值大的城市節點更趨向于聚集成團。

圖2 中國航空網絡城市節點度分布

圖3 中國航空網絡城市節點度與聚類系數相關性

3.2 中國航空網絡重要性節點排序

下面用本文中提到的幾種無向網絡節點重要性評價指標中國航空網絡模型的節點重要程度進行排序，排序結果見表1。

節點的度反映了該機場與其他機場通航能力的大小。中國航空網絡的度分布呈現出明顯的東西差異，結合中國航空網網絡的空間結構，從表1中可以看出，度值較大的節點主要集中東部較發達地區，如北京 (102)、上海(83)、廣州(83)、深圳(69)、杭州(52)、南京(51)以及各個省會城市，如成都(61)、西安(56)、昆明(56)、重慶(56)。

接近中心性是用網絡中的節點到其他節點的平均最短距離來衡量的，因此接近中心性越小，意味著該節點在網絡中越處于中心地位，從而也就越不容易受到其他結點連通情況的控制。也就是說，接近中心性數值較大的機場相對于數值較小的機場獨立性更強，不太容易受到其他機場通航狀況的影響。而接近中心性Top10的節點排序結果基本上跟度中心性保持一致，都表現出明顯的東西差異，這一點在特征向量中心性和半局部中心性中都有所體現。

節點的介數中心性反映了該機場在網絡運輸中的中轉和銜接能力。介數中心性高的節點在地區網絡間的連接中起到了橋梁的作用。中國航空網絡節點的介數中心性排序中，北京依然排在第1位，但是排在第2位的烏魯木齊在其他排序結果的前十中從未出現過，排在第3位的昆明只在度中心性排序中排在第七位。從空間結構上可以看出新疆地區的城市節點大多數通過烏魯木齊與整個航空網絡連接，若移除烏魯木齊，則新疆地區的大部分城市節點將變為孤立節點，而昆明也同樣起到非常重要的橋梁作用。

表1 排名前10中國航空網絡各中心性指標

3.3 用網絡的魯棒性和脆弱性評價排序算法

利用之前的節點重要性評價方法對中國航空網絡的重要節點進行排序之后，分別按照節點的重要性從大到小的順序，依次刪除網絡中的節點。則節點移除后網絡的破壞程度可以用最大連通子圖的相對大小，全局效率以及脆弱性指標來進行評價。

最大連通子圖概念的提出，是為了描述網絡中的節點或連邊由于一些內部或外部的原因所發生的變化。簡單來說，最大連通子圖就是一個網絡的眾多連通子圖中包含節點最多的那個子圖。

網絡中，節點vi和vj之間的效率為兩點之間最短距離的倒數，即1/dij。于是網絡的全局效率[16]就定義為所有節點對效率的平均值，即

如果用i/n表示移除的節點比例，用σ(i/n)表示移除i/n比例的節點后最大連通子圖的相對大小，則該節點移除方式下網絡的魯棒性(robustness)可以用R-指標[17]來評價。具體定義為

顯然，無論針對哪種算法都能得到如下結果

所以在任何網絡中，無論用何種算法移除節點，R∈(0，1/2)。因此，文獻[18]定義V-指標來衡量網絡對所實施的節點移除方法的脆弱性(vulnerability)。

V=1/2-R

可見，脆弱性指標的值越大，表明采用的攻擊方法效果越好。于是，分別采用度中心性、接近中心性、介數中心性、特征向量中心性和半局部中心性5種方法對中國航空網絡進行攻擊，畫出i/n和σ(i/n)在二維坐標上的曲線，并用脆弱性指標考察這5種方法的攻擊效果，同時與隨機攻擊網絡的方法得到的效果進行比較。

圖4為對中國航空網絡模型分別進行隨機攻擊和蓄意攻擊后，網絡中移除節點的比例和最大連通集的規模之間的關系。在此需要說明的是，采用的攻擊方式是同時移除i/n比例的節點，計算剩余網絡中最大連通集所占的比例。

圖4 移除節點比例和最大連通集規模的關系(傳統方法的攻擊效果)

從圖4可以看出，相比于蓄意攻擊，隨機攻擊呈現的攻擊效果較差，這表明中國航空網絡對于隨機攻擊具有較好的魯棒性。在蓄意攻擊的仿真實驗中，基于介數攻擊下的指標下降率遠遠高于基于其他4種方法攻擊下的指標下降率，而且下降速度很快，呈陡峭直線下降趨勢。這表明針對中國航空網絡，基于介數中心性的節點重要性排序方法效果是最好的，介數中心性能夠更準確地刻畫網絡中節點的重要性。

基于各種攻擊方法的中國航空網絡脆弱性指標排序在表2中給出，對比發現，蓄意攻擊下的脆弱性指標遠遠高于隨機攻擊。在蓄意攻擊中，介數中心性的指標Vb明顯高于其他4種，排名第4的半局部中心性和排名第5的特征向量中心性在數值上比較接近。此外，從最大連通集的曲線圖中也不難發現，半局部中心性和特征向量中心性的曲線是非常相近的。這就證明對于中國航空網絡，半局部中心性和特征向量中心性的評價方法效果類似。

表2 中國航空網絡脆弱性指標排序

Table 2 The ranking of vulnerability index of Chinese aviation network

次序攻擊方法脆弱性指標1介數中心性0.4792度中心性0.3603接近中心性0.3414半局部中心性0.3145特征向量中心性0.3126隨機攻擊0.024

另外，值得注意的是，當采用介數中心性對網絡進行攻擊的時候，曲線一開始就陡然下降，這一現象在其他攻擊方法下并沒有出現。單獨觀察介數攻擊下網絡的變化，發現在對北京進行攻擊之后，網絡的最大連通子圖相對大小為0.993，而當對烏魯木齊進行攻擊之后，網絡的最大連通子圖相對大小驟然下降至0.047，網絡幾乎陷入癱瘓狀態，這表明類似于烏魯木齊這樣的“橋”節點對于網絡魯棒性的影響舉足輕重。

根據脆弱性指標判斷，介數中心性能夠更準確地描述節點的重要性，因此取基于介數中心性方法排列出的前20名節點城市，分別單獨移除這些節點，用分析對網絡造成的影響，具體數據見表3。

表3 機場失效后網絡的全局傳輸效率

Table 3 The global transmission efficiency of the network with the failure of airport

次序城市σ(i/n)EΔE/E01北京0.9930.4790.0472烏魯木齊0.9660.4660.0773昆明0.9600.4640.0794廣州0.9870.4830.0375上海0.9870.4840.0356成都0.9800.4800.0457西安0.9800.4800.0438深圳0.9930.4910.0229重慶0.9930.4910.02010長沙0.9800.4820.04011呼和浩特0.9930.4930.01712貴陽0.9870.4880.02613沈陽0.9930.4930.01814哈爾濱0.9870.4890.02615大連0.9930.4930.01816杭州0.9930.4920.01917合肥0.9870.4880.02618長春0.9870.4890.02519廈門0.9930.4920.01820桂林0.9930.4930.018

用σ(i/n)表示移除i/n比例的節點后最大連通子圖的相對大小，E為網絡的全局效率，E0為原始網絡的全局效率，ΔE為網絡減少的效率。結果表明，昆明機場的移除對網絡的全局效率影響最大，其次是烏魯木齊和北京。這也就進一步說明，昆明和烏魯木齊在中國航空網絡中的影響力不容小覷，從而驗證了介數中心性指標的準確性。

這些城市在空間結構上基本上覆蓋了中東部各地區，進一步觀察局部地區的機場影響力情況，得到各個地區影響力最強的機場城市：華北地區——北京、華東地區——上海、華中地區——長沙、華南地區——廣州、西北地區——烏魯木齊、西南地區——昆明以及東北地區——哈爾濱。

4 簇度指標的提出

在航空網絡的背景下，介數中心性能夠準確評價網絡中節點的重要性，但其算法的時間復雜度較高，使其在實際應用中受到限制。

研究表明，除了節點鄰居的直接影響力之外，鄰居之間相互聯系的緊密程度在節點的重要性評價中也起著至關重要的作用。Ugander等[19]對 Facebook 上一個用戶收到某個郵件聯系人的邀請信而成為 Facebook 用戶情況進行了分析, 發現影響節點重要性的決定性因素不是鄰居節點的數目，而是鄰居節點間形成的連通子圖的數目。Centola[20]認為節點的傳播影響力與節點的聚類系數有關，聚類系數越大越不利于信息的廣泛傳播。Chen等[21]在此基礎上提出了一種針對有向網絡的 ClusterRank算法，采用SIR傳播模型進行仿真實驗，結果表明該算法優于一些基準算法。任卓明等[4]將節點的二階鄰居度和聚類系數結合起來，提出了一種新的節點重要性評價方法，并分別用美國航空網絡以及美國西部電力網驗證了方法的有效性。

由此得出結論，局部聚類系數的增大對信息的傳播是具有阻礙作用的，如果節點的鄰居節點更傾向于互相連接，那么以節點為起始點，更容易形成一個局部的區域；相反，如果節點的鄰居更傾向于連接除其鄰居外的其他節點，那么信息才能夠迅速在較大的范圍內傳播。例如在圖5中，節點3和節點5具有相同的度值ki以及相同的其鄰居度之和，即k3=k5=3,f3=f5=9，但是節點5的聚類系數比節點3更小(C3=0.33,C5=0)，也就意味著節點5擁有比節點3更高的影響力。這是因為節點5的鄰居節點更傾向于連接其他節點而不是互相連接，這樣就能把信息傳播到更廣的范圍內。

圖5 示例網絡拓撲結構

可見，節點的度和聚類系數對刻畫其重要性都具有非常重要的意義。將節點的直接影響力和節點鄰居之間連接的緊密程度結合起來，提出一種新的指標即簇度指標為：

μDCL(i)=ki·α-C(i)(α>1)

式中：ki為節點vi的度，α為可調參數，C(i)為節點i的聚類系數。

在此需要說明的是：

1)Chen和任卓明等在構造節點重要性指標中用到了二階鄰居度，但是由于航空網絡的特殊性，即中轉成本造成的平均路徑長度較小，節點的直接影響力在評價節點重要性的過程中占主導地位。

2)由于節點的聚類系數C(i)可能為0，故構造減函數α-C(i)(α>1)，并通過仿真實驗得到α的最優值，在后面的分析中我們將以中國航空網絡為樣本作出詳細的描述。

5 實驗分析

為了驗證簇度指標對節點重要性的度量效果，分別采用簇度指標以及上文提到的6種方法對中國航空網絡進行蓄意攻擊仿真實驗，并用脆弱性指標來評價攻擊效果。

經過調試得出，對于函數μDCL(i)，當α的取值范圍為[4 724,4 952]時，脆弱性指標取最大值0.436，即得到的攻擊效果最好。

網絡中移除節點的比例和最大連通集的規模之間的關系由圖6給出。從圖6中可以看出，按照簇度指標排列出的節點重要性順序對中國航空網絡進行蓄意攻擊，得到的脆弱性指標數值為0.405,攻擊效果僅次于介數中心性。但是介數的時間復雜度為O(N3)；而該指標的時間復雜度為O(N)，比介數中心性要快很多。例如在中國航空網絡中，用介數排序需要0.03 s，而用簇度指標排序只需要0.01 s。

圖6 移除節點比例和最大連通集規模的關系(簇度指標與傳統方法的攻擊效果對比)

6 結束語

本文分別用度中心性、接近中心性、介數中心性、特征向量中心性和半局部中心性5種方法對中國航空網絡模型進行了分析，將網絡中的節點按照重要性從大到小進行排序，并列出了重要性排名前10的節點城市；然后按排列出的節點次序對中國航空網絡進行蓄意攻擊，用脆弱性指標考察這5種方法的攻擊效果。仿真結果表明，相比于其他4種方法，基于介數中心性的節點重要性排序方法能夠更準確地刻畫網絡中節點的重要性。進而根據介數中心性得到的排序結果分別單獨攻擊各個城市節點，觀察機場失效后網絡的全局效率，分析得出各個局部地區的重要性節點。

此外，在航空網絡的背景下,將節點的直接影響力和節點鄰居之間連接的緊密程度結合起來，提出了一種基于度和聚類系數的新指標。對中國航空網絡的仿真研究結果表明，該指標的評價準確性僅次于介數中心性，但是其時間復雜度比介數中心性低很多，具有很好的實用價值。

[1]劉宏鯤, 周濤. 中國城市航空網絡的實證研究與分析[J]. 物理學報, 2007, 56(1): 106-112. LIU Hongkun, ZHOU Tao. Empirical study of Chinese city airline network[J]. Acta physica sinica, 2007, 56(1): 106-112.

[2]劉宏鯤. 中國航空網絡的結構及其影響因素分析[D]. 成都: 西南交通大學, 2007. LIU Hongkun. Analyzing the structure of Chinese aviation network and impact factors[D]. Chengdu: Southwest Jiaotong University, 2007.

[3]姚紅光, 朱麗萍. 基于仿真分析的中國航空網絡魯棒性研究[J]. 武漢理工大學學報: 交通科學與工程版, 2012, 36(1): 42-46. YAO Hongguang, ZHU Liping. Research on robustness of China’s aviation network based on simulation analysis[J]. Journal of Wuhan university of technology: transportation science & engineering, 2012, 36(1): 42-46.

[4]任卓明, 邵鳳, 劉建國, 等. 基于度與集聚系數的網絡節點重要性度量方法研究[J]. 物理學報, 2013, 62(12): 128901. REN Zhuoming, SHAO Feng, LIU Jianguo, et al. Node importance measurement based on the degree and clustering coefficient information[J]. Acta physica sinica, 2013, 62(12): 128901.

[5]張珍, 張振宇, 宋蔓蔓. 一種基于最短路徑介數的重要節點發現算法[J]. 計算機工程與應用, 2013, 49(21): 98-100. ZHANG Zhen, ZHANG Zhenyu, SONG Manman. Important node searching algorithm based on shortest-path betweeness[J]. Computer engineering and applications, 2013, 49(21): 98-100.

[6]BURT R S, MINOR M J. Applied Network Analysis[M]. Newbury Park, CA: Sage, 1983: 195-222.

[7]赫南, 李德毅, 淦文燕, 等. 復雜網絡中重要性節點發掘綜述[J]. 計算機科學, 2007, 34(12): 1-5, 17. HE Nan, LI Deyi, GAN Wenyan, et al. Mining vital nodes in complex networks[J]. Computer science, 2007, 34(12): 1-5, 17.

[8]BONACICH P. Factoring and weighting approaches to status scores and clique identification[J]. The journal of mathematical sociology, 1972, 2(1): 113-120.

[9]汪小帆, 李翔, 陳關榮. 網絡科學導論[M]. 北京: 高等教育出版社, 2012. WANG Xiaofan, LI Xiang, CHEN Guanrong. Network science: an introduction[M]. Beijing: Higher Education Press, 2012.

[10]FREEMAN L C. Centrality in social networks conceptual clarification[J]. Social networks, 1978, 1(3): 215-239.

[11]LATORA V, MARCHIORI M. Efficient behavior of small-world networks[J]. Physical review letters, 2001, 87: 198701.

[12]FREEMAN L C. A set of measures of centrality based upon betweenness[J]. Sociometry, 1977, 40(1): 35-41.

[13]CHEN Duanbing, Lü Linyuan, SHANG Mingsheng, et al. Identifying influential nodes in complex networks[J]. Physica A, 2012, 391(4): 1777-1787.

[14]NEWMAN M E J. The structure and function of complex networks[J]. SIAM review, 2003, 45(2): 167-256.

[15]王姣娥, 莫輝輝, 金鳳君. 中國航空網絡空間結構的復雜性[J]. 地理學報, 2009, 64(8): 899-910. WANG Jiao’e, MO Huihui, JIN Fengjun. Spatial structural characteristics of Chinese aviation network based on complex network theory[J]. Acta geographica sinica, 2009, 64(8): 899-910.

[16]LATORA V, MARCHIORI M. Efficient behavior of small-world networks[J]. Physical review letters, 2001, 87(19): 198701.

[17]SCHNEIDER C M, MOREIRA A A, ANDRADE JR J S, et al. Mitigation of malicious attacks on networks[J]. Proceedings of the national academy of sciences of the United States of America, 2011, 108(10): 3838-3841.

[18]IYER S, KILLINGBACK T, SUNDARAM B, et al. Attack robustness and centrality of complex networks[J]. PLoS one, 2013, 8(4): e59613.

[19]UGANDER J, BACKSTROM L, MARLOW C, et al. Structural diversity in social contagion[J]. Proceedings of the national academy of sciences of the United States of America, 2012, 109(16): 5962-5966.

[20]CENTOLA D. The spread of behavior in an online social network experiment[J]. Science, 2010, 329(5996): 1194-1197.

[21]CHEN Duanbing, GAO Hui, Lü Linyuan, et al. Identifying influential nodes in large-scale directed networks: the role of clustering[J]. PLoS one, 2013, 8(10): e77455.

閆玲玲，女， 1990年生，碩士研究生，主要研究方向為復雜網絡。

陳增強，男，1964年生，教授， 博士生導師，主要研究方向為智能控制、 智能信息處理，曾獲天津市自然科學二等獎，發表學術論文100余篇。

張青，女，1965年生，教授，主要研究方向為復雜系統建模與控制、多智能體系統，發表學術論文30余篇。

Analysis of key nodes in China’s aviation network based on the degree centrality indicator and clustering coefficient

YAN Lingling1,2， CHEN Zengqiang1,2,3， ZHANG Qing3

(1. College of Computer and Control Engineering, Nankai University, Tianjin 300350, China; 2. Key Laboratory of Intelligent Robotics of Tianjin, Nankai University, Tianjin 300350, China; 3. College of Science, Civil Aviation University of China, Tianjin 300300, China)

This paper determines the key nodes of China’s aviation network based on degree centrality, closeness centrality, ‘betweenness’ centrality, eigenvector centrality, semi-local centrality indicators, and then ranks these nodes in descending order of importance. Using a vulnerability index and reviewing risks from deliberate and random attack the effectiveness of the sorting methods is then evaluated. It is apparent from the corresponding vulnerability indices that the aviation network of China is most vulnerable to targeted attacks according to the betweenness centrality indicator. Moreover, based on the aviation network, this paper proposes a new evaluation method, which takes into account not only the number of neighbors, but also the clustering coefficient. Focusing on China’s aviation network, the experimental results demonstrate that the evaluation accuracy of the new index ranks only second to the betweenness centrality, and is more efficient compared with betweenness centrality as regards time complexity.

aviation network; key nodes; degree; clustering coefficient; complex network

2016-01-15.

日期：2016-08-24.

國家自然科學基金項目(61573199)；天津自然科學基金項目(14JCYBJC18700).

閆玲玲. E-mail：yanlingling@mail.nankai.edu.cn.

N94

A

1673-4785(2016)05-0586-08

10.11992/tis.201601024

http://www.cnki.net/kcms/detail/23.1538.TP.20160824.0929.014.html

閆玲玲，陳增強，張青.基于度和聚類系數的中國航空網絡重要性節點分析[J]. 智能系統學報， 2016, 11(5): 586-593.

英文引用格式：YAN Lingling，CHEN Zengqiang，ZHANG Qing.Analysis of Key Nodes in China’s Aviation Network Based on the Degree Centrality Indicator and Clustering Coefficient[J]. CAAI transactions on intelligent systems, 2016,11(5): 586-593.