基于復(fù)雜網(wǎng)絡(luò)異質(zhì)性的節(jié)點(diǎn)重要性評(píng)估方法

黃加增

?

基于復(fù)雜網(wǎng)絡(luò)異質(zhì)性的節(jié)點(diǎn)重要性評(píng)估方法

黃加增

（福建農(nóng)林大學(xué)東方學(xué)院，福建福州 350017）

對(duì)于復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)特殊性，用加權(quán)拓?fù)潇貫槔碚摶A(chǔ)，提出了基于復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)異質(zhì)性變化率的節(jié)點(diǎn)重要程度評(píng)估方法。首先，本文給出了復(fù)雜網(wǎng)絡(luò)加權(quán)拓?fù)潇氐母拍睿U述了基于BBV網(wǎng)絡(luò)的反向演化原理，其次，在反向演化原理的基礎(chǔ)上提出了節(jié)點(diǎn)重要程度取決于網(wǎng)絡(luò)結(jié)構(gòu)異質(zhì)性變化率的觀點(diǎn)，并提出了網(wǎng)絡(luò)割點(diǎn)的異質(zhì)性變化率的計(jì)算方法；最后，以一個(gè)例子來說明節(jié)點(diǎn)重要程度的評(píng)估過程，并對(duì)特殊節(jié)點(diǎn)進(jìn)行了處理分析。

復(fù)雜網(wǎng)絡(luò)，加權(quán)網(wǎng)絡(luò)，加權(quán)拓?fù)潇?，異質(zhì)性變化率，節(jié)點(diǎn)重要程度評(píng)估

0 引言

研究復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性方法主要有兩種：社會(huì)網(wǎng)絡(luò)分析方法和系統(tǒng)科學(xué)方法。其中，社會(huì)網(wǎng)絡(luò)分析方法的主要思想是“假設(shè)顯著性等價(jià)于重要性”，其強(qiáng)調(diào)的是節(jié)點(diǎn)在網(wǎng)絡(luò)中發(fā)揮的作用和功能，即通過度量某個(gè)節(jié)點(diǎn)與網(wǎng)絡(luò)中其他節(jié)點(diǎn)的連接數(shù)量來衡量這個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要程度[1-3]，一般地是以節(jié)點(diǎn)度（Degree）、介數(shù)（Betweenness）、接近度（Closeness）等各種不同的指標(biāo)加以衡量；系統(tǒng)科學(xué)方法的主要思想是“假設(shè)破壞性等價(jià)于重要性”，其原理是以計(jì)算某個(gè)節(jié)點(diǎn)失效后會(huì)給網(wǎng)絡(luò)帶來的破壞程度衡量其重要性[4-11]，如PageRank、HITS、SALSA、PopRank、ObjectRank和RealWalk等較為經(jīng)典的算法。

我國(guó)研究學(xué)者在節(jié)點(diǎn)重要性評(píng)估方面也做了許多的工作，特別是在第二種研究方法方面有許多較為突出的貢獻(xiàn)，如席酉民和唐方成等提出的“核與核度理論”[12,13]，李振華和陳貴海等提出的“分點(diǎn)”概念[14]等。

目前大部分的網(wǎng)絡(luò)都是加權(quán)網(wǎng)絡(luò)（Weighted Network），網(wǎng)絡(luò)中的每條邊用來說明連接兩個(gè)節(jié)點(diǎn)之間是否存在，而且還顯示了這種連接的某種特性（如流量的大?。划?dāng)然，每個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中也扮演著不同角色，具有不完全相同的屬性和能力。無論是技術(shù)網(wǎng)絡(luò)方面的公共交通道路網(wǎng)絡(luò)、Internet網(wǎng)絡(luò)，還是科學(xué)家合作網(wǎng)絡(luò)、引文網(wǎng)絡(luò)等社會(huì)網(wǎng)絡(luò)，都在不同的側(cè)面顯示出其加權(quán)網(wǎng)絡(luò)的特性[15-17]。

對(duì)于上述兩種研究方法，針對(duì)加權(quán)網(wǎng)絡(luò)，通過引入能夠表征全局狀態(tài)的熵及其熵變理論，提出了以網(wǎng)絡(luò)加權(quán)拓?fù)潇氐淖兓孔鳛楣?jié)點(diǎn)重要程度的觀點(diǎn)。一方面，以加權(quán)網(wǎng)絡(luò)中的邊權(quán)和節(jié)點(diǎn)強(qiáng)度等屬性不僅可以表明節(jié)點(diǎn)在網(wǎng)絡(luò)中的不同位置和連接特性，而且還可以充分體現(xiàn)某些處于網(wǎng)絡(luò)邊緣的關(guān)鍵節(jié)點(diǎn)（如計(jì)算機(jī)網(wǎng)絡(luò)中的網(wǎng)關(guān)、服務(wù)器等節(jié)點(diǎn)）的重要性；另一方面，通過能體現(xiàn)網(wǎng)絡(luò)整體狀態(tài)的熵的變遷衡量不同節(jié)點(diǎn)被刪除后對(duì)網(wǎng)絡(luò)所產(chǎn)生的破壞程度。

1 網(wǎng)絡(luò)加權(quán)拓?fù)潇?/h2>

在信息論中，申農(nóng)（Claude E. Shannon）將信息熵定義為離散隨機(jī)事件的出現(xiàn)概率，或者說是信息熵是消除不確定性的一種度量。仿照信息熵的定義，譚躍進(jìn)等人提出了網(wǎng)絡(luò)結(jié)構(gòu)熵的概念，并將其引入到網(wǎng)絡(luò)異質(zhì)性的研究中。在文獻(xiàn)[18]中，譚躍進(jìn)將無標(biāo)度網(wǎng)絡(luò)的網(wǎng)絡(luò)結(jié)構(gòu)熵定義為，其中：，為節(jié)點(diǎn)的度。這個(gè)定義的基本假設(shè)是：網(wǎng)絡(luò)節(jié)點(diǎn)的重要程度完全由這個(gè)節(jié)點(diǎn)的度所決定。

由于上述假設(shè)的缺陷，以及上述定義無法描述加權(quán)復(fù)雜網(wǎng)絡(luò)的拓?fù)錉顩r，本文提出了能夠描述加權(quán)復(fù)雜網(wǎng)絡(luò)異質(zhì)性的定義：

和一般意義上的熵一樣，網(wǎng)絡(luò)加權(quán)拓?fù)潇匾簿哂袠O值，即當(dāng)網(wǎng)絡(luò)結(jié)構(gòu)完全均勻時(shí)，網(wǎng)絡(luò)加權(quán)拓?fù)潇剡_(dá)到其極值。可以很方便地證明這個(gè)極值的存在：

首先，當(dāng)網(wǎng)絡(luò)完全均勻時(shí)，所有的邊權(quán)都會(huì)取同樣的權(quán)、所有的節(jié)點(diǎn)都具有相同的節(jié)點(diǎn)強(qiáng)度。事實(shí)上，這時(shí)的網(wǎng)絡(luò)加權(quán)拓?fù)潇匾呀?jīng)和譚躍進(jìn)教授的網(wǎng)絡(luò)結(jié)構(gòu)熵沒有任何區(qū)別。

因此，在網(wǎng)絡(luò)完全均勻時(shí)網(wǎng)絡(luò)加權(quán)拓?fù)潇厝〉臉O值為：

2 加權(quán)網(wǎng)絡(luò)的演化

2.1 節(jié)點(diǎn)加入網(wǎng)絡(luò)時(shí)的演化

以BBV加權(quán)網(wǎng)絡(luò)為例，當(dāng)某個(gè)節(jié)點(diǎn)加入網(wǎng)絡(luò)并與若干個(gè)節(jié)點(diǎn)相連時(shí)，相關(guān)邊權(quán)和節(jié)點(diǎn)強(qiáng)度按照下列方式進(jìn)行演化：

即節(jié)點(diǎn)強(qiáng)度越大被選中的可能性也越大。

（3）

（5）

2.2 節(jié)點(diǎn)退出網(wǎng)絡(luò)時(shí)的演化

在BBV加權(quán)網(wǎng)絡(luò)中，當(dāng)某個(gè)節(jié)點(diǎn)退出網(wǎng)絡(luò)時(shí)，網(wǎng)絡(luò)中邊的權(quán)重和節(jié)點(diǎn)的強(qiáng)度都會(huì)發(fā)生演化，也就是說這種演化同樣會(huì)發(fā)生在有節(jié)點(diǎn)退出的相關(guān)局域網(wǎng)絡(luò)中。

（7）

（8）

（10）

簡(jiǎn)單證明如下：

3 網(wǎng)絡(luò)異質(zhì)性變化率與節(jié)點(diǎn)重要性評(píng)估

網(wǎng)絡(luò)加權(quán)拓?fù)潇乇碚髁思訖?quán)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的異質(zhì)性，是一種能夠描述加權(quán)網(wǎng)絡(luò)整體狀態(tài)的指標(biāo)。只要網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生改變，網(wǎng)絡(luò)加權(quán)拓?fù)潇匾矔?huì)隨之發(fā)生改變。

對(duì)于加權(quán)網(wǎng)絡(luò)而言，當(dāng)某個(gè)節(jié)點(diǎn)退出網(wǎng)絡(luò)后，網(wǎng)絡(luò)中相關(guān)的邊權(quán)和節(jié)點(diǎn)強(qiáng)度都會(huì)發(fā)生變化，從而導(dǎo)致網(wǎng)絡(luò)異質(zhì)度也隨之發(fā)生變化。因此，我們可以通過網(wǎng)絡(luò)異質(zhì)度的變化率來判斷不同節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性。

在網(wǎng)絡(luò)中，可能會(huì)存在一些稱為“割點(diǎn)”（cut vertex）的特殊節(jié)點(diǎn)，一旦這種節(jié)點(diǎn)退出網(wǎng)絡(luò)后，則網(wǎng)絡(luò)會(huì)被分割成若干個(gè)獨(dú)立的連通子網(wǎng)。

根據(jù)反向演化原理，具有較大強(qiáng)度的節(jié)點(diǎn)退出網(wǎng)絡(luò)時(shí)，不僅僅是網(wǎng)絡(luò)節(jié)點(diǎn)的減少，而且也導(dǎo)致原來由退出節(jié)點(diǎn)所承擔(dān)的負(fù)荷被分配到其它節(jié)點(diǎn)上，從而使得網(wǎng)絡(luò)的異質(zhì)性發(fā)生改變。

根據(jù)加權(quán)拓?fù)潇氐淖兓?dāng)某節(jié)點(diǎn)退出網(wǎng)絡(luò)時(shí)，網(wǎng)絡(luò)異質(zhì)性有以下演化特性：

（1）節(jié)點(diǎn)的度越大，該節(jié)點(diǎn)的退出對(duì)網(wǎng)絡(luò)的異質(zhì)性影響就越大；

（2）與節(jié)點(diǎn)直接相連邊的權(quán)越大，該節(jié)點(diǎn)的退出對(duì)網(wǎng)絡(luò)的異質(zhì)性影響就越大；

（3）分?jǐn)偭藖碜杂趧e的節(jié)點(diǎn)的負(fù)荷越大，該節(jié)點(diǎn)的退出對(duì)網(wǎng)絡(luò)的異質(zhì)性影響就越大。

因此，可以將不同節(jié)點(diǎn)退出前后的網(wǎng)絡(luò)異質(zhì)性變化率作為評(píng)估這些節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要程度的依據(jù)。

4 舉例與分析

下面以一個(gè)示例對(duì)本文提出的節(jié)點(diǎn)重要程度評(píng)估方法加以說明：

圖1是一個(gè)加權(quán)網(wǎng)絡(luò)的拓?fù)鋱D，分別用基于異質(zhì)度的變化率和基于節(jié)點(diǎn)度的方法進(jìn)行節(jié)點(diǎn)重要性的評(píng)估。

圖1 一個(gè)加權(quán)網(wǎng)絡(luò)的拓?fù)鋱D

假設(shè)該網(wǎng)絡(luò)共有17個(gè)節(jié)點(diǎn)，各邊的權(quán)值分別如圖所示。表1是根據(jù)該網(wǎng)絡(luò)的結(jié)構(gòu)和邊權(quán)所計(jì)算的結(jié)果：

表1 初始計(jì)算結(jié)果

Tab.1 Initial results

下面分別計(jì)算不同節(jié)點(diǎn)退出網(wǎng)絡(luò)后，加權(quán)熵及其相關(guān)參數(shù)的變化情況。盡管任何一個(gè)節(jié)點(diǎn)退出后，對(duì)于連通網(wǎng)絡(luò)內(nèi)的各個(gè)節(jié)點(diǎn)的強(qiáng)度和邊權(quán)都會(huì)產(chǎn)生影響，在這里僅考慮與退出節(jié)點(diǎn)有直接連接的節(jié)點(diǎn)及其相關(guān)邊所發(fā)生的變化。

4.1 節(jié)點(diǎn)1退出網(wǎng)絡(luò)時(shí)

表2 節(jié)點(diǎn)1退出網(wǎng)絡(luò)后的各參數(shù)變化

Tab.2 Parameter changes of node 1 after exiting the network

根據(jù)表2，節(jié)點(diǎn)1退出網(wǎng)絡(luò)后，網(wǎng)絡(luò)拓?fù)浣?jīng)過演化，其加權(quán)拓?fù)潇貫椋骸?/p>

圖2 節(jié)點(diǎn)1退出后網(wǎng)絡(luò)的加權(quán)拓?fù)浣Y(jié)構(gòu)

同理，節(jié)點(diǎn)2、節(jié)點(diǎn)3、節(jié)點(diǎn)4、節(jié)點(diǎn)14、節(jié)點(diǎn)15、節(jié)點(diǎn)16和節(jié)點(diǎn)17等分別退出網(wǎng)絡(luò)后，網(wǎng)絡(luò)加權(quán)拓?fù)潇匾餐瑸?.381。

4.2 節(jié)點(diǎn)5退出網(wǎng)絡(luò)時(shí)

與節(jié)點(diǎn)5有直接連邊的節(jié)點(diǎn)分別為節(jié)點(diǎn)1、節(jié)點(diǎn)2、節(jié)點(diǎn)3、節(jié)點(diǎn)4和節(jié)點(diǎn)7。其中前4個(gè)節(jié)點(diǎn)除了與節(jié)點(diǎn)5有連接外，還與節(jié)點(diǎn)6有連接；而節(jié)點(diǎn)7則還與節(jié)點(diǎn)6、節(jié)點(diǎn)8和節(jié)點(diǎn)9有連接。節(jié)點(diǎn)5的退出，使得原來由節(jié)點(diǎn)5承擔(dān)的負(fù)荷都要被轉(zhuǎn)嫁到節(jié)點(diǎn)6上。

表3 節(jié)點(diǎn)5退出網(wǎng)絡(luò)后的各參數(shù)變化

根據(jù)表3，節(jié)點(diǎn)5退出網(wǎng)絡(luò)后，網(wǎng)絡(luò)拓?fù)浣?jīng)過演化，其加權(quán)拓?fù)潇貫椋骸?/p>

圖3 節(jié)點(diǎn)5退出后網(wǎng)絡(luò)的加權(quán)拓?fù)浣Y(jié)構(gòu)

同理，節(jié)點(diǎn)6、節(jié)點(diǎn)12和節(jié)點(diǎn)13等分別退出網(wǎng)絡(luò)后，網(wǎng)絡(luò)加權(quán)拓?fù)潇匾餐瑸?.3082。

4.3 節(jié)點(diǎn)7退出網(wǎng)絡(luò)時(shí)

與節(jié)點(diǎn)7有直接連邊的節(jié)點(diǎn)分別為節(jié)點(diǎn)5、節(jié)點(diǎn)6、節(jié)點(diǎn)8和節(jié)點(diǎn)9。節(jié)點(diǎn)7的退出，導(dǎo)致網(wǎng)絡(luò)分為兩個(gè)連通分支，網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生重大變化。其中，第一個(gè)連通分支由節(jié)點(diǎn)1~節(jié)點(diǎn)6組成，共有6個(gè)節(jié)點(diǎn)；第二個(gè)連通分支由節(jié)點(diǎn)8~節(jié)點(diǎn)17組成，共有10個(gè)節(jié)點(diǎn)。

表4 節(jié)點(diǎn)7退出第一個(gè)連通分支的各參數(shù)變化

Tab.4 The parameters of node 7 exiting the first connected branch

表5 節(jié)點(diǎn)7退出第二個(gè)連通分支的各參數(shù)變化

Tab.5 Node 7 exits the parameters of the second connected branches

圖4 節(jié)點(diǎn)7退出后網(wǎng)絡(luò)的加權(quán)拓?fù)浣Y(jié)構(gòu)

同理，節(jié)點(diǎn)11退出網(wǎng)絡(luò)后，網(wǎng)絡(luò)加權(quán)拓?fù)潇匾矠?.8496。

4.4 節(jié)點(diǎn)8退出網(wǎng)絡(luò)時(shí)

與節(jié)點(diǎn)8有直接連邊的節(jié)點(diǎn)分別為節(jié)點(diǎn)7和節(jié)點(diǎn)11。其中，節(jié)點(diǎn)7除了與節(jié)點(diǎn)8有連接外，還與節(jié)點(diǎn)5、節(jié)點(diǎn)6和節(jié)點(diǎn)9有連接；而節(jié)點(diǎn)11則還與節(jié)點(diǎn)10、節(jié)點(diǎn)12和節(jié)點(diǎn)13有連接。節(jié)點(diǎn)8的退出，使得原來由節(jié)點(diǎn)8承擔(dān)的負(fù)荷都要被轉(zhuǎn)嫁到節(jié)點(diǎn)7和節(jié)點(diǎn)11上。

表6 節(jié)點(diǎn)8退出網(wǎng)絡(luò)后的各參數(shù)變化

Tab.6 Parameter changes of node 8 after exiting the network

根據(jù)表6，節(jié)點(diǎn)8退出網(wǎng)絡(luò)后，網(wǎng)絡(luò)拓?fù)浣?jīng)過演化，其加權(quán)拓?fù)潇貫椋骸?/p>

圖5 節(jié)點(diǎn)8退出后網(wǎng)絡(luò)的加權(quán)拓?fù)浣Y(jié)構(gòu)

4.5 節(jié)點(diǎn)9退出網(wǎng)絡(luò)時(shí)

與節(jié)點(diǎn)9有直接連邊的節(jié)點(diǎn)分別為節(jié)點(diǎn)7和節(jié)點(diǎn)10。其中，節(jié)點(diǎn)7除了與節(jié)點(diǎn)9有連接外，還與節(jié)點(diǎn)5、節(jié)點(diǎn)6和節(jié)點(diǎn)8有連接；而節(jié)點(diǎn)10則還與節(jié)點(diǎn)11有連接。節(jié)點(diǎn)8的退出，使得原來由節(jié)點(diǎn)9承擔(dān)的負(fù)荷都要被轉(zhuǎn)嫁到節(jié)點(diǎn)7和節(jié)點(diǎn)10上。

表7 節(jié)點(diǎn)9退出網(wǎng)絡(luò)后的各參數(shù)變化

Tab.7 Parameter changes of node 9 after exiting the network

根據(jù)表7，節(jié)點(diǎn)9退出網(wǎng)絡(luò)后，網(wǎng)絡(luò)拓?fù)浣?jīng)過演化，其加權(quán)拓?fù)潇貫椋骸?/p>

圖6 節(jié)點(diǎn)9退出后網(wǎng)絡(luò)的加權(quán)拓?fù)浣Y(jié)構(gòu)

同理，節(jié)點(diǎn)10退出網(wǎng)絡(luò)后，網(wǎng)絡(luò)加權(quán)拓?fù)潇匾矠?.3121。

4.6 對(duì)比與分析

通過對(duì)加權(quán)拓?fù)潇氐挠?jì)算，可以看到：不同節(jié)點(diǎn)的退出對(duì)網(wǎng)絡(luò)的異質(zhì)性所帶來的影響各不相同，特別是割點(diǎn)的退出對(duì)網(wǎng)絡(luò)的異質(zhì)性影響尤為重大。表8描述了網(wǎng)絡(luò)異質(zhì)性變化率與節(jié)點(diǎn)度兩種不同的節(jié)點(diǎn)重要程度評(píng)估方法的對(duì)比。

表8 異質(zhì)性變化率與節(jié)點(diǎn)度對(duì)比表

Tab.8 Comparison table of heterogeneity change rate and node degree

從表中可以看到：

根據(jù)節(jié)點(diǎn)度方法的重要程度評(píng)估中，節(jié)點(diǎn)5、節(jié)點(diǎn)6、節(jié)點(diǎn)12和節(jié)點(diǎn)13為最重要的節(jié)點(diǎn)，因?yàn)檫@幾個(gè)節(jié)點(diǎn)的度最大；而根據(jù)異質(zhì)性變化率進(jìn)行的評(píng)估則認(rèn)為節(jié)點(diǎn)7和節(jié)點(diǎn)11的重要程度最高，因?yàn)檫@兩個(gè)節(jié)點(diǎn)所到導(dǎo)致的異質(zhì)性變化率最高。從實(shí)際來看，這樣的結(jié)論也是合理的，因?yàn)楣?jié)點(diǎn)7和節(jié)點(diǎn)11都是網(wǎng)絡(luò)的割點(diǎn)，不論是節(jié)點(diǎn)7還是節(jié)點(diǎn)11，只要退出網(wǎng)絡(luò)，則都會(huì)導(dǎo)致網(wǎng)絡(luò)連通性的破壞，而且所形成的兩個(gè)連通分支都具有較大的規(guī)模。

比較有意思的是節(jié)點(diǎn)8、節(jié)點(diǎn)9和節(jié)點(diǎn)10之間的重要程度排序。由于節(jié)點(diǎn)9和節(jié)點(diǎn)10是對(duì)稱關(guān)系，所以這里只討論節(jié)點(diǎn)8與節(jié)點(diǎn)9的重要程度排序：

● 當(dāng)節(jié)點(diǎn)8的節(jié)點(diǎn)強(qiáng)度小于節(jié)點(diǎn)9時(shí)，節(jié)點(diǎn)9的重要程度就大于節(jié)點(diǎn)8；

● 當(dāng)節(jié)點(diǎn)8的節(jié)點(diǎn)強(qiáng)度大于節(jié)點(diǎn)9的節(jié)點(diǎn)強(qiáng)度，但不超過2倍時(shí)，節(jié)點(diǎn)9的重要程度就大于節(jié)點(diǎn)8；

● 當(dāng)節(jié)點(diǎn)8的節(jié)點(diǎn)強(qiáng)度達(dá)到節(jié)點(diǎn)9的節(jié)點(diǎn)強(qiáng)度2倍時(shí)，節(jié)點(diǎn)8的重要程度就大于節(jié)點(diǎn)9。

除此而外，基于網(wǎng)絡(luò)異質(zhì)性變化率的節(jié)點(diǎn)重要程度評(píng)估方法還具有劃分層次更加豐富的特性。如上述例子中，根據(jù)節(jié)點(diǎn)度的方法只劃分了3個(gè)層次的重要程度，而根據(jù)異質(zhì)性變化率的方法則劃分出了5個(gè)不同的層次。豐富的層次可以為網(wǎng)絡(luò)的管理和維護(hù)提供更加可信的依據(jù)。

5 總結(jié)

熵是一個(gè)能夠反映系統(tǒng)整體狀態(tài)及其演化的指標(biāo)。本文從整體觀點(diǎn)進(jìn)行網(wǎng)絡(luò)節(jié)點(diǎn)重要程度評(píng)估方法的研究，并在BBV網(wǎng)絡(luò)的基礎(chǔ)上，提出了基于網(wǎng)絡(luò)異質(zhì)性變化率的評(píng)估方法。該方法具有以下一些特點(diǎn)：

（1）以網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的演化研究各節(jié)點(diǎn)在網(wǎng)絡(luò)中所發(fā)揮的作用，具有整體的視點(diǎn)，克服了諸如節(jié)點(diǎn)度方法等的局部觀點(diǎn)所固有的缺陷。

（2）通過邊權(quán)和節(jié)點(diǎn)強(qiáng)度計(jì)算，可以實(shí)時(shí)的反應(yīng)節(jié)點(diǎn)重要程度的動(dòng)態(tài)變化。

（3）采用影響因子的方式解決了多個(gè)連通分支時(shí)的異質(zhì)性變化率的計(jì)算問題。

（4）以異質(zhì)性變化率作為衡量的指標(biāo)，從而豐富了重要程度的層次。

總之，異質(zhì)性變化率的評(píng)估方法為網(wǎng)絡(luò)脆弱性的研究，并且能夠?yàn)槿粘５木W(wǎng)絡(luò)管理、維護(hù)和安全防范等都提供重要的依據(jù)。

[1] Albert R, Jeong H, Barabási A L. Error and attack tolerance of complex networks[J]. Nature. 2000, 406: 378-382.

[2] Reuters. Scientists spot Achilles heel of the Internet . United States: CNN, 2000 [2005207215]. http://archives.cnn.com/ 2000/TECH/computing/07/26/science. internet. reut/

[3] [3] Poulin R , Boily M C , Masse B R. Dynamical Systems to Define Cent rality in Social Networks[J]. Social Networks, 2000, 22: 187-220

[4] Lempel R, Moran S. The stochastic approach for link- structure analysis (SALSA) and the TKC effect. Computer Networks, 2000, 33(126): 387-401

[5] Nie Z, Zhang Y, Wen J-R, Ma W-Y. Object-level ranking: Bringing order to Web objects//Proceedings of the www. Chiba, Japan, 2005: 567-574

[6] Balmin A, Hristidis V, Papakonstantinou Y. Object rank : Authority-based keyword search in databases//Proceedings of the VLDB. Toronto, Canada , 2004: 564-575

[7] Geerts F, Mannila H, Terzi E. Relational link-based ranking// Proceedings of t he VLDB. Toronto, Canada, 2004: 552-563.

[8] Ding L, Pan R, Finin T, Joshi A, Peng Y, Kolari P. Finding and ranking knowledge on t he semantic Web//Proceedings of t he ISWC. Galway, Ireland, 2005: 156-170

[9] Guimera R. Classes of Complex Networks Definedby Role- to-role Connectivity Profiles[J]. Nature Physics, 2007 (3): 63-69

[10] 于會(huì), 劉尊, 李勇軍. 基于多屬性決策的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性綜合評(píng)價(jià)方法[J]. 物理學(xué)報(bào), 2013, 62(2), 1-9 YU H, LIU Z, LI Y J. Key nodes in complex networks identified by multi-attribute decision-making method[J]. Acta Physica Sinica, 2013, 62(2), 1-9. (in Chinese)

[11] 胡平, 王文, 劉志華. 綜合節(jié)點(diǎn)異質(zhì)性、刪除及DPA的網(wǎng)絡(luò)演化模型[J]. 管理科學(xué)學(xué)報(bào), 2011(8), 1-7, 16 HU P, WANG W, LIU Z H. Evolving network model of integrating three mechanisms: Node otherness, uniform node deletion and double preferential attachment[J]. Journal of management sciences in China, 2011(8), 1-7, 16. (in Chinese)

[12] Lusseau D , Newman M E J . Identifying the Role that Animals Play in Their Social Networks[C] Proceedings of the Royal Society of London Series B-biological Sciences , 2004 , 271(10): 477-481

[13] 席酉民, 唐方成. 組織的立體多核網(wǎng)絡(luò)模型研究[J]. 西安交通大學(xué)學(xué)報(bào), 2002, 36 (4) : 430-435. XI Y M, TANG F C. Research of organizational multiplex multi-kernel network model[J]. Journal of xi’an jiaotong university, 2002, 36 (4): 430-435. (in Chinese)

[14] 李振華, 陳貴海, 邱彤慶. 分點(diǎn): 無結(jié)構(gòu)對(duì)等網(wǎng)絡(luò)的拓?fù)潢P(guān)鍵點(diǎn)[J]. 軟件學(xué)報(bào), 2008, 19(9): 2376-2388. LI Z H, CHEN G H, QIU T Q. Partition node: topolog-ically-critical nodes of unstructured peer-to-peer networks[J]. Journal of software, 2008, 19(9): 2376-2388. (in Chinese)

[15] 郝彬彬, 井元偉, 張嗣瀛. 復(fù)雜網(wǎng)絡(luò)度分布的異質(zhì)性對(duì)其同步能力的影響[J]. 東北大學(xué)學(xué)報(bào): 自然科學(xué)版, 2008(11), 1521-1524 HAO B B, JING Y W, ZHANG S Y. Effect of heterogeneous distribution of degree on synchronization in complex networks[J ]. Journal of Northeastern University(Natural Science). 2008, (11), 1521-1524. (in Chinese)

[16] 王班, 馬潤(rùn)年, 王剛, 陳波. 改進(jìn)的加權(quán)網(wǎng)絡(luò)節(jié)點(diǎn)重要性評(píng)估的互信息方法[J]. 計(jì)算機(jī)應(yīng)用, 2015, 35(7), 1820-1823, 1828. WANG B, MA R N, WANG G, CHEN B. Improved evaluation method for node importance based on mutual information in weighted networks[J]. Journal of Computer Appli-cations, 2015, 35(7), 1820-1823, 1828. (in Chinese)

[17] 朱鵬鵬, 董建民, 李慧嘉. 節(jié)點(diǎn)重要性指標(biāo)在加權(quán)網(wǎng)絡(luò)中的應(yīng)用[J]. 計(jì)算機(jī)安全, 2013(4), 47-49 ZHU P P, DONG J M, LI H J. Application of vertex centrality indices to weighted networks[J]. Netword and computer security, 2013(4), 47-49. (in Chinese)

[18] 譚躍進(jìn), 吳俊. 網(wǎng)絡(luò)結(jié)構(gòu)熵及其在非標(biāo)度網(wǎng)絡(luò)中的應(yīng)用[J]. 系統(tǒng)工程理論與實(shí)踐, 2004, 24(6): 1-3. TAN Y J, WU J. Network structure entropy and its application to scale-free networks[J]. Systems engineering- theory and practice, 2004, 24(6): 1-3. (in Chinese)

Node Importance Evaluation Method Based on the Heterogeneity of Complex Networks

HUANG Jia-zeng

(Dongfang College, Fujian Agriculture and Forestry University, Fujian, Fuzhou 350017)

For the special structure of complex networks, weighted topological entropy theory, evaluation method of node important degree of heterogeneity of complex network structure based on the rate of change is proposed. Firstly, this paper gives the concept of weighted complex network topological entropy, elaborated the BBV network based on evolution principle, secondly, based on the principle of reverse evolution the proposed node important degree depends on the heterogeneity of network structure change rate of view, and puts forward the calculating method of heterogeneous change network cut point rate; finally, with an example to illustrate the evaluation process of node important degree, and the special nodes were analyzed.

Complex network; Weighted network; Weighted topological entropy; Heterogeneity change rate; Node importance evaluation

TP393.01

A

10.3969/j.issn.1003-6970.2017.04.014

基于粗糙概念格對(duì)城市交通科學(xué)規(guī)劃研究，（JB12288）

黃加增(1974-)，男，碩士研究生，研究方向?yàn)榇植诩c概念格。

本文著錄格式：黃加增. 基于復(fù)雜網(wǎng)絡(luò)異質(zhì)性的節(jié)點(diǎn)重要性評(píng)估方法[J]. 軟件，2017，38（4）：77-84