基于結(jié)構(gòu)洞指數(shù)的網(wǎng)絡(luò)節(jié)點(diǎn)重要度評(píng)估

張惠玲 張蒙

摘要：首先定義節(jié)點(diǎn)的限制度效率和等級(jí)度效率，由此構(gòu)建節(jié)點(diǎn)的重要性評(píng)價(jià)矩陣，從而提出一種利用節(jié)點(diǎn)間的結(jié)構(gòu)來(lái)判斷通信網(wǎng)中節(jié)點(diǎn)重要性的方法.該方法通過考慮三個(gè)節(jié)點(diǎn)之間的關(guān)系結(jié)構(gòu)來(lái)確定節(jié)點(diǎn)的重要性，克服單獨(dú)分析各個(gè)節(jié)點(diǎn)重要性的不足。最后，利用該算法對(duì)ARPA網(wǎng)的節(jié)點(diǎn)重要性進(jìn)行分析，并與已有的節(jié)點(diǎn)收縮法作對(duì)比。

關(guān)鍵詞：等級(jí)度效率；限制度效率；節(jié)點(diǎn)重要性

中圖分類號(hào)：TN915文獻(xiàn)標(biāo)識(shí)碼：A

1引言

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

上述方法都是通過單獨(dú)分析各個(gè)節(jié)點(diǎn)的方法來(lái)分析節(jié)點(diǎn)的重要性，但這并不能準(zhǔn)確分析節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中的重要性，因?yàn)楣?jié)點(diǎn)的重要性還與其結(jié)構(gòu)有關(guān)，而結(jié)構(gòu)洞理論恰好超出了兩個(gè)節(jié)點(diǎn)之間的“強(qiáng)弱”關(guān)系，更多的關(guān)注的是三個(gè)節(jié)點(diǎn)之間關(guān)系的“結(jié)構(gòu)”層面[10].

基于這種考慮，我們從節(jié)點(diǎn)的結(jié)構(gòu)出發(fā)，引用了結(jié)構(gòu)洞的概念，然后從計(jì)算結(jié)構(gòu)洞的兩個(gè)指標(biāo)（限制度和等級(jí)度）出發(fā)，定義了限制度效率和等級(jí)度效率，由此構(gòu)建了可判斷節(jié)點(diǎn)重要性的評(píng)價(jià)矩陣，提出了一種確定復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性的方法，給出了相應(yīng)的算法及其復(fù)雜性，最后對(duì)ARPA網(wǎng)的節(jié)點(diǎn)重要性進(jìn)行分析，驗(yàn)證了該方法的有效性。

2理論基礎(chǔ)

定義1[10]結(jié)構(gòu)洞是兩個(gè)行動(dòng)者之間的非冗余關(guān)系，例如，對(duì)于三個(gè)行動(dòng)者A，B，C來(lái)說，如果A和B關(guān)聯(lián)，B和C關(guān)聯(lián)，而A和C不關(guān)聯(lián)，此時(shí)稱A和C之間存在一個(gè)結(jié)構(gòu)洞。

結(jié)構(gòu)洞的計(jì)算可以通過伯特給出的結(jié)構(gòu)洞指數(shù)來(lái)測(cè)量.主要包括有效規(guī)模、效率、限制度以及等級(jí)度。

定義2[10]限制度指的是一個(gè)人在自己的網(wǎng)絡(luò)中擁有的運(yùn)用結(jié)構(gòu)洞的能力。

定義3[10]等級(jí)度指的是限制性在多大程度上集中在一個(gè)行動(dòng)者身上。

對(duì)于一個(gè)網(wǎng)絡(luò)圖，節(jié)點(diǎn)越居于網(wǎng)絡(luò)中心，它的結(jié)構(gòu)洞可能越多，受到的網(wǎng)絡(luò)限制度就越小，且等級(jí)度也越小。

計(jì)算技術(shù)與自動(dòng)化2016年3月

第35卷第1期張惠玲等：基于結(jié)構(gòu)洞指數(shù)的網(wǎng)絡(luò)節(jié)點(diǎn)重要度評(píng)估

3構(gòu)建模型

設(shè)圖G是有n個(gè)節(jié)點(diǎn)的簡(jiǎn)單圖，Cij表示節(jié)點(diǎn)j對(duì)節(jié)點(diǎn)i的限制度.Cij越大，表明節(jié)點(diǎn)j對(duì)節(jié)點(diǎn)i的限制性越大，即節(jié)點(diǎn)i對(duì)相鄰節(jié)點(diǎn)j的重要度貢獻(xiàn)越小.設(shè)Hi表示節(jié)點(diǎn)i的等級(jí)度，Hi越小，節(jié)點(diǎn)i越居于網(wǎng)絡(luò)核心。

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

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

定義5等級(jí)度效率.需要同時(shí)考慮節(jié)點(diǎn)自身在網(wǎng)絡(luò)中的重要性，提出了節(jié)點(diǎn)i的等級(jí)度效率Ki.定義如下：

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

于是由限制度效率和等級(jí)度效率構(gòu)建了判定節(jié)點(diǎn)重要性的評(píng)價(jià)矩陣：

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

根據(jù)節(jié)點(diǎn)重要性評(píng)價(jià)矩陣，綜合考慮節(jié)點(diǎn)自身的效率和相鄰節(jié)點(diǎn)的重要度，定義了節(jié)點(diǎn)i的重要度Ii.定義如下：

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

4節(jié)點(diǎn)重要性評(píng)價(jià)算法

下面給出節(jié)點(diǎn)重要性評(píng)估算法步驟：

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

輸出：節(jié)點(diǎn)i的重要度Ii.

Begin

步驟1計(jì)算結(jié)構(gòu)洞指標(biāo)限制度和等級(jí)度；

步驟2計(jì)算所有節(jié)點(diǎn)對(duì)的限制度效率Lij；

步驟3計(jì)算所有節(jié)點(diǎn)的等級(jí)度效率Ki；

步驟4確定節(jié)點(diǎn)重要度評(píng)價(jià)矩陣節(jié)M；

步驟5將評(píng)價(jià)矩陣M的第i行上的所有元素相加，得出節(jié)點(diǎn)i的重要度Ii.

End

5實(shí)例分析

下面利用圖1ARPA網(wǎng)絡(luò)拓?fù)涞墓?jié)點(diǎn)重要性評(píng)價(jià)算法進(jìn)行分析。它由21個(gè)節(jié)點(diǎn)和23條邊組成，大部分節(jié)點(diǎn)的度為2。

運(yùn)用本文的算法，計(jì)算網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)重要度，然后與文獻(xiàn)[3]和文獻(xiàn)[9]中相應(yīng)的結(jié)果作比較，結(jié)果見表1。

三種方法得出的節(jié)點(diǎn)的重要度排序結(jié)果有所差別，是因?yàn)楦髯耘袛嗟膫?cè)重點(diǎn)不同.本文考慮的是各個(gè)節(jié)點(diǎn)對(duì)其余節(jié)點(diǎn)的限制力和控制力，而文獻(xiàn)[3]考慮的是移除節(jié)點(diǎn)后相應(yīng)的生成樹數(shù)目的變化；文獻(xiàn)[9]考慮的是各個(gè)節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)信息傳輸?shù)呢暙I(xiàn).本文得出的最重要節(jié)點(diǎn)是v3，與文獻(xiàn)[3]的結(jié)論一致.并且v1和v4雖都是2度頂點(diǎn)，但它們的重要度并不相同，這也說明了節(jié)點(diǎn)的度數(shù)并不能完全決定節(jié)點(diǎn)的重要度。從表1中還可以看出，文獻(xiàn)[3]認(rèn)為節(jié)點(diǎn)v7至v11的重要度是一致的，而根據(jù)本文的算法可知，這5個(gè)節(jié)點(diǎn)的重要度是有區(qū)別的，這與文獻(xiàn)[9]的結(jié)論一致。endprint

6結(jié)論

評(píng)估通信網(wǎng)節(jié)點(diǎn)的重要性一直是復(fù)雜網(wǎng)絡(luò)中的一個(gè)熱點(diǎn)，本文通過計(jì)算結(jié)構(gòu)洞的兩個(gè)指標(biāo)等級(jí)度和限制度，定義了等級(jí)度效率和限制度效率，并由此構(gòu)建可判斷節(jié)點(diǎn)重要性的評(píng)價(jià)矩陣，提出了一種確定通信網(wǎng)節(jié)點(diǎn)重要性的方法.最后通過對(duì)ARPA網(wǎng)分析，表明該方法運(yùn)算量小，并能有效確定節(jié)點(diǎn)的重要性。

參考文獻(xiàn)

[1]任曉龍，呂琳媛.網(wǎng)絡(luò)重要節(jié)點(diǎn)排序方法綜述[J].科學(xué)通報(bào)，2014，59（13）：1175-1197.

[2]劉建國(guó)，任卓明，郭強(qiáng)，等.復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)重要性排序研究進(jìn)展[J].物理學(xué)報(bào)，2013，62（17）：178901（1-10）

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

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

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

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

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

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

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

[10]劉軍.整體網(wǎng)分析講義——UCINET軟件應(yīng)用[A].第二屆社會(huì)網(wǎng)與關(guān)系管理研討會(huì)[C].哈爾濱：哈爾濱工程大學(xué)社會(huì)學(xué)系.2007：194.

第35卷第1期2016年3月計(jì)算技術(shù)與自動(dòng)化ComputingTechnologyandAutomationVol35，No1Mar.2016第35卷第1期2016年3月計(jì)算技術(shù)與自動(dòng)化ComputingTechnologyandAutomationVol35，No1Mar.2016endprint