基于復雜網絡異質性的節點重要性評估方法

黃加增

?

基于復雜網絡異質性的節點重要性評估方法

黃加增

（福建農林大學東方學院，福建福州 350017）

對于復雜網絡的結構特殊性，用加權拓撲熵為理論基礎，提出了基于復雜網絡結構異質性變化率的節點重要程度評估方法。首先，本文給出了復雜網絡加權拓撲熵的概念，闡述了基于BBV網絡的反向演化原理，其次，在反向演化原理的基礎上提出了節點重要程度取決于網絡結構異質性變化率的觀點，并提出了網絡割點的異質性變化率的計算方法；最后，以一個例子來說明節點重要程度的評估過程，并對特殊節點進行了處理分析。

復雜網絡，加權網絡，加權拓撲熵，異質性變化率，節點重要程度評估

0 引言

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

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

目前大部分的網絡都是加權網絡（Weighted Network），網絡中的每條邊用來說明連接兩個節點之間是否存在，而且還顯示了這種連接的某種特性（如流量的大小）；當然，每個節點在網絡中也扮演著不同角色，具有不完全相同的屬性和能力。無論是技術網絡方面的公共交通道路網絡、Internet網絡，還是科學家合作網絡、引文網絡等社會網絡，都在不同的側面顯示出其加權網絡的特性[15-17]。

對于上述兩種研究方法，針對加權網絡，通過引入能夠表征全局狀態的熵及其熵變理論，提出了以網絡加權拓撲熵的變化量作為節點重要程度的觀點。一方面，以加權網絡中的邊權和節點強度等屬性不僅可以表明節點在網絡中的不同位置和連接特性，而且還可以充分體現某些處于網絡邊緣的關鍵節點（如計算機網絡中的網關、服務器等節點）的重要性；另一方面，通過能體現網絡整體狀態的熵的變遷衡量不同節點被刪除后對網絡所產生的破壞程度。

1 網絡加權拓撲熵

在信息論中，申農（Claude E. Shannon）將信息熵定義為離散隨機事件的出現概率，或者說是信息熵是消除不確定性的一種度量。仿照信息熵的定義，譚躍進等人提出了網絡結構熵的概念，并將其引入到網絡異質性的研究中。在文獻[18]中，譚躍進將無標度網絡的網絡結構熵定義為，其中：，為節點的度。這個定義的基本假設是：網絡節點的重要程度完全由這個節點的度所決定。

由于上述假設的缺陷，以及上述定義無法描述加權復雜網絡的拓撲狀況，本文提出了能夠描述加權復雜網絡異質性的定義：

和一般意義上的熵一樣，網絡加權拓撲熵也具有極值，即當網絡結構完全均勻時，網絡加權拓撲熵達到其極值。可以很方便地證明這個極值的存在：

首先，當網絡完全均勻時，所有的邊權都會取同樣的權、所有的節點都具有相同的節點強度。事實上，這時的網絡加權拓撲熵已經和譚躍進教授的網絡結構熵沒有任何區別。

因此，在網絡完全均勻時網絡加權拓撲熵取的極值為：

2 加權網絡的演化

2.1 節點加入網絡時的演化

以BBV加權網絡為例，當某個節點加入網絡并與若干個節點相連時，相關邊權和節點強度按照下列方式進行演化：

即節點強度越大被選中的可能性也越大。

（3）

（5）

2.2 節點退出網絡時的演化

在BBV加權網絡中，當某個節點退出網絡時，網絡中邊的權重和節點的強度都會發生演化，也就是說這種演化同樣會發生在有節點退出的相關局域網絡中。

（7）

（8）

（10）

簡單證明如下：

3 網絡異質性變化率與節點重要性評估

網絡加權拓撲熵表征了加權網絡拓撲結構的異質性，是一種能夠描述加權網絡整體狀態的指標。只要網絡結構發生改變，網絡加權拓撲熵也會隨之發生改變。

對于加權網絡而言，當某個節點退出網絡后，網絡中相關的邊權和節點強度都會發生變化，從而導致網絡異質度也隨之發生變化。因此，我們可以通過網絡異質度的變化率來判斷不同節點在網絡中的重要性。

在網絡中，可能會存在一些稱為“割點”（cut vertex）的特殊節點，一旦這種節點退出網絡后，則網絡會被分割成若干個獨立的連通子網。

根據反向演化原理，具有較大強度的節點退出網絡時，不僅僅是網絡節點的減少，而且也導致原來由退出節點所承擔的負荷被分配到其它節點上，從而使得網絡的異質性發生改變。

根據加權拓撲熵的變化，當某節點退出網絡時，網絡異質性有以下演化特性：

（1）節點的度越大，該節點的退出對網絡的異質性影響就越大；

（2）與節點直接相連邊的權越大，該節點的退出對網絡的異質性影響就越大；

（3）分攤了來自于別的節點的負荷越大，該節點的退出對網絡的異質性影響就越大。

因此，可以將不同節點退出前后的網絡異質性變化率作為評估這些節點在網絡中的重要程度的依據。

4 舉例與分析

下面以一個示例對本文提出的節點重要程度評估方法加以說明：

圖1是一個加權網絡的拓撲圖，分別用基于異質度的變化率和基于節點度的方法進行節點重要性的評估。

圖1 一個加權網絡的拓撲圖

假設該網絡共有17個節點，各邊的權值分別如圖所示。表1是根據該網絡的結構和邊權所計算的結果：

表1 初始計算結果

Tab.1 Initial results

下面分別計算不同節點退出網絡后，加權熵及其相關參數的變化情況。盡管任何一個節點退出后，對于連通網絡內的各個節點的強度和邊權都會產生影響，在這里僅考慮與退出節點有直接連接的節點及其相關邊所發生的變化。

4.1 節點1退出網絡時

表2 節點1退出網絡后的各參數變化

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

根據表2，節點1退出網絡后，網絡拓撲經過演化，其加權拓撲熵為：。

圖2 節點1退出后網絡的加權拓撲結構

同理，節點2、節點3、節點4、節點14、節點15、節點16和節點17等分別退出網絡后，網絡加權拓撲熵也同為2.381。

4.2 節點5退出網絡時

與節點5有直接連邊的節點分別為節點1、節點2、節點3、節點4和節點7。其中前4個節點除了與節點5有連接外，還與節點6有連接；而節點7則還與節點6、節點8和節點9有連接。節點5的退出，使得原來由節點5承擔的負荷都要被轉嫁到節點6上。

表3 節點5退出網絡后的各參數變化

根據表3，節點5退出網絡后，網絡拓撲經過演化，其加權拓撲熵為：。

圖3 節點5退出后網絡的加權拓撲結構

同理，節點6、節點12和節點13等分別退出網絡后，網絡加權拓撲熵也同為2.3082。

4.3 節點7退出網絡時

與節點7有直接連邊的節點分別為節點5、節點6、節點8和節點9。節點7的退出，導致網絡分為兩個連通分支，網絡結構發生重大變化。其中，第一個連通分支由節點1~節點6組成，共有6個節點；第二個連通分支由節點8~節點17組成，共有10個節點。

表4 節點7退出第一個連通分支的各參數變化

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

表5 節點7退出第二個連通分支的各參數變化

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

圖4 節點7退出后網絡的加權拓撲結構

同理，節點11退出網絡后，網絡加權拓撲熵也為1.8496。

4.4 節點8退出網絡時

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

表6 節點8退出網絡后的各參數變化

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

根據表6，節點8退出網絡后，網絡拓撲經過演化，其加權拓撲熵為：。

圖5 節點8退出后網絡的加權拓撲結構

4.5 節點9退出網絡時

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

表7 節點9退出網絡后的各參數變化

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

根據表7，節點9退出網絡后，網絡拓撲經過演化，其加權拓撲熵為：。

圖6 節點9退出后網絡的加權拓撲結構

同理，節點10退出網絡后，網絡加權拓撲熵也為2.3121。

4.6 對比與分析

通過對加權拓撲熵的計算，可以看到：不同節點的退出對網絡的異質性所帶來的影響各不相同，特別是割點的退出對網絡的異質性影響尤為重大。表8描述了網絡異質性變化率與節點度兩種不同的節點重要程度評估方法的對比。

表8 異質性變化率與節點度對比表

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

從表中可以看到：

根據節點度方法的重要程度評估中，節點5、節點6、節點12和節點13為最重要的節點，因為這幾個節點的度最大；而根據異質性變化率進行的評估則認為節點7和節點11的重要程度最高，因為這兩個節點所到導致的異質性變化率最高。從實際來看，這樣的結論也是合理的，因為節點7和節點11都是網絡的割點，不論是節點7還是節點11，只要退出網絡，則都會導致網絡連通性的破壞，而且所形成的兩個連通分支都具有較大的規模。

比較有意思的是節點8、節點9和節點10之間的重要程度排序。由于節點9和節點10是對稱關系，所以這里只討論節點8與節點9的重要程度排序：

● 當節點8的節點強度小于節點9時，節點9的重要程度就大于節點8；

● 當節點8的節點強度大于節點9的節點強度，但不超過2倍時，節點9的重要程度就大于節點8；

● 當節點8的節點強度達到節點9的節點強度2倍時，節點8的重要程度就大于節點9。

除此而外，基于網絡異質性變化率的節點重要程度評估方法還具有劃分層次更加豐富的特性。如上述例子中，根據節點度的方法只劃分了3個層次的重要程度，而根據異質性變化率的方法則劃分出了5個不同的層次。豐富的層次可以為網絡的管理和維護提供更加可信的依據。

5 總結

熵是一個能夠反映系統整體狀態及其演化的指標。本文從整體觀點進行網絡節點重要程度評估方法的研究，并在BBV網絡的基礎上，提出了基于網絡異質性變化率的評估方法。該方法具有以下一些特點：

（1）以網絡拓撲結構的演化研究各節點在網絡中所發揮的作用，具有整體的視點，克服了諸如節點度方法等的局部觀點所固有的缺陷。

（2）通過邊權和節點強度計算，可以實時的反應節點重要程度的動態變化。

（3）采用影響因子的方式解決了多個連通分支時的異質性變化率的計算問題。

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

總之，異質性變化率的評估方法為網絡脆弱性的研究，并且能夠為日常的網絡管理、維護和安全防范等都提供重要的依據。

[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] 于會, 劉尊, 李勇軍. 基于多屬性決策的復雜網絡節點重要性綜合評價方法[J]. 物理學報, 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] 胡平, 王文, 劉志華. 綜合節點異質性、刪除及DPA的網絡演化模型[J]. 管理科學學報, 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] 席酉民, 唐方成. 組織的立體多核網絡模型研究[J]. 西安交通大學學報, 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] 李振華, 陳貴海, 邱彤慶. 分點: 無結構對等網絡的拓撲關鍵點[J]. 軟件學報, 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] 郝彬彬, 井元偉, 張嗣瀛. 復雜網絡度分布的異質性對其同步能力的影響[J]. 東北大學學報: 自然科學版, 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] 王班, 馬潤年, 王剛, 陳波. 改進的加權網絡節點重要性評估的互信息方法[J]. 計算機應用, 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] 朱鵬鵬, 董建民, 李慧嘉. 節點重要性指標在加權網絡中的應用[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]. 系統工程理論與實踐, 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

基于粗糙概念格對城市交通科學規劃研究，（JB12288）

黃加增(1974-)，男，碩士研究生，研究方向為粗糙集與概念格。

本文著錄格式：黃加增. 基于復雜網絡異質性的節點重要性評估方法[J]. 軟件，2017，38（4）：77-84