沈安慰，郭基聯(lián)，王卓健

（空軍工程大學(xué)航空航天工程學(xué)院，西安 710038）

基于自然連通度的復(fù)雜網(wǎng)絡(luò)節(jié)點重要性度量方法*

沈安慰，郭基聯(lián)，王卓健

（空軍工程大學(xué)航空航天工程學(xué)院，西安 710038）

節(jié)點重要性度量是復(fù)雜網(wǎng)絡(luò)研究中的熱點問題。從復(fù)雜網(wǎng)絡(luò)的抗毀性指標(biāo)入手，給出了自然連通度的定義，并且以此為基礎(chǔ)設(shè)計了基于自然連通度的復(fù)雜網(wǎng)絡(luò)節(jié)點重要性度量方法。最后以著名的風(fēng)箏網(wǎng)絡(luò)為例，分析了該方法的適用性，并與其他經(jīng)典的節(jié)點重要性度量方法進(jìn)行對比，證明了該方法的合理性。

復(fù)雜網(wǎng)絡(luò)，自然連通度，風(fēng)箏網(wǎng)絡(luò)，節(jié)點重要性

0 引言

現(xiàn)實世界中的很多復(fù)雜系統(tǒng)都可以用網(wǎng)絡(luò)來刻畫。隨著基礎(chǔ)研究的不斷深入，各國的研究工作者和工程技術(shù)人員逐漸認(rèn)識到計算機(jī)通信網(wǎng)絡(luò)系統(tǒng)、國家交通網(wǎng)絡(luò)、社會關(guān)系網(wǎng)絡(luò)、武器裝備體系等復(fù)雜系統(tǒng)的研究都可以歸結(jié)于復(fù)雜網(wǎng)絡(luò)。如何判斷復(fù)雜網(wǎng)絡(luò)中節(jié)點的重要性是復(fù)雜網(wǎng)絡(luò)研究中急需解決的關(guān)鍵問題之一［1］。

大量實際復(fù)雜網(wǎng)絡(luò)的研究結(jié)果表明，分析節(jié)點的度（網(wǎng)絡(luò)中與該節(jié)點相連的邊的數(shù)量）是衡量節(jié)點重要性的一個簡單有效方法。度指標(biāo)描述了一個節(jié)點的鄰居節(jié)點的個數(shù)，體現(xiàn)了該節(jié)點與周圍節(jié)點之間建立直接聯(lián)系的影響力。顯然，網(wǎng)絡(luò)節(jié)點的度越大，該節(jié)點越重要。但度指標(biāo)只利用了自身的信息，沒有考慮到該節(jié)點在網(wǎng)絡(luò)中的位置。王建偉［2］等在度指標(biāo)的基礎(chǔ)上提出了節(jié)點及鄰居節(jié)點度的概念，認(rèn)為網(wǎng)絡(luò)中節(jié)點的重要性不僅與自身的度有一定的聯(lián)系，并且與該節(jié)點鄰居節(jié)點的度也存在一定的關(guān)聯(lián)。在此基礎(chǔ)上，任卓明［1］等綜合權(quán)衡考慮了節(jié)點的鄰居個數(shù)以及其鄰居之間的連接緊密程度，提出了一種基于鄰居信息與集聚系數(shù)的節(jié)點重要性評價方法。

上述方法都是基于局部信息進(jìn)行節(jié)點重要性度量的。此類方法算法復(fù)雜度較低，能夠適應(yīng)大規(guī)模復(fù)雜網(wǎng)絡(luò)，但計算精度往往不高，難以體現(xiàn)網(wǎng)絡(luò)的全局特征?；诰W(wǎng)絡(luò)全局屬性的節(jié)點重要性指標(biāo)研究也得到了大量的研究。例如，考慮網(wǎng)絡(luò)鄰接矩陣的特征值和特征向量的節(jié)點重要度評價方法。Sabidussi提出了描述網(wǎng)絡(luò)節(jié)點重要性的緊密度指標(biāo)，之后人們在此基礎(chǔ)上定義了Kernel函數(shù)法。Comin考慮度與介數(shù)的關(guān)系，定義了一個新的節(jié)點重要性評價指標(biāo)。此類方法較為經(jīng)典，但面對大規(guī)模復(fù)雜網(wǎng)絡(luò)時則表現(xiàn)出了算法復(fù)雜度較高的缺點。

另一種評價復(fù)雜網(wǎng)絡(luò)節(jié)點重要性的思路是將該節(jié)點刪除，在對刪除指定節(jié)點后復(fù)雜網(wǎng)絡(luò)特性研究的基礎(chǔ)上進(jìn)行評估。例如，李鵬翔［3］認(rèn)為刪除節(jié)點的重要性可以用該節(jié)點被刪除后形成的所有節(jié)點之間的最短距離的倒數(shù)之和來度量。譚躍進(jìn)［4］在此基礎(chǔ)上提出了一種評估復(fù)雜網(wǎng)絡(luò)節(jié)點重要度的節(jié)點收縮方法。饒育萍［5］認(rèn)為網(wǎng)絡(luò)平均等效距離越多，網(wǎng)絡(luò)的抗毀能力越強(qiáng)，并提出了一種基于平均等效最短路徑數(shù)的抗毀評價模型，認(rèn)為如果節(jié)點失效后網(wǎng)絡(luò)抗毀度下降得越多，則該節(jié)點在網(wǎng)絡(luò)中的重要性越大。此類方法在指定網(wǎng)絡(luò)中表現(xiàn)較好。

針對上述復(fù)雜網(wǎng)絡(luò)節(jié)點重要性度量方法的不足和優(yōu)點，本文從復(fù)雜網(wǎng)絡(luò)抗毀性指標(biāo)入手，提出了基于復(fù)雜網(wǎng)絡(luò)自然連通度的節(jié)點重要性度量方法。并將其與常見的度量方法進(jìn)行對比分析，證明了本文所提方法的合理性。

1 節(jié)點重要性度量的常用方法

定義1：簡單無權(quán)圖G中，若vi與vj之間存在邊則aij=1，否則aij=0，且aii=0。則稱為網(wǎng)絡(luò)的鄰接矩陣。

1.1 節(jié)點度

節(jié)點的度為與該節(jié)點相連接的鄰居節(jié)點數(shù)目。具體可表示為

節(jié)點度指標(biāo)能夠直觀地反映一個節(jié)點在網(wǎng)絡(luò)中的重要程度。例如，在朋友關(guān)系網(wǎng)絡(luò)中，一個人擁有的朋友越多，在網(wǎng)絡(luò)中就越重要。

1.2 節(jié)點及其鄰居節(jié)點度

在節(jié)點度的基礎(chǔ)上，研究者［2］又提出了節(jié)點及其鄰居節(jié)點度方法來判斷一個節(jié)點的重要程度。即節(jié)點的度以及節(jié)點的鄰居節(jié)點的度越大，節(jié)點就越重要。該方法認(rèn)為連接節(jié)點的邊越重要，節(jié)點就越重要。具體可表示為：

其中，wi表示節(jié)點i所連邊的權(quán)值之和，wij表示邊ij的權(quán)重，且。。A為鄰接矩陣，e為單位向量。

1.3 度與集聚系數(shù)

任卓明［1］等人綜合考慮節(jié)點的鄰居個數(shù)，以及其鄰居之間的連接緊密程度，又提出了度與集聚系數(shù)的節(jié)點重要度評估方法。該方法利用節(jié)點的鄰居信息，并考慮節(jié)點鄰居之間的緊密程度，節(jié)點重要性評價指標(biāo)pi表示為

1.4 緊密度

度量網(wǎng)絡(luò)中節(jié)點重要程度的另一種方法是度量該節(jié)點通過網(wǎng)絡(luò)對其他節(jié)點施加影響的能力，可用緊密度來表示，具體如下：

其中，dij表示節(jié)點i到節(jié)點j的最短距離。

1.5 Kernel函數(shù)法

考慮節(jié)點的影響范圍，一些學(xué)者又定義了Kernel函數(shù)法，具體如下：

其中，dij表示節(jié)點i到節(jié)點j的最短距離，h表示Kernel函數(shù)的寬度。h越大表示此函數(shù)越平滑，因此，節(jié)點的影響范圍也越大。

2 基于自然連通度的復(fù)雜網(wǎng)絡(luò)節(jié)點重要性度量

2.1 理論基礎(chǔ)

復(fù)雜網(wǎng)絡(luò)節(jié)點重要性度量可借助網(wǎng)絡(luò)的抗毀性指標(biāo)來表征。并且認(rèn)為如果節(jié)點失效后網(wǎng)絡(luò)抗毀度下降得越多，則該節(jié)點在網(wǎng)絡(luò)中的重要性越大。本文在饒育萍［5］的基礎(chǔ)上，考慮抗毀性指標(biāo)新的測度方法——自然連通度，以此來評價網(wǎng)絡(luò)中節(jié)點的重要性。

現(xiàn)實網(wǎng)絡(luò)可能節(jié)點眾多、連接復(fù)雜，傳統(tǒng)基于圖論的抗毀性測度已不適用于復(fù)雜網(wǎng)絡(luò)的抗毀性度量。本文關(guān)注到吳?。?-7］等人提到以自然連通度為測度衡量復(fù)雜網(wǎng)絡(luò)抗毀性。分析發(fā)現(xiàn)，自然連通度在描述網(wǎng)絡(luò)抗毀性時其計算復(fù)雜度很低而精確性很高。

圖1 簡單網(wǎng)絡(luò)示意圖

自然連通度從網(wǎng)絡(luò)的冗余替代路徑出發(fā)描述一個網(wǎng)絡(luò)的抗毀能力。我們知道，網(wǎng)絡(luò)的抗毀能力與節(jié)點之間的冗余替代路徑密切相關(guān)。例如，圖1是由4個節(jié)點構(gòu)成的簡單網(wǎng)絡(luò)示意圖。圖1（a）和圖1（b）中節(jié)點v1到節(jié)點v4的路徑數(shù)如表1所示。顯然，圖1（b）的網(wǎng)絡(luò)抗毀性能強(qiáng)于圖1（a）所示的網(wǎng)絡(luò)。通過這樣一個簡單案例，可以看出，網(wǎng)絡(luò)抗毀性源于網(wǎng)絡(luò)中節(jié)點冗余替代路徑的數(shù)目。

表1 圖1（a）、圖1（b）節(jié)點到節(jié)點的路徑數(shù)

由于復(fù)雜網(wǎng)絡(luò)一般冗余替代路徑計算和完全統(tǒng)計非常困難，那么可以換種思路，統(tǒng)計網(wǎng)絡(luò)中所有封閉路徑冗余數(shù)（網(wǎng)絡(luò)中從一個節(jié)點出發(fā)經(jīng)過若干其他節(jié)點最后仍能夠回到出發(fā)節(jié)點的所有路徑統(tǒng)稱為封閉路徑），這樣同樣能夠表示網(wǎng)絡(luò)的抗毀性能。設(shè)nk表示一個網(wǎng)絡(luò)所有路徑長度為k的封閉路徑數(shù)，S表示所有封閉路徑數(shù)，那么有

S的值越大，表明網(wǎng)絡(luò)中冗余替代路徑數(shù)目越多，其抗毀性越好?？紤]到統(tǒng)計網(wǎng)絡(luò)中長度為k的路徑數(shù)時存在大量重復(fù)統(tǒng)計。如長度為2的路徑共統(tǒng)計了2次，長度為3的路徑共統(tǒng)計6次。因此，S可按式（7）計算

由于當(dāng)N較大時S值也很大，所以考慮簡化

S*表示網(wǎng)絡(luò)特征譜密度平均值的自然對數(shù)，由此可定義S*為網(wǎng)絡(luò)的自然連通度，i是網(wǎng)絡(luò)鄰接矩陣的特征值，N是網(wǎng)絡(luò)節(jié)點數(shù)。

若G為無向圖，則A（G）為對稱矩陣，即aij=aji。令為A（G）的特征根，則集合｛｝i為圖G的鄰接矩陣特征譜。

自然連通度從網(wǎng)絡(luò)中的內(nèi)部結(jié)構(gòu)屬性出發(fā)，通過計算網(wǎng)絡(luò)中不同長度閉環(huán)數(shù)目的加權(quán)和，刻畫了網(wǎng)絡(luò)中替代途徑的冗余性，具有明確的物理意義和簡潔的數(shù)學(xué)形式。文獻(xiàn)［6-7］在詳細(xì)闡述自然連通度提出的背景意義基礎(chǔ)上，推導(dǎo)了自然連通度和鄰接矩陣特征值的關(guān)系，并證明了其關(guān)于添加節(jié)點或邊是嚴(yán)格單調(diào)的，獲得了國際學(xué)術(shù)界的高度認(rèn)可。因為自然連通度能精確地刻畫出復(fù)雜網(wǎng)絡(luò)的抗毀性細(xì)微區(qū)別，準(zhǔn)確表征出抗毀性的演化過程，并且相對來講具有便于計算的特點，所以本文以自然連通度為基礎(chǔ)，探索復(fù)雜網(wǎng)絡(luò)節(jié)點重要性度量的新方法。

2.2 方法步驟

本文以復(fù)雜網(wǎng)絡(luò)的自然連通度為基礎(chǔ)，設(shè)計了基于自然連通度參數(shù)的節(jié)點重要性度量方法，具體步驟如下：

步驟3：按照節(jié)點的順序依次刪除網(wǎng)絡(luò)中的每一個節(jié)點與其對應(yīng)的連邊。每刪除一個節(jié)點，其鄰接矩陣為，計算該狀態(tài)下網(wǎng)絡(luò)的自然連通度，共可得到N個自然連通度。

從上述步驟可以看出，節(jié)點的重要度pi表征的物理意義在于節(jié)點刪除之后，網(wǎng)絡(luò)抗毀性改變的快慢的趨勢。

3 案例分析

以Krackhardt設(shè)計的“風(fēng)箏網(wǎng)絡(luò)”為例［8］，分析本文提出的基于自然連通度的復(fù)雜網(wǎng)絡(luò)節(jié)點重要性度量方法。風(fēng)箏網(wǎng)絡(luò)的結(jié)構(gòu)如圖2所示。

首先將該網(wǎng)絡(luò)表示為鄰接矩陣的形式，如表2所示。

表2 風(fēng)箏網(wǎng)絡(luò)的鄰接矩陣

表3 風(fēng)箏網(wǎng)絡(luò)節(jié)點重要性度量結(jié)果

從表3中可以看出，風(fēng)箏網(wǎng)絡(luò)中基于自然連通度的復(fù)雜網(wǎng)絡(luò)節(jié)點重要性排序為，表明節(jié)點7在風(fēng)箏網(wǎng)絡(luò)中最為重要，節(jié)點1最為不重要。該計算結(jié)果與節(jié)點度、節(jié)點及其鄰居節(jié)點度、Kernel函數(shù)法的計算結(jié)果一致。但節(jié)點度、節(jié)點及其鄰居節(jié)點度在某些情況下不能區(qū)分部分節(jié)點的重要性排序，這兩種方法度量結(jié)果較為粗糙。

圖2 風(fēng)箏網(wǎng)絡(luò)

基于度與集聚系數(shù)的方法在節(jié)點3的重要性認(rèn)定上與本文的方法出現(xiàn)了不一致的現(xiàn)象，主要是由于該方法考慮了聚類系數(shù)。在高聚集性網(wǎng)絡(luò)中，其節(jié)點重要性評估的效果會有所降低。

基于緊密度的方法也在節(jié)點3的認(rèn)定上與本文方法出現(xiàn)了不一致的現(xiàn)象，主要是該方法認(rèn)為節(jié)點3被破壞了之后整個網(wǎng)絡(luò)就出現(xiàn)了不連通現(xiàn)象。

從上述各種方法的對比可以看出，基于不同的度量標(biāo)準(zhǔn)，網(wǎng)絡(luò)節(jié)點重要性的度量結(jié)果就會不一樣。本文從復(fù)雜網(wǎng)絡(luò)的抗毀性入手，提出的基于自然連通度的節(jié)點重要性度量方法具有一定的現(xiàn)實意義。

4 結(jié)論

節(jié)點重要性度量的側(cè)重點不同，其結(jié)果自然不一樣。本文以復(fù)雜網(wǎng)絡(luò)抗毀性為重要性度量標(biāo)準(zhǔn)，提出了基于自然連通度的復(fù)雜網(wǎng)絡(luò)節(jié)點重要性度量方法，并且給出了該方法的計算步驟。最后，本文以風(fēng)箏網(wǎng)絡(luò)為例，分析了本文方法的節(jié)點重要性度量結(jié)果，并與經(jīng)典方法進(jìn)行對比分析，證明了本文所提方法的合理性。

［1］任卓明，邵鳳，劉建國，等.基于度與集聚系數(shù)的網(wǎng)絡(luò)節(jié)點重要性度量方法研究［J］.物理學(xué)報，2013，62（12）：128901.

［2］王建偉，榮莉莉，郭天柱.一種基于局部特征的網(wǎng)絡(luò)節(jié)點重要性度量方法［J］.大連理工大學(xué)學(xué)報，2010，50（5）：822-826.

［3］李鵬翔，任玉晴，席酉民.網(wǎng)絡(luò)節(jié)點（集）重要性的一種度量指標(biāo)［J］.系統(tǒng)工程，2014，22（4）：13-20.

［4］譚躍進(jìn)，吳俊，鄧宏鐘.復(fù)雜網(wǎng)絡(luò)中節(jié)點重要度評估的節(jié)點收縮方法［J］.系統(tǒng)工程理論與實踐，2006，26（4）：79-83.

［5］饒育萍，林競焉，月東方.網(wǎng)絡(luò)抗毀度和節(jié)點重要性評價方法［J］.計算機(jī)工程，2009，35（6）：14-16.

［6］WU J，BARAHONA M，TAN Y J，et al.Spectral measure of structural robustness in compex network ［J］，IEEE Transactions on Systems Man and Cybernetics Part A ，2011，41（6）：1244-1252.

［7］WU J，BARAHONA M，TAN Y J，et al.Natural connectivity of complex network［J］.Chin Phys Lett，2010，7（7）：078902.

［8］汪小帆，李翔，陳關(guān)榮.網(wǎng)絡(luò)科學(xué)導(dǎo)論［M］.北京：高等教育出版社，2012.

［9］袁榮坤，孟相如，李明迅，等.節(jié)點重要度的網(wǎng)絡(luò)抗毀性評估方法［J］.火力與指揮控制，2012，37（10）：40-42.

Research of Complex Networks Node Importance Ranking Based on Natural Connectivity

SHEN An-wei，GUO Ji-lian，WANG Zhuo-jian
（School of Aeronautics and Astronautics Engineering，Air Force University of Engineering，Xi’an 710038，China）

Node importance ranking of complex networks is a hot topic nowadays.This paper gives the definition of natural connectivity.And then the method of complex networks node importance ranking based on natural connectivity has been proposed.Finally，the applicability of proposed method is analyzed by an example of kite network.The contrast of proposed method and other common method prove that the reasonability of our method.

complex networks，natural connectivity，kite network，node importance

TP399

A

1002-0640（2017）05-0052-04

2016-03-17

2016-06-17

國家自然科學(xué)基金資助項目（71501185）

沈安慰（1988- ），男，浙江衢州人，在讀博士研究生。研究方向：飛機(jī)RMS論證與評估。