基于結構洞指數的網絡節點重要度評估

張惠玲 張蒙

摘要：首先定義節點的限制度效率和等級度效率，由此構建節點的重要性評價矩陣，從而提出一種利用節點間的結構來判斷通信網中節點重要性的方法.該方法通過考慮三個節點之間的關系結構來確定節點的重要性，克服單獨分析各個節點重要性的不足。最后，利用該算法對ARPA網的節點重要性進行分析，并與已有的節點收縮法作對比。

關鍵詞：等級度效率；限制度效率；節點重要性

中圖分類號：TN915文獻標識碼：A

1引言

在通信網的設計和維護中，可靠性是網絡運行質量的一個重要指標，這一問題已經引起了人們的重視[1-2].在對網絡的可靠性研究中，利用節點的某一屬性評估節點的重要性是一種常見方法.例如將圖論中度、最短路徑、最小生成樹等概念結合實際問題的背景給出判斷節點重要性的判定方法，如：在文獻[3]中，定義最重要的節點是該節點在失效的情況下，相應的生成樹數目最小的節點記為最重要節點.在文獻[4]中，通過最短路徑結束的方法確定網絡中的重要性節點.文獻[5]利用節點收縮的方法，通過刪除待分析節點的鄰接點來判斷節點的重要度，該方法簡化了計算的復雜度，但沒有考慮節點刪除后會導致網絡結構變化，從而引起節點重要性的變化。文獻[6]提出了基于網絡性能梯度的節點重要性評價方法。文獻[7]克服了節點刪除法、節點收縮法的弊端，將各個節點聯系起來，從分析節點對網絡資源的控制能力的角度，構造重要度貢獻矩陣來比較節點的重要性.然而文獻[8]認為這些傳統評價方法僅考慮了節點的某一屬性，應將多個屬性綜合考慮，于是提出了一種多因子評價方法。

上述方法都是通過單獨分析各個節點的方法來分析節點的重要性，但這并不能準確分析節點在整個網絡中的重要性，因為節點的重要性還與其結構有關，而結構洞理論恰好超出了兩個節點之間的“強弱”關系，更多的關注的是三個節點之間關系的“結構”層面[10].

基于這種考慮，我們從節點的結構出發，引用了結構洞的概念，然后從計算結構洞的兩個指標（限制度和等級度）出發，定義了限制度效率和等級度效率，由此構建了可判斷節點重要性的評價矩陣，提出了一種確定復雜網絡節點重要性的方法，給出了相應的算法及其復雜性，最后對ARPA網的節點重要性進行分析，驗證了該方法的有效性。

2理論基礎

定義1[10]結構洞是兩個行動者之間的非冗余關系，例如，對于三個行動者A，B，C來說，如果A和B關聯，B和C關聯，而A和C不關聯，此時稱A和C之間存在一個結構洞。

結構洞的計算可以通過伯特給出的結構洞指數來測量.主要包括有效規模、效率、限制度以及等級度。

定義2[10]限制度指的是一個人在自己的網絡中擁有的運用結構洞的能力。

定義3[10]等級度指的是限制性在多大程度上集中在一個行動者身上。

對于一個網絡圖，節點越居于網絡中心，它的結構洞可能越多，受到的網絡限制度就越小，且等級度也越小。

計算技術與自動化2016年3月

第35卷第1期張惠玲等：基于結構洞指數的網絡節點重要度評估

3構建模型

設圖G是有n個節點的簡單圖，Cij表示節點j對節點i的限制度.Cij越大，表明節點j對節點i的限制性越大，即節點i對相鄰節點j的重要度貢獻越小.設Hi表示節點i的等級度，Hi越小，節點i越居于網絡核心。

定義4限制度效率.由于網絡是由節點和邊組成，因此與節點距離為1的相鄰節點提供的信息最多.為了考慮節點的局部重要性，提出了節點i對相鄰節點j的限制度效率Lij.定義如下：

Lij=1-Cij∑nj=1Cij（1）

定義5等級度效率.需要同時考慮節點自身在網絡中的重要性，提出了節點i的等級度效率Ki.定義如下：

Ki=1-Hi∑ni=1Hi（2）

于是由限制度效率和等級度效率構建了判定節點重要性的評價矩陣：

M=K1L12…L1nL21K2…L2nLn1Ln2…Kn（3）

根據節點重要性評價矩陣，綜合考慮節點自身的效率和相鄰節點的重要度，定義了節點i的重要度Ii.定義如下：

Ii=∑nj=1Mij=Ki+∑nj=1Lij（4）

4節點重要性評價算法

下面給出節點重要性評估算法步驟：

輸入：鄰接矩陣（mij）n×m.

輸出：節點i的重要度Ii.

Begin

步驟1計算結構洞指標限制度和等級度；

步驟2計算所有節點對的限制度效率Lij；

步驟3計算所有節點的等級度效率Ki；

步驟4確定節點重要度評價矩陣節M；

步驟5將評價矩陣M的第i行上的所有元素相加，得出節點i的重要度Ii.

End

5實例分析

下面利用圖1ARPA網絡拓撲的節點重要性評價算法進行分析。它由21個節點和23條邊組成，大部分節點的度為2。

運用本文的算法，計算網絡中各個節點重要度，然后與文獻[3]和文獻[9]中相應的結果作比較，結果見表1。

三種方法得出的節點的重要度排序結果有所差別，是因為各自判斷的側重點不同.本文考慮的是各個節點對其余節點的限制力和控制力，而文獻[3]考慮的是移除節點后相應的生成樹數目的變化；文獻[9]考慮的是各個節點對網絡信息傳輸的貢獻.本文得出的最重要節點是v3，與文獻[3]的結論一致.并且v1和v4雖都是2度頂點，但它們的重要度并不相同，這也說明了節點的度數并不能完全決定節點的重要度。從表1中還可以看出，文獻[3]認為節點v7至v11的重要度是一致的，而根據本文的算法可知，這5個節點的重要度是有區別的，這與文獻[9]的結論一致。endprint

6結論

評估通信網節點的重要性一直是復雜網絡中的一個熱點，本文通過計算結構洞的兩個指標等級度和限制度，定義了等級度效率和限制度效率，并由此構建可判斷節點重要性的評價矩陣，提出了一種確定通信網節點重要性的方法.最后通過對ARPA網分析，表明該方法運算量小，并能有效確定節點的重要性。

參考文獻

[1]任曉龍，呂琳媛.網絡重要節點排序方法綜述[J].科學通報，2014，59（13）：1175-1197.

[2]劉建國，任卓明，郭強，等.復雜網絡中節點重要性排序研究進展[J].物理學報，2013，62（17）：178901（1-10）

[3]陳勇，胡愛群，胡嘯.通信網中節點重要性的評價方法[J].通信學報，2004，25（8）：129-131.

[4]張珍，張振宇，宋蔓蔓.一種基于最短路徑結束的重要節點發現算法[J].計算機工程與應用，2013，49（21）：98-100，132.

[5]譚躍進，吳俊，鄧宏鐘.復雜網絡中節點重要度評估的節點收縮方法[J].系統工程理論與實踐，2006，26（11）：79-83.

[6]余新，李艷和，鄭小平，等.基于網絡性能變化梯度的通信網絡節點重要程度評價方法[J].清華大學學報：自然科學版，2008，48（4）：541-544.

[7]趙毅寰，王祖林，鄭晶，等.利用重要性貢獻矩陣確定通信網中最重要節點[J].北京航空航天大學學報，2009，35（9）：1076-1079.

[8]于會，劉尊，李勇軍.基于多屬性決策的復雜網絡節點重要性綜合評價方法[J].物理學報，2013，62（2）：020204.

[9]周漩，張鳳鳴，李克武，等.利用重要度評價矩陣確定復雜網絡關鍵節點[J].物理學報，2012，61（5）：050201.

[10]劉軍.整體網分析講義——UCINET軟件應用[A].第二屆社會網與關系管理研討會[C].哈爾濱：哈爾濱工程大學社會學系.2007：194.

第35卷第1期2016年3月計算技術與自動化ComputingTechnologyandAutomationVol35，No1Mar.2016第35卷第1期2016年3月計算技術與自動化ComputingTechnologyandAutomationVol35，No1Mar.2016endprint