蔣豐景，陳玥琪

(西安電子科技大學(xué)理學(xué)院，陜西西安710071)

復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)重要度的一個(gè)評(píng)估指標(biāo)

蔣豐景，陳玥琪

(西安電子科技大學(xué)理學(xué)院，陜西西安710071)

為了簡(jiǎn)單而有效地評(píng)估網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中各節(jié)點(diǎn)重要性，本文基于節(jié)點(diǎn)的連接度和局部連通性，定義了一個(gè)節(jié)點(diǎn)重要度函數(shù).該重要度函數(shù)指標(biāo)實(shí)質(zhì)上與網(wǎng)絡(luò)中的平均最短距離指標(biāo)是一致的，通過該重要度函數(shù)指標(biāo)值的大小可以得到網(wǎng)絡(luò)中各節(jié)點(diǎn)的重要度排序.理論分析與實(shí)例表明，對(duì)于小型網(wǎng)絡(luò)，該方法的計(jì)算比較簡(jiǎn)單，且直觀、有效、合理.

節(jié)點(diǎn)重要度;鄰居節(jié)點(diǎn);節(jié)點(diǎn)刪除;平均最短距離

隨著信息技術(shù)飛速發(fā)展，互聯(lián)網(wǎng)已成為社會(huì)輿論傳播的主要載體之一，無(wú)論是現(xiàn)實(shí)生活還是系統(tǒng)科學(xué)，都與網(wǎng)絡(luò)密切相關(guān).特別是很多實(shí)際網(wǎng)絡(luò)所抽象出來(lái)的復(fù)雜網(wǎng)絡(luò)，表現(xiàn)出了與以往網(wǎng)絡(luò)理論不同的特性［1］，如小世界特性、無(wú)尺度特性等.如何在復(fù)雜網(wǎng)絡(luò)環(huán)境下，保證網(wǎng)絡(luò)的可靠性和抗毀性［2］成為復(fù)雜網(wǎng)絡(luò)研究的重要課題.研究表明，在選擇性打擊下，即優(yōu)先攻擊網(wǎng)絡(luò)中“核心節(jié)點(diǎn)”，無(wú)標(biāo)度網(wǎng)絡(luò)異常脆弱，網(wǎng)絡(luò)基本處于癱瘓狀態(tài).因此，找出網(wǎng)絡(luò)中的“核心節(jié)點(diǎn)”并將它們保護(hù)起來(lái)對(duì)維持整個(gè)網(wǎng)絡(luò)的可靠性具有重要作用;同時(shí)，“核心節(jié)點(diǎn)”的保障和維護(hù)對(duì)實(shí)現(xiàn)網(wǎng)絡(luò)信息流通和降低網(wǎng)絡(luò)信息交換成本，提高信息流通效率有重要意義.網(wǎng)絡(luò)節(jié)點(diǎn)的重要度指標(biāo)的度量方法有節(jié)點(diǎn)的度、接近度、介數(shù)、信息、特征向量和累計(jì)提名等.其中最簡(jiǎn)單的方法是以節(jié)點(diǎn)的度作為節(jié)點(diǎn)重要性的衡量標(biāo)準(zhǔn)，認(rèn)為節(jié)點(diǎn)的度越大則該節(jié)點(diǎn)越重要，但一個(gè)節(jié)點(diǎn)的度僅僅描述了該節(jié)點(diǎn)對(duì)于其他節(jié)點(diǎn)的直接影響力，因此有很大的片面性;文獻(xiàn)［3］提出了一種基于生成樹數(shù)目的節(jié)點(diǎn)刪除法，如果多個(gè)節(jié)點(diǎn)的刪除都使得網(wǎng)絡(luò)不連通，那么這些節(jié)點(diǎn)的重要度將是一致的，從而使得評(píng)估不精確;文獻(xiàn)［4］提出的介數(shù)能很好地衡量節(jié)點(diǎn)重要度，但計(jì)算節(jié)點(diǎn)的介數(shù)非常復(fù)雜，不僅要計(jì)算各個(gè)節(jié)點(diǎn)對(duì)之間的最短路徑長(zhǎng)度，還要記錄這些最短路徑的路線.

本文利用網(wǎng)絡(luò)的連通性來(lái)反映系統(tǒng)某種功能的完整性，通過度量節(jié)點(diǎn)刪除對(duì)網(wǎng)絡(luò)連通的破壞程度來(lái)反映網(wǎng)絡(luò)節(jié)點(diǎn)(集)的重要性，即“破壞性等價(jià)于重要性”.從這種思想出發(fā)構(gòu)造了一個(gè)和平均最短路徑指標(biāo)具有等價(jià)性的節(jié)點(diǎn)重要度函數(shù)指標(biāo)I(vi)，利用該函數(shù)可以有效地判定網(wǎng)絡(luò)中各節(jié)點(diǎn)重要程度的大小，并且無(wú)需復(fù)雜的計(jì)算，實(shí)例計(jì)算也驗(yàn)證了該方法的合理性.

1 節(jié)點(diǎn)重要度評(píng)估模型

本文所研究的復(fù)雜網(wǎng)絡(luò)均為無(wú)向、無(wú)權(quán)、無(wú)重邊網(wǎng)絡(luò)，用圖G=(V，E)表示，其中V={v1，v2，…，vn}表示網(wǎng)絡(luò)G中節(jié)點(diǎn)的集合，E={e1，e2，…，em}為G中邊的集合.

定義1節(jié)點(diǎn)vi的度是指與它相關(guān)聯(lián)的邊的條數(shù)，記為ki.

定義2節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)是指與vi直接有邊相連的那些節(jié)點(diǎn)，這些節(jié)點(diǎn)的集合構(gòu)成vi的鄰居節(jié)點(diǎn)集.

定義3把vi和vj之間跳數(shù)最少的路徑稱為它們的最短路徑，顯然，vi和vj之間的最短路徑可能不止一條.

定義5定義li為刪除節(jié)點(diǎn)vi后，網(wǎng)絡(luò)中vi的鄰居節(jié)點(diǎn)集中保持連通的節(jié)點(diǎn)對(duì)數(shù)目.根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)與邊的關(guān)系，有l(wèi)i為介于0與ki(ki-1)/2的正整數(shù).當(dāng)li比較大時(shí)，表明刪除節(jié)點(diǎn)vi后，網(wǎng)絡(luò)的連通性仍然很好，即節(jié)點(diǎn)vi自身的重要性相對(duì)比較小，這個(gè)指標(biāo)可以有效地反映節(jié)點(diǎn)的局部連通情況，因此可以用它來(lái)考慮網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性.

定義6稱I(vi)=［ki(ki-1)］/［2(li+1)］為節(jié)點(diǎn)vi的重要度函數(shù)，考慮到葉子節(jié)點(diǎn)的li為0的情況，定義分母為li+1.該指標(biāo)從節(jié)點(diǎn)自身的連接度和節(jié)點(diǎn)的局部連通性考慮了節(jié)點(diǎn)的重要性.同等條件下，連接度越大的節(jié)點(diǎn)收縮以后，網(wǎng)絡(luò)中節(jié)點(diǎn)和邊的數(shù)目就越少，因此該節(jié)點(diǎn)相對(duì)越重要.而處于關(guān)鍵位置的節(jié)點(diǎn)重要度也相對(duì)而言比較高，因?yàn)楹芏喙?jié)點(diǎn)對(duì)之間的最短路徑都要經(jīng)過該節(jié)點(diǎn)，該節(jié)點(diǎn)收縮后將減少網(wǎng)絡(luò)的平均最短距離，因此該節(jié)點(diǎn)比較重要.

2 節(jié)點(diǎn)重要性指標(biāo)

網(wǎng)絡(luò)節(jié)點(diǎn)之間進(jìn)行通信的路徑首選最短路徑，如果某個(gè)節(jié)點(diǎn)被許多最短路徑經(jīng)過，則表明該節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中的作用和影響力是比較大的.因此，把網(wǎng)絡(luò)中平均最短路徑作為節(jié)點(diǎn)重要性指標(biāo)是比較合理的，但是它的計(jì)算式比較復(fù)雜，因?yàn)椴粌H要計(jì)算出每個(gè)節(jié)點(diǎn)對(duì)之間的最短路徑長(zhǎng)度，并且還要記錄這些最短路徑.下面分析說(shuō)明本文定義的節(jié)點(diǎn)重要度函數(shù)指標(biāo)與網(wǎng)絡(luò)中平均最短路徑指標(biāo)具有一致性，只是放大的顯著性程度有所差別.

當(dāng)節(jié)點(diǎn)vi被刪除或者收縮后網(wǎng)絡(luò)中平均最短路徑變化情況如下：

如果節(jié)點(diǎn)vi不在最短路徑上，則一部分節(jié)點(diǎn)的最短路徑不經(jīng)過vi.因此，當(dāng)節(jié)點(diǎn)vi被刪除或者收縮后對(duì)這些節(jié)點(diǎn)的最短路徑無(wú)影響，從而對(duì)整個(gè)網(wǎng)絡(luò)的平均最短路徑也沒有影響.如果節(jié)點(diǎn)間的最短路徑經(jīng)過vi，則刪除節(jié)點(diǎn)vi后這些節(jié)點(diǎn)間的最短路徑將會(huì)發(fā)生變化.假設(shè)被刪除節(jié)點(diǎn)的li比較小，即節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)的連通性比較差，則最短路徑中經(jīng)過vi的鄰居節(jié)點(diǎn)的概率比較小.相對(duì)而言，經(jīng)過vi的最短路徑的概率就比較大，這與li減小，I(vi)增大是一致的.因此，節(jié)點(diǎn)的I(vi)越大，表明刪除節(jié)點(diǎn)vi后，通過vi的最大路徑變大，從而網(wǎng)絡(luò)的平均最短路徑變大.也就是，節(jié)點(diǎn)vi的I(vi)越大，刪除vi后網(wǎng)絡(luò)的平均最短距離變大.因此，本文定義的節(jié)點(diǎn)重要度函數(shù)指標(biāo)與網(wǎng)絡(luò)中平均最短路徑指標(biāo)具有一致性.

3 實(shí)例分析

設(shè)某網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)如圖1，用文獻(xiàn)［3］與文獻(xiàn)［5］得到節(jié)點(diǎn)4與節(jié)點(diǎn)6的重要度是一樣的，使用本文的方法有：節(jié)點(diǎn)4的度k4=4，l4為刪除節(jié)點(diǎn)4后，節(jié)點(diǎn)4的鄰居節(jié)點(diǎn)中保持連通的節(jié)點(diǎn)對(duì)數(shù)目，顯然l4=1，因此I(v4)=3.同樣很容易計(jì)算l(v6)=6.因此節(jié)點(diǎn)4的重要性程度比節(jié)點(diǎn)6要小.從直觀上也可以發(fā)現(xiàn)，當(dāng)刪除節(jié)點(diǎn)4，節(jié)點(diǎn)1，2，3的連通性比刪除節(jié)點(diǎn)6后節(jié)點(diǎn)7，8，9的連通性要好，因此，節(jié)點(diǎn)4的重要性比節(jié)點(diǎn)6的重要性要小.

由表1知，本文使用節(jié)點(diǎn)重要度函數(shù)指標(biāo)得到的節(jié)點(diǎn)重要度排序結(jié)果與文獻(xiàn)［7］中的方法得到的節(jié)點(diǎn)重要度排序結(jié)果是一致的，并且與實(shí)際結(jié)果是一致的.但是對(duì)于小型網(wǎng)絡(luò)，本文中計(jì)算節(jié)點(diǎn)重要度的方法更為簡(jiǎn)單.此外，若通過文獻(xiàn)［3］的方法，即考慮刪除節(jié)點(diǎn)后網(wǎng)絡(luò)的生成樹變化數(shù)目的變化情況，則節(jié)點(diǎn)4～7的重要度是一樣的.然而從直觀上看，網(wǎng)絡(luò)中這幾個(gè)節(jié)點(diǎn)的重要度是有差別的.因此本文的方法是合理有效的.

表1 節(jié)點(diǎn)重要度評(píng)估結(jié)果

圖1 含有9個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)拓?fù)鋱D

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

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

評(píng)估網(wǎng)絡(luò)中的節(jié)點(diǎn)重要性一直是社會(huì)網(wǎng)絡(luò)分析領(lǐng)域和系統(tǒng)科學(xué)研究領(lǐng)域的一個(gè)熱點(diǎn)，本文基于“破壞性等價(jià)于重要性”這一思想，構(gòu)造了一個(gè)節(jié)點(diǎn)重要度函數(shù)，從而使這一思想得到了精細(xì)的量化.對(duì)于小型網(wǎng)絡(luò)，該方法避免了復(fù)雜的計(jì)算，實(shí)例分析也驗(yàn)證了該方法的合理性、有效性和優(yōu)越性.

［1］汪小帆，李翔，陳光榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用［M］.北京：清華大學(xué)出版社，2006.

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

［3］陳勇，胡愛群.通信網(wǎng)絡(luò)中最重要節(jié)點(diǎn)確定方法［J］.高技術(shù)通訊，2004(1)：573-575.

［4］FREEMAN L C.A set of measures of centrality based upon betweenness［J］.Sociometry，1977，40(1)：35-41.

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

［6］陳勇，胡愛群，胡嘯.通信網(wǎng)中節(jié)點(diǎn)重要性的評(píng)價(jià)方法［J］.通信學(xué)報(bào)，2004，25(8)：129-134.

［7］陳靜，孫林夫.復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)重要度評(píng)估［J］.西南交通大學(xué)學(xué)報(bào)，2009，44(3)：426-429.

［8］孫睿，羅萬(wàn)伯.網(wǎng)絡(luò)輿論中節(jié)點(diǎn)重要性評(píng)估方案綜述［J］.計(jì)算機(jī)應(yīng)用研究，2012，29(10)：3 606-3 608.

［8］葉春森，汪傳雷，劉宏偉.節(jié)點(diǎn)重要度評(píng)價(jià)方法研究［J］.統(tǒng)計(jì)與決策，2010(1)：22-24.

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

An evaluation index of node importance in complex networks

JIANG Feng-jing，CHEN Yue-qi

(College of Science，Xidian University，Xi'an 710071，China)

To simply and effectively evaluate the importance of each node in network topology structure，a node importance function based on the node connectivity degree and local connectivity is defined.The index of the node importance function is substantially consistent with the index of the average shortest path in networks，the importance of each node in the network can be sorted by the size of the index value.For small networks，it is relatively simple in calculation，the method is vertified more intuitive，effective and reasonable by theoretical analysis and practical examples.

node importance;neighbor node;node removal;average shortest distance

C 934

A

1674-649X(2014)01-0140-03

編輯：：武暉;校對(duì)：孟超

2013-04-15

蔣豐景(1989-)，男，江蘇省淮安市人，西安電子科技大學(xué)碩士研究生.E-mail：727729909@qq.com