• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

    2016-04-11 01:50:06張惠玲張蒙

    張惠玲 張蒙

    摘要:首先定義節(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

    娄底市| 潮州市| 资溪县| 澎湖县| 安顺市| 息烽县| 东平县| 万州区| 隆子县| 襄樊市| 喀什市| 三门峡市| 明水县| 延安市| 温泉县| 于都县| 塔城市| 唐山市| 穆棱市| 隆化县| 滁州市| 唐河县| 天水市| 鹰潭市| 潮安县| 永昌县| 襄樊市| 且末县| 左贡县| 静海县| 遂溪县| 仁怀市| 闽清县| 黄石市| 那坡县| 故城县| 鹤庆县| 缙云县| 尼勒克县| 阿瓦提县| 河间市|