閆玲玲，陳增強(qiáng),，張青

(1.南開(kāi)大學(xué) 計(jì)算機(jī)與控制工程學(xué)院，天津 300350； 2.南開(kāi)大學(xué) 智能機(jī)器人技術(shù)天津市重點(diǎn)實(shí)驗(yàn)室，天津 300350; 3.中國(guó)民航大學(xué) 理學(xué)院, 天津 300300)

?

基于度和聚類(lèi)系數(shù)的中國(guó)航空網(wǎng)絡(luò)重要性節(jié)點(diǎn)分析

閆玲玲1,2，陳增強(qiáng)1,2,3，張青3

(1.南開(kāi)大學(xué) 計(jì)算機(jī)與控制工程學(xué)院，天津 300350； 2.南開(kāi)大學(xué) 智能機(jī)器人技術(shù)天津市重點(diǎn)實(shí)驗(yàn)室，天津 300350; 3.中國(guó)民航大學(xué) 理學(xué)院, 天津 300300)

運(yùn)用度中心性、接近中心性、介數(shù)中心性、特征向量中心性和半局部中心性5種方法，對(duì)中國(guó)航空網(wǎng)絡(luò)進(jìn)行節(jié)點(diǎn)重要性排序；對(duì)重要節(jié)點(diǎn)分別進(jìn)行蓄意攻擊和隨機(jī)攻擊，采用脆弱性指標(biāo)驗(yàn)證排序方法的有效性，仿真結(jié)果表明介數(shù)中心性能夠更準(zhǔn)確地刻畫(huà)中國(guó)航空網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性；在航空網(wǎng)絡(luò)的背景下,將節(jié)點(diǎn)的直接影響力和節(jié)點(diǎn)鄰居之間連接的緊密程度結(jié)合起來(lái)，提出了一種基于度和聚類(lèi)系數(shù)的新指標(biāo)，經(jīng)中國(guó)航空網(wǎng)絡(luò)實(shí)例驗(yàn)證,該指標(biāo)的評(píng)價(jià)準(zhǔn)確性僅次于介數(shù)中心性，但是其時(shí)間復(fù)雜度比介數(shù)中心性低很多。

航空網(wǎng)絡(luò)；節(jié)點(diǎn)重要性；度；聚類(lèi)系數(shù)；復(fù)雜網(wǎng)絡(luò)

自20世紀(jì)初飛機(jī)問(wèn)世以來(lái)，航空運(yùn)輸系統(tǒng)飛速發(fā)展。與其他運(yùn)輸方式相比，航空運(yùn)輸具有及時(shí)、高效、靈活的優(yōu)勢(shì)，尤其是在長(zhǎng)距離運(yùn)輸和國(guó)際客運(yùn)方面的重要作用日益凸顯[1]。航空運(yùn)輸系統(tǒng)是一個(gè)易受環(huán)境影響的開(kāi)放的復(fù)雜系統(tǒng)，隨著系統(tǒng)規(guī)模的不斷擴(kuò)大，它在帶給人們便利的同時(shí)也帶來(lái)了一系列的問(wèn)題。航班延誤已經(jīng)成為人們司空見(jiàn)慣的現(xiàn)象，于是，在自然災(zāi)害或人為因素導(dǎo)致航班不能正常起降的突發(fā)情況下，航空運(yùn)輸系統(tǒng)能夠保持其魯棒性，成為人們?cè)絹?lái)越關(guān)注的問(wèn)題。

劉宏鯤等[2]研究表明，中國(guó)城市航空網(wǎng)絡(luò)具有較大的聚類(lèi)系數(shù)和較短的平均路徑長(zhǎng)度，其度分布服從雙段冪律分布，是一個(gè)具有小世界網(wǎng)絡(luò)特性的無(wú)標(biāo)度網(wǎng)絡(luò)； 姚紅光等[3]通過(guò)仿真實(shí)驗(yàn)得出，中國(guó)航空網(wǎng)絡(luò)在面對(duì)隨機(jī)干擾時(shí)魯棒性較強(qiáng)，而在蓄意攻擊下魯棒性較差；不同的城市節(jié)點(diǎn)對(duì)于網(wǎng)絡(luò)魯棒性的貢獻(xiàn)程度不同，目前有40余個(gè)核心城市在中國(guó)航空網(wǎng)絡(luò)中占有舉足輕重的地位。

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

1 理論基礎(chǔ)

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

定義1無(wú)向網(wǎng)絡(luò)中節(jié)點(diǎn)vi的度ki是指與節(jié)點(diǎn)直接相連的邊的數(shù)目。它與節(jié)點(diǎn)的重要程度有很大的關(guān)系。一般而言，ki的值越大，節(jié)點(diǎn)就越重要。其表達(dá)形式為

定義2節(jié)點(diǎn)距離定義為連接這兩個(gè)節(jié)點(diǎn)的最短路徑上的邊的數(shù)目，用dij表示。

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

定義4網(wǎng)絡(luò)中一個(gè)度為ki的節(jié)點(diǎn)vi的聚類(lèi)系數(shù)C(i)定義為

式中：Ei是節(jié)點(diǎn)vi的ki個(gè)鄰節(jié)點(diǎn)之間實(shí)際存在的邊數(shù)，即節(jié)點(diǎn)vi的ki個(gè)鄰節(jié)點(diǎn)之間實(shí)際存在的鄰居對(duì)的數(shù)目。聚類(lèi)系數(shù)表征在網(wǎng)絡(luò)中某一節(jié)點(diǎn)的兩個(gè)相鄰節(jié)點(diǎn)也相鄰的概率，反映的是網(wǎng)絡(luò)的集聚化程度。

2 無(wú)向網(wǎng)絡(luò)節(jié)點(diǎn)重要性指標(biāo)

在復(fù)雜網(wǎng)絡(luò)領(lǐng)域里評(píng)價(jià)節(jié)點(diǎn)重要性的方法有很多，本質(zhì)上都是源于圖論和基于圖的數(shù)據(jù)挖掘，主要分為以下3類(lèi)：社會(huì)網(wǎng)絡(luò)分析、系統(tǒng)科學(xué)分析、信息搜索領(lǐng)域分析[5]。其本質(zhì)上都是源于圖論以及基于圖的數(shù)據(jù)挖掘，主要從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)入手進(jìn)行分析。

社會(huì)網(wǎng)絡(luò)分析方法起始于20世紀(jì)40年代末，在評(píng)價(jià)節(jié)點(diǎn)重要性的研究領(lǐng)域中是比較常見(jiàn)的。它主要基于這樣一種假設(shè)：“重要性等價(jià)于顯著性”，即節(jié)點(diǎn)的重要性等價(jià)于該節(jié)點(diǎn)與其他節(jié)點(diǎn)的連接而使其具有的顯著性[6]。該方法主要以網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)為切入點(diǎn)，在不破壞網(wǎng)絡(luò)連通性的前提下對(duì)重要節(jié)點(diǎn)進(jìn)行研究，并且通常不考慮節(jié)點(diǎn)集的重要性[7]。通過(guò)分析網(wǎng)絡(luò)中的某種有用信息來(lái)區(qū)分不同節(jié)點(diǎn)的重要性差異，其主要的分析指標(biāo)包括節(jié)點(diǎn)的度(degree)、接近度(closeness)、介數(shù)(betweenness)、特征向量(eigenvector)等。

2.1 度中心性

度中心性(degree centrality)[8]，就是按照度值的大小對(duì)節(jié)點(diǎn)進(jìn)行排列。它是網(wǎng)絡(luò)中刻畫(huà)節(jié)點(diǎn)重要性最簡(jiǎn)單而又非常重要的指標(biāo)。具有相同度值的節(jié)點(diǎn)在不同規(guī)模的網(wǎng)絡(luò)中的重要程度是不同的，因此為了便于比較，將節(jié)點(diǎn)的度中心性進(jìn)行歸一化處理：

顯然，度中心性描述的是節(jié)點(diǎn)對(duì)于其鄰居節(jié)點(diǎn)的直接影響力，它認(rèn)為一個(gè)節(jié)點(diǎn)的度值越大，與之有直接聯(lián)系的鄰居就越多，也就越重要[9]。這種方法簡(jiǎn)單直觀，計(jì)算的復(fù)雜度低，但是它僅僅考慮了節(jié)點(diǎn)的最局部的信息，具有非常大的片面性，沒(méi)有辦法準(zhǔn)確地刻畫(huà)網(wǎng)絡(luò)中節(jié)點(diǎn)的重要程度。例如，“橋節(jié)點(diǎn)”雖然只有兩條邊相連，但是在網(wǎng)絡(luò)中處于重要的核心地位。

2.2 接近中心性

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

于是節(jié)點(diǎn)vi的接近中心性定義為di的倒數(shù)，即：

該定義只能在連通的網(wǎng)絡(luò)中使用，因此文獻(xiàn)[11]對(duì)上式進(jìn)行了改進(jìn)，使其能夠用于非連通網(wǎng)絡(luò)中，即：

如果節(jié)點(diǎn)vi和vj之間沒(méi)有路徑可達(dá)，則定義dij=，即1/dij=0。

由上式可知，節(jié)點(diǎn)的接近中心性越大，表明該節(jié)點(diǎn)越接近網(wǎng)絡(luò)的中心位置，那么它在網(wǎng)絡(luò)中就越重要。這一類(lèi)節(jié)點(diǎn)與其他節(jié)點(diǎn)的聯(lián)系并非最多，但是與網(wǎng)絡(luò)中其他節(jié)點(diǎn)的距離總和最短，也就是該節(jié)點(diǎn)在網(wǎng)絡(luò)中具有最佳視野，可以察知網(wǎng)絡(luò)中所發(fā)生的事情以及信息的流通方向。與前面的度中心性相比，接近中心性更能反映網(wǎng)絡(luò)的全局結(jié)構(gòu)，但是這種方法的計(jì)算復(fù)雜度較高，并且對(duì)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)具有依賴性，例如它可以準(zhǔn)確地發(fā)現(xiàn)星形網(wǎng)絡(luò)結(jié)構(gòu)的中心節(jié)點(diǎn)，但是并不適用于隨機(jī)網(wǎng)絡(luò)。

2.3 介數(shù)中心性

介數(shù)中心性[12](betweenness centrality)一般是指最短路徑介數(shù)中心性(shortest path BC)。簡(jiǎn)單地講，它刻畫(huà)了節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)中沿最短路徑傳輸?shù)木W(wǎng)絡(luò)流的控制力，很好地描述了網(wǎng)絡(luò)中節(jié)點(diǎn)可能需要承載的流量。

節(jié)點(diǎn)vi的介數(shù)定義為

節(jié)點(diǎn)的介數(shù)值越高，表明流經(jīng)它的網(wǎng)絡(luò)流越多，那么這個(gè)節(jié)點(diǎn)就越有影響力。與此同時(shí)，這也意味著該節(jié)點(diǎn)更容易發(fā)生擁塞，成為網(wǎng)絡(luò)的瓶頸。介數(shù)中心性能夠非常準(zhǔn)確地找到網(wǎng)絡(luò)中“流量”大的節(jié)點(diǎn)，但是它的時(shí)間復(fù)雜度為O(N3)，計(jì)算效率低，對(duì)于大型的網(wǎng)絡(luò)并不適用。

2.4 特征向量中心性

特征向量中心性(eigenvector centrality)[8]是評(píng)價(jià)網(wǎng)絡(luò)中節(jié)點(diǎn)重要性的一個(gè)重要指標(biāo)。前面介紹的幾種方法把周?chē)泥従庸?jié)點(diǎn)視為同等重要，僅僅從鄰居節(jié)點(diǎn)的數(shù)量上來(lái)考慮節(jié)點(diǎn)的重要性。而特征向量中心性同時(shí)兼顧了鄰居節(jié)點(diǎn)的數(shù)量和質(zhì)量對(duì)節(jié)點(diǎn)重要性的影響，認(rèn)為一個(gè)節(jié)點(diǎn)的重要性不僅取決于該節(jié)點(diǎn)鄰居的數(shù)量, 而且取決于每個(gè)鄰居節(jié)點(diǎn)的重要程度。特征向量中心性指標(biāo)是指網(wǎng)絡(luò)鄰接矩陣對(duì)應(yīng)其最大特征值的特征向量，即：

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

2.5 半局部中心性

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

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

式中：Γ(j)表示節(jié)點(diǎn)vj的一階鄰居節(jié)點(diǎn)的集合，N(w)指從vw出發(fā)兩步內(nèi)可以到達(dá)的鄰居的數(shù)目，稱為節(jié)點(diǎn)vw的兩層鄰居度。

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

3 中國(guó)航空網(wǎng)絡(luò)重要性節(jié)點(diǎn)分析

3.1 網(wǎng)絡(luò)構(gòu)建與結(jié)構(gòu)特性

以中國(guó)民用航空局官方網(wǎng)站公布的夏秋航季客運(yùn)航線相關(guān)數(shù)據(jù)為樣本構(gòu)建中國(guó)航空網(wǎng)絡(luò)模型，其中機(jī)場(chǎng)所在的城市為網(wǎng)絡(luò)節(jié)點(diǎn)，通航城市之間的直飛航線為網(wǎng)絡(luò)的邊。這樣形成了148個(gè)節(jié)點(diǎn)，1 153條無(wú)向邊(2 306條航線)的中國(guó)航空網(wǎng)絡(luò)(見(jiàn)圖1)。將中國(guó)航空網(wǎng)絡(luò)用一個(gè)148×148的鄰接矩陣A表示，如果節(jié)點(diǎn)vi和vj之間有可達(dá)的航班，則aij=1；反之a(chǎn)ij=0，于是得到一個(gè)對(duì)稱矩陣。

圖1 中國(guó)航空網(wǎng)絡(luò)結(jié)構(gòu)圖

在此需要說(shuō)明的是：

1)網(wǎng)絡(luò)中所選的航線均為往返航線，因此在后期運(yùn)算過(guò)程中不需要考慮航線的方向問(wèn)題；

2)對(duì)于擁有兩個(gè)及以上機(jī)場(chǎng)的城市，將其數(shù)據(jù)進(jìn)行合并，如上海的浦東機(jī)場(chǎng)和虹橋機(jī)場(chǎng)的數(shù)據(jù)可統(tǒng)一合并成到城市節(jié)點(diǎn)“上?！敝?。

節(jié)點(diǎn)的度、平均路徑長(zhǎng)度和聚類(lèi)系數(shù)是描述復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)最基本的特征參量。本文使用的中國(guó)航空網(wǎng)絡(luò)樣本，平均度為15.58，也就是說(shuō)平均每個(gè)城市機(jī)場(chǎng)約與其他16個(gè)城市有直接的航空聯(lián)系；Pearson相關(guān)系數(shù)[14]r=-0.384 3，說(shuō)明中國(guó)航空網(wǎng)絡(luò)是度—度負(fù)相關(guān)的，度值大的節(jié)點(diǎn)更傾向于和度值小的節(jié)點(diǎn)相連接。平均路徑長(zhǎng)度為2.216 5，意味著任意兩個(gè)城市機(jī)場(chǎng)通過(guò)不到2次轉(zhuǎn)機(jī)就可以相互連通；聚類(lèi)系數(shù)為0.687 7，表現(xiàn)出較強(qiáng)集聚性，說(shuō)明中國(guó)航空網(wǎng)絡(luò)各節(jié)點(diǎn)城市之間更傾向于形成短距離的聯(lián)系[15]。由此可見(jiàn)，中國(guó)航空網(wǎng)絡(luò)具有較大的聚類(lèi)系數(shù)和較小的平均路徑長(zhǎng)度，表現(xiàn)出了小世界網(wǎng)絡(luò)特性。而圖2表明，中國(guó)航空網(wǎng)絡(luò)服從雙冪律分布，具有無(wú)標(biāo)度特性。

中國(guó)航空網(wǎng)絡(luò)城市節(jié)點(diǎn)度與聚類(lèi)系數(shù)相關(guān)性如圖3所示?？梢钥闯?，隨著節(jié)點(diǎn)度值k的不斷增加，聚類(lèi)系數(shù)C(k)的數(shù)值是不斷下降的，也就是說(shuō)節(jié)點(diǎn)的度和聚類(lèi)系數(shù)呈負(fù)相關(guān)。這說(shuō)明在中國(guó)航空網(wǎng)絡(luò)中，度值小的城市節(jié)點(diǎn)比度值大的城市節(jié)點(diǎn)更趨向于聚集成團(tuán)。

圖2 中國(guó)航空網(wǎng)絡(luò)城市節(jié)點(diǎn)度分布

圖3 中國(guó)航空網(wǎng)絡(luò)城市節(jié)點(diǎn)度與聚類(lèi)系數(shù)相關(guān)性

3.2 中國(guó)航空網(wǎng)絡(luò)重要性節(jié)點(diǎn)排序

下面用本文中提到的幾種無(wú)向網(wǎng)絡(luò)節(jié)點(diǎn)重要性評(píng)價(jià)指標(biāo)中國(guó)航空網(wǎng)絡(luò)模型的節(jié)點(diǎn)重要程度進(jìn)行排序，排序結(jié)果見(jiàn)表1。

節(jié)點(diǎn)的度反映了該機(jī)場(chǎng)與其他機(jī)場(chǎng)通航能力的大小。中國(guó)航空網(wǎng)絡(luò)的度分布呈現(xiàn)出明顯的東西差異，結(jié)合中國(guó)航空網(wǎng)網(wǎng)絡(luò)的空間結(jié)構(gòu)，從表1中可以看出，度值較大的節(jié)點(diǎn)主要集中東部較發(fā)達(dá)地區(qū)，如北京 (102)、上海(83)、廣州(83)、深圳(69)、杭州(52)、南京(51)以及各個(gè)省會(huì)城市，如成都(61)、西安(56)、昆明(56)、重慶(56)。

接近中心性是用網(wǎng)絡(luò)中的節(jié)點(diǎn)到其他節(jié)點(diǎn)的平均最短距離來(lái)衡量的，因此接近中心性越小，意味著該節(jié)點(diǎn)在網(wǎng)絡(luò)中越處于中心地位，從而也就越不容易受到其他結(jié)點(diǎn)連通情況的控制。也就是說(shuō)，接近中心性數(shù)值較大的機(jī)場(chǎng)相對(duì)于數(shù)值較小的機(jī)場(chǎng)獨(dú)立性更強(qiáng)，不太容易受到其他機(jī)場(chǎng)通航狀況的影響。而接近中心性Top10的節(jié)點(diǎn)排序結(jié)果基本上跟度中心性保持一致，都表現(xiàn)出明顯的東西差異，這一點(diǎn)在特征向量中心性和半局部中心性中都有所體現(xiàn)。

節(jié)點(diǎn)的介數(shù)中心性反映了該機(jī)場(chǎng)在網(wǎng)絡(luò)運(yùn)輸中的中轉(zhuǎn)和銜接能力。介數(shù)中心性高的節(jié)點(diǎn)在地區(qū)網(wǎng)絡(luò)間的連接中起到了橋梁的作用。中國(guó)航空網(wǎng)絡(luò)節(jié)點(diǎn)的介數(shù)中心性排序中，北京依然排在第1位，但是排在第2位的烏魯木齊在其他排序結(jié)果的前十中從未出現(xiàn)過(guò)，排在第3位的昆明只在度中心性排序中排在第七位。從空間結(jié)構(gòu)上可以看出新疆地區(qū)的城市節(jié)點(diǎn)大多數(shù)通過(guò)烏魯木齊與整個(gè)航空網(wǎng)絡(luò)連接，若移除烏魯木齊，則新疆地區(qū)的大部分城市節(jié)點(diǎn)將變?yōu)楣铝⒐?jié)點(diǎn)，而昆明也同樣起到非常重要的橋梁作用。

表1 排名前10中國(guó)航空網(wǎng)絡(luò)各中心性指標(biāo)

3.3 用網(wǎng)絡(luò)的魯棒性和脆弱性評(píng)價(jià)排序算法

利用之前的節(jié)點(diǎn)重要性評(píng)價(jià)方法對(duì)中國(guó)航空網(wǎng)絡(luò)的重要節(jié)點(diǎn)進(jìn)行排序之后，分別按照節(jié)點(diǎn)的重要性從大到小的順序，依次刪除網(wǎng)絡(luò)中的節(jié)點(diǎn)。則節(jié)點(diǎn)移除后網(wǎng)絡(luò)的破壞程度可以用最大連通子圖的相對(duì)大小，全局效率以及脆弱性指標(biāo)來(lái)進(jìn)行評(píng)價(jià)。

最大連通子圖概念的提出，是為了描述網(wǎng)絡(luò)中的節(jié)點(diǎn)或連邊由于一些內(nèi)部或外部的原因所發(fā)生的變化。簡(jiǎn)單來(lái)說(shuō)，最大連通子圖就是一個(gè)網(wǎng)絡(luò)的眾多連通子圖中包含節(jié)點(diǎn)最多的那個(gè)子圖。

網(wǎng)絡(luò)中，節(jié)點(diǎn)vi和vj之間的效率為兩點(diǎn)之間最短距離的倒數(shù)，即1/dij。于是網(wǎng)絡(luò)的全局效率[16]就定義為所有節(jié)點(diǎn)對(duì)效率的平均值，即

如果用i/n表示移除的節(jié)點(diǎn)比例，用σ(i/n)表示移除i/n比例的節(jié)點(diǎn)后最大連通子圖的相對(duì)大小，則該節(jié)點(diǎn)移除方式下網(wǎng)絡(luò)的魯棒性(robustness)可以用R-指標(biāo)[17]來(lái)評(píng)價(jià)。具體定義為

顯然，無(wú)論針對(duì)哪種算法都能得到如下結(jié)果

所以在任何網(wǎng)絡(luò)中，無(wú)論用何種算法移除節(jié)點(diǎn)，R∈(0，1/2)。因此，文獻(xiàn)[18]定義V-指標(biāo)來(lái)衡量網(wǎng)絡(luò)對(duì)所實(shí)施的節(jié)點(diǎn)移除方法的脆弱性(vulnerability)。

V=1/2-R

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

圖4為對(duì)中國(guó)航空網(wǎng)絡(luò)模型分別進(jìn)行隨機(jī)攻擊和蓄意攻擊后，網(wǎng)絡(luò)中移除節(jié)點(diǎn)的比例和最大連通集的規(guī)模之間的關(guān)系。在此需要說(shuō)明的是，采用的攻擊方式是同時(shí)移除i/n比例的節(jié)點(diǎn)，計(jì)算剩余網(wǎng)絡(luò)中最大連通集所占的比例。

圖4 移除節(jié)點(diǎn)比例和最大連通集規(guī)模的關(guān)系(傳統(tǒng)方法的攻擊效果)

從圖4可以看出，相比于蓄意攻擊，隨機(jī)攻擊呈現(xiàn)的攻擊效果較差，這表明中國(guó)航空網(wǎng)絡(luò)對(duì)于隨機(jī)攻擊具有較好的魯棒性。在蓄意攻擊的仿真實(shí)驗(yàn)中，基于介數(shù)攻擊下的指標(biāo)下降率遠(yuǎn)遠(yuǎn)高于基于其他4種方法攻擊下的指標(biāo)下降率，而且下降速度很快，呈陡峭直線下降趨勢(shì)。這表明針對(duì)中國(guó)航空網(wǎng)絡(luò)，基于介數(shù)中心性的節(jié)點(diǎn)重要性排序方法效果是最好的，介數(shù)中心性能夠更準(zhǔn)確地刻畫(huà)網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性。

基于各種攻擊方法的中國(guó)航空網(wǎng)絡(luò)脆弱性指標(biāo)排序在表2中給出，對(duì)比發(fā)現(xiàn)，蓄意攻擊下的脆弱性指標(biāo)遠(yuǎn)遠(yuǎn)高于隨機(jī)攻擊。在蓄意攻擊中，介數(shù)中心性的指標(biāo)Vb明顯高于其他4種，排名第4的半局部中心性和排名第5的特征向量中心性在數(shù)值上比較接近。此外，從最大連通集的曲線圖中也不難發(fā)現(xiàn)，半局部中心性和特征向量中心性的曲線是非常相近的。這就證明對(duì)于中國(guó)航空網(wǎng)絡(luò)，半局部中心性和特征向量中心性的評(píng)價(jià)方法效果類(lèi)似。

表2 中國(guó)航空網(wǎng)絡(luò)脆弱性指標(biāo)排序

Table 2 The ranking of vulnerability index of Chinese aviation network

次序攻擊方法脆弱性指標(biāo)1介數(shù)中心性0.4792度中心性0.3603接近中心性0.3414半局部中心性0.3145特征向量中心性0.3126隨機(jī)攻擊0.024

另外，值得注意的是，當(dāng)采用介數(shù)中心性對(duì)網(wǎng)絡(luò)進(jìn)行攻擊的時(shí)候，曲線一開(kāi)始就陡然下降，這一現(xiàn)象在其他攻擊方法下并沒(méi)有出現(xiàn)。單獨(dú)觀察介數(shù)攻擊下網(wǎng)絡(luò)的變化，發(fā)現(xiàn)在對(duì)北京進(jìn)行攻擊之后，網(wǎng)絡(luò)的最大連通子圖相對(duì)大小為0.993，而當(dāng)對(duì)烏魯木齊進(jìn)行攻擊之后，網(wǎng)絡(luò)的最大連通子圖相對(duì)大小驟然下降至0.047，網(wǎng)絡(luò)幾乎陷入癱瘓狀態(tài)，這表明類(lèi)似于烏魯木齊這樣的“橋”節(jié)點(diǎn)對(duì)于網(wǎng)絡(luò)魯棒性的影響舉足輕重。

根據(jù)脆弱性指標(biāo)判斷，介數(shù)中心性能夠更準(zhǔn)確地描述節(jié)點(diǎn)的重要性，因此取基于介數(shù)中心性方法排列出的前20名節(jié)點(diǎn)城市，分別單獨(dú)移除這些節(jié)點(diǎn)，用分析對(duì)網(wǎng)絡(luò)造成的影響，具體數(shù)據(jù)見(jiàn)表3。

表3 機(jī)場(chǎng)失效后網(wǎng)絡(luò)的全局傳輸效率

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長(zhǎng)沙0.9800.4820.04011呼和浩特0.9930.4930.01712貴陽(yáng)0.9870.4880.02613沈陽(yáng)0.9930.4930.01814哈爾濱0.9870.4890.02615大連0.9930.4930.01816杭州0.9930.4920.01917合肥0.9870.4880.02618長(zhǎng)春0.9870.4890.02519廈門(mén)0.9930.4920.01820桂林0.9930.4930.018

用σ(i/n)表示移除i/n比例的節(jié)點(diǎn)后最大連通子圖的相對(duì)大小，E為網(wǎng)絡(luò)的全局效率，E0為原始網(wǎng)絡(luò)的全局效率，ΔE為網(wǎng)絡(luò)減少的效率。結(jié)果表明，昆明機(jī)場(chǎng)的移除對(duì)網(wǎng)絡(luò)的全局效率影響最大，其次是烏魯木齊和北京。這也就進(jìn)一步說(shuō)明，昆明和烏魯木齊在中國(guó)航空網(wǎng)絡(luò)中的影響力不容小覷，從而驗(yàn)證了介數(shù)中心性指標(biāo)的準(zhǔn)確性。

這些城市在空間結(jié)構(gòu)上基本上覆蓋了中東部各地區(qū)，進(jìn)一步觀察局部地區(qū)的機(jī)場(chǎng)影響力情況，得到各個(gè)地區(qū)影響力最強(qiáng)的機(jī)場(chǎng)城市：華北地區(qū)——北京、華東地區(qū)——上海、華中地區(qū)——長(zhǎng)沙、華南地區(qū)——廣州、西北地區(qū)——烏魯木齊、西南地區(qū)——昆明以及東北地區(qū)——哈爾濱。

4 簇度指標(biāo)的提出

在航空網(wǎng)絡(luò)的背景下，介數(shù)中心性能夠準(zhǔn)確評(píng)價(jià)網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性，但其算法的時(shí)間復(fù)雜度較高，使其在實(shí)際應(yīng)用中受到限制。

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

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

圖5 示例網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

可見(jiàn)，節(jié)點(diǎn)的度和聚類(lèi)系數(shù)對(duì)刻畫(huà)其重要性都具有非常重要的意義。將節(jié)點(diǎn)的直接影響力和節(jié)點(diǎn)鄰居之間連接的緊密程度結(jié)合起來(lái)，提出一種新的指標(biāo)即簇度指標(biāo)為：

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

式中：ki為節(jié)點(diǎn)vi的度，α為可調(diào)參數(shù)，C(i)為節(jié)點(diǎn)i的聚類(lèi)系數(shù)。

在此需要說(shuō)明的是：

1)Chen和任卓明等在構(gòu)造節(jié)點(diǎn)重要性指標(biāo)中用到了二階鄰居度，但是由于航空網(wǎng)絡(luò)的特殊性，即中轉(zhuǎn)成本造成的平均路徑長(zhǎng)度較小，節(jié)點(diǎn)的直接影響力在評(píng)價(jià)節(jié)點(diǎn)重要性的過(guò)程中占主導(dǎo)地位。

2)由于節(jié)點(diǎn)的聚類(lèi)系數(shù)C(i)可能為0，故構(gòu)造減函數(shù)α-C(i)(α>1)，并通過(guò)仿真實(shí)驗(yàn)得到α的最優(yōu)值，在后面的分析中我們將以中國(guó)航空網(wǎng)絡(luò)為樣本作出詳細(xì)的描述。

5 實(shí)驗(yàn)分析

為了驗(yàn)證簇度指標(biāo)對(duì)節(jié)點(diǎn)重要性的度量效果，分別采用簇度指標(biāo)以及上文提到的6種方法對(duì)中國(guó)航空網(wǎng)絡(luò)進(jìn)行蓄意攻擊仿真實(shí)驗(yàn)，并用脆弱性指標(biāo)來(lái)評(píng)價(jià)攻擊效果。

經(jīng)過(guò)調(diào)試得出，對(duì)于函數(shù)μDCL(i)，當(dāng)α的取值范圍為[4 724,4 952]時(shí)，脆弱性指標(biāo)取最大值0.436，即得到的攻擊效果最好。

網(wǎng)絡(luò)中移除節(jié)點(diǎn)的比例和最大連通集的規(guī)模之間的關(guān)系由圖6給出。從圖6中可以看出，按照簇度指標(biāo)排列出的節(jié)點(diǎn)重要性順序?qū)χ袊?guó)航空網(wǎng)絡(luò)進(jìn)行蓄意攻擊，得到的脆弱性指標(biāo)數(shù)值為0.405,攻擊效果僅次于介數(shù)中心性。但是介數(shù)的時(shí)間復(fù)雜度為O(N3)；而該指標(biāo)的時(shí)間復(fù)雜度為O(N)，比介數(shù)中心性要快很多。例如在中國(guó)航空網(wǎng)絡(luò)中，用介數(shù)排序需要0.03 s，而用簇度指標(biāo)排序只需要0.01 s。

圖6 移除節(jié)點(diǎn)比例和最大連通集規(guī)模的關(guān)系(簇度指標(biāo)與傳統(tǒng)方法的攻擊效果對(duì)比)

6 結(jié)束語(yǔ)

本文分別用度中心性、接近中心性、介數(shù)中心性、特征向量中心性和半局部中心性5種方法對(duì)中國(guó)航空網(wǎng)絡(luò)模型進(jìn)行了分析，將網(wǎng)絡(luò)中的節(jié)點(diǎn)按照重要性從大到小進(jìn)行排序，并列出了重要性排名前10的節(jié)點(diǎn)城市；然后按排列出的節(jié)點(diǎn)次序?qū)χ袊?guó)航空網(wǎng)絡(luò)進(jìn)行蓄意攻擊，用脆弱性指標(biāo)考察這5種方法的攻擊效果。仿真結(jié)果表明，相比于其他4種方法，基于介數(shù)中心性的節(jié)點(diǎn)重要性排序方法能夠更準(zhǔn)確地刻畫(huà)網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性。進(jìn)而根據(jù)介數(shù)中心性得到的排序結(jié)果分別單獨(dú)攻擊各個(gè)城市節(jié)點(diǎn)，觀察機(jī)場(chǎng)失效后網(wǎng)絡(luò)的全局效率，分析得出各個(gè)局部地區(qū)的重要性節(jié)點(diǎn)。

此外，在航空網(wǎng)絡(luò)的背景下,將節(jié)點(diǎn)的直接影響力和節(jié)點(diǎn)鄰居之間連接的緊密程度結(jié)合起來(lái)，提出了一種基于度和聚類(lèi)系數(shù)的新指標(biāo)。對(duì)中國(guó)航空網(wǎng)絡(luò)的仿真研究結(jié)果表明，該指標(biāo)的評(píng)價(jià)準(zhǔn)確性僅次于介數(shù)中心性，但是其時(shí)間復(fù)雜度比介數(shù)中心性低很多，具有很好的實(shí)用價(jià)值。

[1]劉宏鯤, 周濤. 中國(guó)城市航空網(wǎng)絡(luò)的實(shí)證研究與分析[J]. 物理學(xué)報(bào), 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]劉宏鯤. 中國(guó)航空網(wǎng)絡(luò)的結(jié)構(gòu)及其影響因素分析[D]. 成都: 西南交通大學(xué), 2007. LIU Hongkun. Analyzing the structure of Chinese aviation network and impact factors[D]. Chengdu: Southwest Jiaotong University, 2007.

[3]姚紅光, 朱麗萍. 基于仿真分析的中國(guó)航空網(wǎng)絡(luò)魯棒性研究[J]. 武漢理工大學(xué)學(xué)報(bào): 交通科學(xué)與工程版, 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]任卓明, 邵鳳, 劉建國(guó), 等. 基于度與集聚系數(shù)的網(wǎng)絡(luò)節(jié)點(diǎn)重要性度量方法研究[J]. 物理學(xué)報(bào), 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]張珍, 張振宇, 宋蔓蔓. 一種基于最短路徑介數(shù)的重要節(jié)點(diǎn)發(fā)現(xiàn)算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 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]赫南, 李德毅, 淦文燕, 等. 復(fù)雜網(wǎng)絡(luò)中重要性節(jié)點(diǎn)發(fā)掘綜述[J]. 計(jì)算機(jī)科學(xué), 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]汪小帆, 李翔, 陳關(guān)榮. 網(wǎng)絡(luò)科學(xué)導(dǎo)論[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]王姣娥, 莫輝輝, 金鳳君. 中國(guó)航空網(wǎng)絡(luò)空間結(jié)構(gòu)的復(fù)雜性[J]. 地理學(xué)報(bào), 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年生，碩士研究生，主要研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)。

陳增強(qiáng)，男，1964年生，教授， 博士生導(dǎo)師，主要研究方向?yàn)橹悄芸刂啤?智能信息處理，曾獲天津市自然科學(xué)二等獎(jiǎng)，發(fā)表學(xué)術(shù)論文100余篇。

張青，女，1965年生，教授，主要研究方向?yàn)閺?fù)雜系統(tǒng)建模與控制、多智能體系統(tǒng)，發(fā)表學(xué)術(shù)論文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.

國(guó)家自然科學(xué)基金項(xiàng)目(61573199)；天津自然科學(xué)基金項(xiàng)目(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

閆玲玲，陳增強(qiáng)，張青.基于度和聚類(lèi)系數(shù)的中國(guó)航空網(wǎng)絡(luò)重要性節(jié)點(diǎn)分析[J]. 智能系統(tǒng)學(xué)報(bào)， 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.