用于復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要度評(píng)估的離心率算法改進(jìn)研究

陸年生 嚴(yán)廣樂

摘 要：復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)重要度評(píng)估一直備受關(guān)注。鑒于離心率中心性只考慮節(jié)點(diǎn)最大最短路徑存在一定局限性，通過計(jì)算處理節(jié)點(diǎn)的平均最短路徑，考慮離心率數(shù)值與平均最短路徑的差值，提出改進(jìn)后的新方法。在具有代表性的APAR網(wǎng)絡(luò)上進(jìn)行計(jì)算實(shí)現(xiàn)，并與其它節(jié)點(diǎn)重要性評(píng)估方法進(jìn)行對(duì)比，發(fā)現(xiàn)該方法較離心率中心性方法，對(duì)于節(jié)點(diǎn)的粗略劃分更加精細(xì)、有效;在SI模型的模擬對(duì)照中，發(fā)現(xiàn)該方法在最終第10個(gè)單位時(shí)間時(shí)，準(zhǔn)確性相較于離心率中心性提升了15%。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò);離心率算法;節(jié)點(diǎn)重要度評(píng)估;最短路徑

0 引言

現(xiàn)實(shí)生活中的許多系統(tǒng)都可簡(jiǎn)化成網(wǎng)絡(luò)的形式加以研究[1]，例如交通網(wǎng)絡(luò)、電力網(wǎng)絡(luò)、科研網(wǎng)絡(luò)、交際網(wǎng)絡(luò)等。隨著復(fù)雜網(wǎng)絡(luò)研究的興起，節(jié)點(diǎn)重要性評(píng)估越來越受到國(guó)內(nèi)外學(xué)者的關(guān)注。復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)重要度評(píng)估十分重要，通過識(shí)別并保護(hù)這些節(jié)點(diǎn)，可有效提高網(wǎng)絡(luò)的魯棒性與可靠性[2]。例如，在交通網(wǎng)絡(luò)中，某一個(gè)交通樞紐城市因突發(fā)事件導(dǎo)致交通癱瘓，與該城市相鄰的其它城市交通也極有可能嚴(yán)重受阻，使得城市間的運(yùn)輸途徑中斷繼而引發(fā)大規(guī)模交通問題。研究發(fā)現(xiàn)，有效保護(hù)交通網(wǎng)絡(luò)中的重要節(jié)點(diǎn)，可以避免其在受到外界干擾時(shí)造成航線大面積延誤甚至導(dǎo)致網(wǎng)絡(luò)癱瘓，保證交通運(yùn)輸安全高效運(yùn)營(yíng)[3]。

最早的節(jié)點(diǎn)重要性評(píng)估方法其實(shí)就是度中心性[4]，度中心性將節(jié)點(diǎn)連接邊的數(shù)量作為節(jié)點(diǎn)重要性評(píng)估指標(biāo)?；诙刃畔ⅲ琋ewman等[5]研究了電子郵件網(wǎng)絡(luò)，Magoni[6]研究了英特網(wǎng)，Jeong等[7]研究了蛋白質(zhì)網(wǎng)絡(luò)。但是節(jié)點(diǎn)度僅反映節(jié)點(diǎn)自身信息，對(duì)于節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置及其對(duì)網(wǎng)絡(luò)全局的影響并沒有很好地描述。因此，F(xiàn)reeman[8]引入了介數(shù)的概念，介數(shù)中心性是以節(jié)點(diǎn)之間的最短路徑為基礎(chǔ)，計(jì)算經(jīng)過每個(gè)節(jié)點(diǎn)的最短路徑數(shù)量，但在復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)眾多、結(jié)構(gòu)復(fù)雜的情況下，該方法的時(shí)間復(fù)雜度較高。Per Hage等[9]提出了離心率中心性算法，將一節(jié)點(diǎn)距離其它所有節(jié)點(diǎn)的最短路徑中最長(zhǎng)的一條作為該節(jié)點(diǎn)重要度評(píng)估指標(biāo);Kitsak等[10]將度與節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置相結(jié)合，提出利用k-shell算法判斷節(jié)點(diǎn)重要性，該方法認(rèn)為ks值越大的節(jié)點(diǎn)越重要，但該指標(biāo)存在一定缺陷，在某些特定的復(fù)雜網(wǎng)絡(luò)中會(huì)出現(xiàn)多個(gè)節(jié)點(diǎn)ks值相同的情況;鄧凱旋等[11]對(duì)k-shell算法進(jìn)行了改進(jìn)，利用該算法分解過程中節(jié)點(diǎn)被刪除時(shí)的迭代層數(shù)，進(jìn)一步識(shí)別節(jié)點(diǎn)重要性，從而提出一種新的評(píng)價(jià)指標(biāo)EKsd。同樣是在k-shell算法基礎(chǔ)上，Liu等[12]考慮目標(biāo)節(jié)點(diǎn)與ks值最大的節(jié)點(diǎn)集之間的最短路徑，從而提出一種改進(jìn)的節(jié)點(diǎn)重要性排序方法;周漩等[13]提出通過定義節(jié)點(diǎn)效率和節(jié)點(diǎn)重要度評(píng)價(jià)矩陣確定復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)重要性，利用節(jié)點(diǎn)度值和效率值表征其對(duì)相鄰節(jié)點(diǎn)的重要度貢獻(xiàn)，該方法在大型網(wǎng)絡(luò)上表現(xiàn)較好;阮逸潤(rùn)[14]等在度和鄰居節(jié)點(diǎn)拓?fù)渲睾隙鹊幕A(chǔ)上，通過獲取節(jié)點(diǎn)二跳內(nèi)的鄰居信息計(jì)算節(jié)點(diǎn)重要性;韓忠明[15]等基于ListNet排序法并融合多個(gè)度量指標(biāo)，構(gòu)建了一個(gè)能夠綜合評(píng)價(jià)面向結(jié)構(gòu)洞節(jié)點(diǎn)的重要節(jié)點(diǎn)排序方法;王雨[16]等通過分析節(jié)點(diǎn)的局部重要性以及網(wǎng)絡(luò)中所有節(jié)點(diǎn)間的連接關(guān)系，提出一種基于多重影響力矩陣的節(jié)點(diǎn)重要性評(píng)估方法;汪宏[17]等基于標(biāo)簽傳播動(dòng)力學(xué)，將每個(gè)節(jié)點(diǎn)接收到不同標(biāo)簽的數(shù)量作為節(jié)點(diǎn)重要性評(píng)估指標(biāo)。此外，孔江濤[18]等基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型，建立偏離均值和基于偏離均值的方差兩級(jí)評(píng)估標(biāo)準(zhǔn)，進(jìn)而提出了兩種新的節(jié)點(diǎn)重要性評(píng)估方法。

綜上所述，每個(gè)節(jié)點(diǎn)重要性排序方法都有其針對(duì)性，雖然都能在一定程度上判斷出不同節(jié)點(diǎn)的重要性，但它們都存在一定的局限性。其中，離心率中心性方法對(duì)節(jié)點(diǎn)重要性識(shí)別較為準(zhǔn)確且較容易實(shí)現(xiàn)，但該方法也存在不足，以節(jié)點(diǎn)最短路徑最大值為指標(biāo)時(shí)，一些中心節(jié)點(diǎn)會(huì)因?yàn)榇嬖趥€(gè)別數(shù)值較大的最短路徑而被標(biāo)識(shí)為非重要節(jié)點(diǎn)，并且網(wǎng)絡(luò)中會(huì)出現(xiàn)部分節(jié)點(diǎn)離心率值相同的情況而無法對(duì)節(jié)點(diǎn)作出精確判斷。因此，只有對(duì)方法進(jìn)行一定程度的改進(jìn)，才能實(shí)現(xiàn)對(duì)節(jié)點(diǎn)重要度更為準(zhǔn)確的判斷。本文在最短路徑基礎(chǔ)上，對(duì)離心率中心性算法進(jìn)行改進(jìn)并將平均路徑加入方法中，該方法將節(jié)點(diǎn)全局屬性及網(wǎng)絡(luò)位置考慮進(jìn)去，相較于離心率方法能夠更有效地對(duì)復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)重要度進(jìn)行排序。

3 結(jié)語

節(jié)點(diǎn)重要度評(píng)估一直是復(fù)雜網(wǎng)絡(luò)中的研究熱點(diǎn)，其在實(shí)際應(yīng)用中具有重要意義。本文通過改進(jìn)離心率中心性算法，構(gòu)建評(píng)估節(jié)點(diǎn)重要性的新方法re（i），該方法引入了節(jié)點(diǎn)的平均最短路徑并對(duì)其進(jìn)行了簡(jiǎn)單處理，使其在節(jié)點(diǎn)重要性判斷中能充分利用節(jié)點(diǎn)的全局屬性，利用差值誤差提高評(píng)估結(jié)果的準(zhǔn)確性。實(shí)際網(wǎng)絡(luò)APAR網(wǎng)的研究結(jié)果發(fā)現(xiàn)，本文方法與其它典型節(jié)點(diǎn)重要性判定指標(biāo)，如度中心性方法、Pagerank算法的部分結(jié)果相同或相似，側(cè)面說明了本文方法的合理性與有效性，并且對(duì)于離心率算法判斷模糊的節(jié)點(diǎn)也能夠更好地區(qū)分開來。最后在SI模型中，兩個(gè)不同節(jié)點(diǎn)的對(duì)照實(shí)驗(yàn)也證明了本文方法在重要節(jié)點(diǎn)的判定上，相較于離心率中心性算法準(zhǔn)確性有所提升。由于本文方法是基于節(jié)點(diǎn)的全局屬性，在節(jié)點(diǎn)局部結(jié)構(gòu)較為復(fù)雜的網(wǎng)絡(luò)中，其評(píng)估準(zhǔn)確性可能會(huì)有所降低。后續(xù)將繼續(xù)研究網(wǎng)絡(luò)節(jié)點(diǎn)的局部屬性并與之結(jié)合，進(jìn)一步增強(qiáng)節(jié)點(diǎn)重要性評(píng)估效果。

參考文獻(xiàn)：

[1] BARABASI A L. Scale-free networks： a decade and beyond[J]. Science， 2009， 325（5939）： 412-415.

[2] 譚躍進(jìn)，吳俊，鄧宏鐘， 等. 復(fù)雜網(wǎng)絡(luò)抗毀性研究綜述[J]. 系統(tǒng)工程， 2006，24（10）： 1-5.

[3] 任卓明，邵鳳，劉建國(guó)，等. 基于度與集聚系數(shù)的網(wǎng)絡(luò)節(jié)點(diǎn)重要性度量方法研究[J]. 物理學(xué)報(bào)， 2013， 62（12）： 1-4.

[4] PHILLIP BONACICH. Power and centrality： a family of measures[J].? American Journal of Sociology， 1987， 92（5）：1170-1182.

[5] NEWMAN M E J， FORREST S， BALTHROP A. Email networks and the spread of computer viruses[J]. Physical Review，2002，66（3）： 035101.

[6] DAMIEN MAGONI. Tearing down the Internet[J].? IEEE Journal on Selected Areas in Communications， 2003， 21（6）： 949-960.

[7] JEONG H，MASON S，BARABASI A L. Lethality and centrality in protein networks[J]. Nature，2001， 411（6883）： 41-43.

[8] FREEMAN L. A set of measures of centrality based upon betweenness[J].? Sociometry，1977， 40（1）： 35-41.

[9] PER HAGE， FRANK HARARY. Eccentricity and centrality in networks[J]. Social Networks，1995，17（1）：57-63.

[10] KITSAK M， GAILOS L K. HAVLIN S， et al. Identification of influential spreaders in complex networks[J].? Nature Physics， 2010（6）：888-893.

[11] 鄧凱旋，陳鴻昶，黃瑞陽. 一種基于改進(jìn)K-shell的節(jié)點(diǎn)重要性排序方法[J]. 計(jì)算機(jī)應(yīng)用研究， 2017， 34（10）： 3017-3019， 3084.

[12] LIU J G， REN Z M， GUO Q. Ranking the spreading influence in complex networks[J].? Physica A， 2013， 392（18）：4154-4159.

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

[14] 阮逸潤(rùn)，老松楊，王竣德，等. 基于領(lǐng)域相似度的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要度評(píng)估算法[J]. 物理學(xué)報(bào)， 2017， 66（3）： 1-8.

[15] 韓忠明，吳楊，譚旭升，等. 面向結(jié)構(gòu)洞的復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)排序[J].? 物理學(xué)報(bào)，2015， 64（5）： 1-8.

[16] 王雨， 郭進(jìn)利. 基于多重影響力矩陣的有向加權(quán)網(wǎng)絡(luò)節(jié)點(diǎn)重要性評(píng)估方法[J]. 物理學(xué)報(bào)，2017， 66（5）： 1-11.

[17] 汪宏，鮑中奎，張海峰. 基于標(biāo)簽傳播識(shí)別網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)[J].? 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2017，14（2）： 19-25.

[18] 孔江濤，黃健，龔建興，等. 基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的無向加權(quán)網(wǎng)絡(luò)節(jié)點(diǎn)重要性評(píng)估[J]. 物理學(xué)報(bào)， 2018， 67（9）： 1-16.

[19] 馬睿，朱建沖，楊美玲. 基于抗毀性的軍事通信網(wǎng)可靠性和節(jié)點(diǎn)重要性分析[J]. 兵工自動(dòng)化，2012， 31（10）： 46-47.

[20] 張翼，劉玉華，許凱華，等. 一種基于互信息的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性評(píng)估方法[J].? 計(jì)算機(jī)科學(xué)，2011，38（6）：88-89，109.

（責(zé)任編輯：孫 娟）