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

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

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

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

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

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

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

0 引言

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

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

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

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

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

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

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

1.1 節(jié)點(diǎn)度

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

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

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

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

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

1.3 度與集聚系數(shù)

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

1.4 緊密度

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

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

1.5 Kernel函數(shù)法

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

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

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

2.1 理論基礎(chǔ)

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

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

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

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

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

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

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

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

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

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

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

2.2 方法步驟

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

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

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

3 案例分析

以Krackhardt設(shè)計(jì)的“風(fēng)箏網(wǎng)絡(luò)”為例［8］，分析本文提出的基于自然連通度的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性度量方法。風(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é)點(diǎn)重要性度量結(jié)果

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

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

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

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

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

4 結(jié)論

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

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

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

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

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

［5］饒育萍，林競(jìng)焉，月東方.網(wǎng)絡(luò)抗毀度和節(jié)點(diǎn)重要性評(píng)價(jià)方法［J］.計(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é)點(diǎn)重要度的網(wǎng)絡(luò)抗毀性評(píng)估方法［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

國(guó)家自然科學(xué)基金資助項(xiàng)目（71501185）

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