張惠玲, 張　蒙

(西安航空學(xué)院 理學(xué)院， 陜西 西安 710077)

網(wǎng)絡(luò)節(jié)點(diǎn)重要性的多指標(biāo)綜合評(píng)價(jià)方法

張惠玲, 張蒙

(西安航空學(xué)院 理學(xué)院， 陜西 西安 710077)

摘要:給出了網(wǎng)絡(luò)節(jié)點(diǎn)重要性的一種多指標(biāo)綜合評(píng)價(jià)方法。從網(wǎng)絡(luò)的備選路由數(shù)、網(wǎng)絡(luò)被分割的程度和網(wǎng)絡(luò)性能三方面考慮節(jié)點(diǎn)的重要性，分別引入“改進(jìn)的生成樹數(shù)目”、“改進(jìn)的網(wǎng)絡(luò)連通性”和“改進(jìn)的剩余節(jié)點(diǎn)對(duì)距離和的增量”三個(gè)指標(biāo)，并根據(jù)變異系數(shù)法，確定其權(quán)重，以其線性加權(quán)值作為節(jié)點(diǎn)重要性的測(cè)度。最后，利用該方法對(duì)一個(gè)無向圖的節(jié)點(diǎn)重要性進(jìn)行分析，并與節(jié)點(diǎn)刪除法進(jìn)行比較，該方法可行有效。

關(guān)鍵詞:網(wǎng)絡(luò)；節(jié)點(diǎn)重要性；變異系數(shù)法

網(wǎng)絡(luò)節(jié)點(diǎn)重要性分析方法主要有兩大類。社會(huì)網(wǎng)絡(luò)分析方法通常不破壞網(wǎng)絡(luò)的連通性，通過分析網(wǎng)絡(luò)節(jié)點(diǎn)的一些靜態(tài)屬性，如度、中心度、介數(shù)等，來判斷節(jié)點(diǎn)的重要性，即“顯著性等價(jià)于重要性”。系統(tǒng)科學(xué)分析方法通常破壞網(wǎng)絡(luò)的連通性，通過刪除網(wǎng)絡(luò)中的節(jié)點(diǎn)，給出一些度量網(wǎng)絡(luò)破壞程度的指標(biāo)來反映節(jié)點(diǎn)的重要性，即“破壞性等價(jià)于重要性”[1]。研究通信網(wǎng)絡(luò)的抗毀性能，就必須評(píng)價(jià)節(jié)點(diǎn)的重要程度，為確定通信網(wǎng)絡(luò)節(jié)點(diǎn)被移除的順序提供參考。

通過刪除節(jié)點(diǎn)，可以比較網(wǎng)絡(luò)性能變化，進(jìn)而確定網(wǎng)絡(luò)節(jié)點(diǎn)的重要性。刪除節(jié)點(diǎn)后生成樹數(shù)目的多少反映了通信網(wǎng)絡(luò)中任意兩節(jié)點(diǎn)的相對(duì)重要性[2]。定義網(wǎng)絡(luò)的連通性指標(biāo)，可以討論移除節(jié)點(diǎn)導(dǎo)致網(wǎng)絡(luò)被分割的情況[3]?；凇氨平硐肱判蚍ā钡亩鄬傩詻Q策方法，可以權(quán)衡影響節(jié)點(diǎn)重要性的多種因素，以確定節(jié)點(diǎn)的重要程度[4]。利用基于最短路徑介數(shù)的方法，也可確定網(wǎng)絡(luò)中的重要性節(jié)點(diǎn)[5]。利用節(jié)點(diǎn)收縮的方法，通過刪除待分析節(jié)點(diǎn)的鄰接點(diǎn)來判斷節(jié)點(diǎn)的重要度，能夠簡化計(jì)算復(fù)雜度[6]，但容易忽略節(jié)點(diǎn)刪除后所導(dǎo)致的網(wǎng)絡(luò)結(jié)構(gòu)變化，從而引起節(jié)點(diǎn)重要性的變化。定義相關(guān)指標(biāo)，利用線性運(yùn)算將指標(biāo)結(jié)合起來，即可定義節(jié)點(diǎn)的重要性[7]。將節(jié)點(diǎn)的度平均分配到各個(gè)相鄰節(jié)點(diǎn)后，又結(jié)合介數(shù)構(gòu)造重要度評(píng)價(jià)矩陣，由此可以給出節(jié)點(diǎn)重要度評(píng)價(jià)方法[8]。在若節(jié)點(diǎn)被刪除后網(wǎng)絡(luò)仍然是連通的情況下，定義“剩余節(jié)點(diǎn)對(duì)最短距離和增量”指標(biāo)，可以給出網(wǎng)絡(luò)節(jié)點(diǎn)的相對(duì)重要性[9]。

單一指標(biāo)的提出一般都只是針對(duì)網(wǎng)絡(luò)的某種性能，難以整體上有效評(píng)價(jià)網(wǎng)絡(luò)節(jié)點(diǎn)的重要性。網(wǎng)絡(luò)中節(jié)點(diǎn)的重要程度需要從不同的角度來考慮，利用節(jié)點(diǎn)的多個(gè)重要性指標(biāo)來進(jìn)行綜合評(píng)價(jià)。多指標(biāo)綜合評(píng)價(jià)方法是將所選擇的有代表性的若干指標(biāo)綜合成一個(gè)指數(shù)[10]，從而對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)的重要性做出綜合評(píng)價(jià)。此過程需要解決兩個(gè)問題，一是指標(biāo)的歸一化，二是綜合時(shí)權(quán)重的確定。尤其對(duì)于指標(biāo)權(quán)重的確定，僅憑主觀因素是缺乏科學(xué)性的，不具說服力。

本文擬從網(wǎng)絡(luò)的備選路由數(shù)、網(wǎng)絡(luò)被分割的程度和網(wǎng)絡(luò)性能三方面考慮節(jié)點(diǎn)的重要性，分別引入“改進(jìn)的生成樹數(shù)目”、“改進(jìn)的網(wǎng)絡(luò)連通性”和“改進(jìn)的剩余節(jié)點(diǎn)對(duì)距離和的增量”三個(gè)指標(biāo)，然后將它們歸一化，再利用變異系數(shù)法，給出三個(gè)指標(biāo)相應(yīng)的權(quán)重，從而得出一種判斷網(wǎng)絡(luò)節(jié)點(diǎn)重要性的方法，以求更加合理地反映刪除節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)性能的影響。

1評(píng)價(jià)指標(biāo)的歸一化

1.1生成樹數(shù)目指標(biāo)

生成樹的數(shù)目可以作為評(píng)價(jià)節(jié)點(diǎn)重要性的一個(gè)指標(biāo)[2]。為了與其他指標(biāo)進(jìn)行綜合，將其歸一化。確定圖G中節(jié)點(diǎn)vi的重要性指標(biāo)為

其中G-vi表示去掉節(jié)點(diǎn)vi以及與其相連的邊之后得到的子圖，τ(G)表示圖G的生成樹數(shù)目。

1.2改進(jìn)的網(wǎng)絡(luò)連通性指標(biāo)

為表示刪除節(jié)點(diǎn)vi后，網(wǎng)絡(luò)中不連通的節(jié)點(diǎn)對(duì)數(shù)目，可設(shè)

則刪除vi后網(wǎng)絡(luò)中不連通的節(jié)點(diǎn)對(duì)數(shù)目為

它越大，節(jié)點(diǎn)vi越重要。對(duì)此指標(biāo)歸一化，得

1.3改進(jìn)的剩余節(jié)點(diǎn)對(duì)最短距離和增量指標(biāo)

設(shè)節(jié)點(diǎn)vi被刪除前后,節(jié)點(diǎn)vj和vk之間的最短距離分別為Djk和dij,則節(jié)點(diǎn)vi未被刪除前,原網(wǎng)絡(luò)中除節(jié)點(diǎn)vi外所有節(jié)點(diǎn)對(duì)之間的最短距離之和

節(jié)點(diǎn)vi被刪除后,網(wǎng)絡(luò)中剩余節(jié)點(diǎn)對(duì)之間的最短距離之和

節(jié)點(diǎn)vi被刪除前后，除去節(jié)點(diǎn)vi剩余節(jié)點(diǎn)對(duì)最短距離和的增量

δi=SG-vi-SG(vi)。

此增量越大，表明節(jié)點(diǎn)vi越重要。對(duì)此指標(biāo)歸一化，得

該指標(biāo)考慮的是節(jié)點(diǎn)被刪除后網(wǎng)絡(luò)仍然連通的情形，若節(jié)點(diǎn)vi被刪除后網(wǎng)絡(luò)不連通，可直接令

Δi=1。

2變異系數(shù)法與指標(biāo)權(quán)重

2.1變異系數(shù)法

在評(píng)價(jià)體系中，指標(biāo)取值的變異系數(shù)越大，說明該指標(biāo)的個(gè)體取值差異越大，所含的信息量越大。越能反映被評(píng)價(jià)個(gè)體差距的指標(biāo)，越應(yīng)該予以重視，越應(yīng)給予較大的權(quán)重。變異系數(shù)越小，指標(biāo)所含的信息量越小，指標(biāo)反映的個(gè)體差異越小，權(quán)重應(yīng)該越小。

設(shè)σj是第j項(xiàng)指標(biāo)的標(biāo)準(zhǔn)差，μj是第j項(xiàng)指標(biāo)的平均數(shù)。定義標(biāo)準(zhǔn)差與平均數(shù)的比值為變異系數(shù)，即第j項(xiàng)指標(biāo)的變異系數(shù)

于是第j項(xiàng)指標(biāo)的權(quán)重為

2.2綜合指標(biāo)

考慮“改進(jìn)的生成樹數(shù)目指標(biāo)”Ti，“改進(jìn)的網(wǎng)絡(luò)連通性指標(biāo)”Li，“改進(jìn)的剩余節(jié)點(diǎn)對(duì)最短距離和增量指標(biāo)”Δi三個(gè)指標(biāo),可得節(jié)點(diǎn)vi的重要性評(píng)價(jià)綜合指標(biāo)為

Mi=W1Ti+W2Li+W3Δi。

3分析驗(yàn)證

將綜合指標(biāo)分別應(yīng)用于評(píng)價(jià)簡單網(wǎng)絡(luò)和復(fù)雜網(wǎng)絡(luò)，并與已有算法的評(píng)價(jià)結(jié)果進(jìn)行比較。

3.1簡單網(wǎng)絡(luò)

針對(duì)如圖1所示的簡單網(wǎng)絡(luò)，分別去掉節(jié)點(diǎn)vi(i=1,2,…,7)后，相應(yīng)的各指標(biāo)值如表1所示。

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

去掉節(jié)點(diǎn)指標(biāo)Ti指標(biāo)Li指標(biāo)Δiv10.666700v20.666700v310.88891v4111v510.88891v60.666700v70.666700

根據(jù)表1中的數(shù)據(jù)，分別計(jì)算各指標(biāo)的平均數(shù)μj和標(biāo)準(zhǔn)差σj(j=1,2,3),可得

μ1=0.396 8,σ1=0.496 3,

μ2=0.428 6,σ2=0.534 5,

μ3=0.809 5,σ3=0.178 2。

變異系數(shù)分別為

各項(xiàng)指標(biāo)所占權(quán)重分別為

節(jié)點(diǎn)vi的重要性綜合指標(biāo)，及其與生成樹法[2]和節(jié)點(diǎn)收縮法[11]所確定的節(jié)點(diǎn)重要性對(duì)比結(jié)果如表2所示。

表2　節(jié)點(diǎn)重要性評(píng)價(jià)結(jié)果及比較

三種算法得出的節(jié)點(diǎn)重要性排序略有差異。依據(jù)綜合指標(biāo)法，最重要的節(jié)點(diǎn)是v4,而v3和v5次之，v1,v2,v6,v7序后。與另兩種方法相比，可以區(qū)別出節(jié)點(diǎn)v4比v3和v5更重要。造成這種差異的原因在于，生成樹法刪去節(jié)點(diǎn)v3或v4均導(dǎo)致剩余節(jié)點(diǎn)構(gòu)成的網(wǎng)絡(luò)圖的生成樹為0。另外，在按節(jié)點(diǎn)收縮法所得結(jié)果中，節(jié)點(diǎn)v4的重要性被排在節(jié)點(diǎn)v3和v5之后，顯然跟實(shí)際不符。

3.2復(fù)雜網(wǎng)絡(luò)

針對(duì)如圖2所示復(fù)雜網(wǎng)絡(luò)中各節(jié)點(diǎn)的重要性進(jìn)行分析。這是一個(gè)ARPA網(wǎng)絡(luò)拓?fù)洌欠治鼍W(wǎng)絡(luò)節(jié)點(diǎn)重要性時(shí)普遍使用的網(wǎng)絡(luò)拓?fù)?。該網(wǎng)絡(luò)由21個(gè)節(jié)點(diǎn)和23條邊組成，大部分節(jié)點(diǎn)的度為2。

圖2　ARPA網(wǎng)絡(luò)拓?fù)?/p>

分別利用綜合指標(biāo)法、生成樹法[2]和節(jié)點(diǎn)收縮法[11]進(jìn)行分析，所得節(jié)點(diǎn)重要性排序結(jié)果如表3所示。

表3　ARPA網(wǎng)的節(jié)點(diǎn)重要性評(píng)價(jià)結(jié)果

生成樹法考慮的是移除節(jié)點(diǎn)后生成樹的數(shù)目變化，而節(jié)點(diǎn)收縮法考慮的是節(jié)點(diǎn)收縮后網(wǎng)絡(luò)路徑和頂點(diǎn)數(shù)的變化。根據(jù)生成樹法，v7～v11這5個(gè)節(jié)點(diǎn)被認(rèn)為重要性一致，沒有區(qū)別，而根據(jù)綜合指標(biāo)法，這5個(gè)節(jié)點(diǎn)的重要性是有區(qū)別的，這與依據(jù)節(jié)點(diǎn)收縮法所得結(jié)果一致，更為精確。不同的時(shí)，依據(jù)節(jié)點(diǎn)收縮法，最重要節(jié)點(diǎn)是v6，而依據(jù)綜合指標(biāo)法，最重要節(jié)點(diǎn)是v3，這又與依據(jù)生成樹法所得出的結(jié)果一致。

4結(jié)語

引入節(jié)點(diǎn)的“改進(jìn)的生成樹數(shù)目”、“改進(jìn)的網(wǎng)絡(luò)連通性”和“改進(jìn)的剩余節(jié)點(diǎn)對(duì)最短距離和增量”三個(gè)指標(biāo)，借助變異系數(shù)法確定其權(quán)重，利用綜合指法分析節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要程度。就簡單網(wǎng)絡(luò)和ARPA復(fù)雜網(wǎng)絡(luò)所進(jìn)行的計(jì)算顯示，這種分析方法是有效的，且能克服單一指標(biāo)判斷節(jié)點(diǎn)重要性的不足。

參考文獻(xiàn)

[1]周漩，張鳳鳴，李克武，等.利用重要度評(píng)價(jià)矩陣確定復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)[J]. 物理學(xué)報(bào)，2012，61(5)：1-7.

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

[3]余新，李艷和，鄭小平，等. 基于網(wǎng)絡(luò)性能變化梯度的通信網(wǎng)絡(luò)節(jié)點(diǎn)重要程度評(píng)價(jià)方法[J]. 清華大學(xué)學(xué)報(bào)：自然科學(xué)版.2008，48(4)：541-544.

[4]于會(huì)，劉尊，李勇軍. 基于多屬性決策的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性綜合評(píng)價(jià)方法[J]. 物理學(xué)報(bào)，2013，62(2)：1-9.

[5]張珍，張振宇，宋蔓蔓. 一種基于最短路徑介數(shù)的重要節(jié)點(diǎn)發(fā)現(xiàn)算法[J].計(jì)算機(jī)工程與應(yīng)用，2013，49(21)98-100.

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

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

[8]趙毅寰，王祖林，鄭晶，等. 利用重要性貢獻(xiàn)矩陣確定通信網(wǎng)中最重要節(jié)點(diǎn)[J].北京航空航天大學(xué)學(xué)報(bào)，2009，35(9)：1076-1079.

[9]李琳，劉雅奇. 通信網(wǎng)節(jié)點(diǎn)重要性的多指標(biāo)評(píng)價(jià)方法[J]. 海軍工程大學(xué)學(xué)報(bào)，2010，22(5)：69-73.

[10] 鐘霞，鐘懷軍. 多指標(biāo)綜合評(píng)價(jià)方法及其應(yīng)用[J].內(nèi)蒙古大學(xué)學(xué)報(bào)：人文社會(huì)科學(xué)版，2004，36(4)：107-111.

[11]WUJ,TANYJ.Findingthemostvitalnodebynodeconstractionincommunicationnetworks[C]//IEEEInternationalConferenceonCommunications.Changsha:IEEEPress, 2005:1283-1286.

[責(zé)任編輯:瑞金]

Multi-indexcomprehensiveevaluationmethodonnetworknodeimportance

ZHANGHuiling,ZHANGMeng

(SchoolofScience,Xi’anAerotechnicalUniversity,Xi’an710077,China)

Abstract:A multi-index comprehensive evaluation method for the importance of network nodes is proposed. The node importance is considered according to the three aspects of network: alternate routing number, the partition of the network degree and network performance. Three indexes, which are the number of spanning tree improved, improved network connectivity, and the increase of the sum of the distance improved between certain nodes, are introduced, and their weights are determined through the variation coefficient method. Then their linear weighted value is regarded as a measure of the importance of nodes. Finally, this method is used to analyze the importance of the nodes in an undirected graph, and compared to Node deletion method. Results show that this method is feasible and effective.

Keywords:network, node importance, variation coefficient method

doi:10.13682/j.issn.2095-6533.2016.01.007

收稿日期：2015-04-20

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(11171271)

作者簡介：張惠玲(1979-)，女，博士，副教授，從事復(fù)雜網(wǎng)絡(luò)研究。E-mail: huilingzhang0915@163.com 張蒙(1981-)，男，碩士，講師，從事博弈論研究。 E-mail: 24042807@qq.com

中圖分類號(hào)：TN915

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：2095-6533(2016)01-0038-04