基于平衡系數(shù)的加權(quán)網(wǎng)絡(luò)改進(jìn)k核算法

王 棹,張曦煌

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院,江蘇 無錫 214000)

0 概述

復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性研究是復(fù)雜網(wǎng)絡(luò)理論中十分重要的部分,對不同網(wǎng)絡(luò)的研究已經(jīng)發(fā)展出很多新的理論[1-3]。這些相關(guān)理論已應(yīng)用到社交網(wǎng)絡(luò)[4]、傳播網(wǎng)絡(luò)[5]、計(jì)算機(jī)網(wǎng)絡(luò)[6]等各種網(wǎng)絡(luò)的分析中,并取得了科學(xué)的可靠的結(jié)果。由于復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)目十分巨大,一個網(wǎng)絡(luò)中有成百上千個甚至數(shù)十萬個網(wǎng)絡(luò)節(jié)點(diǎn),如何高效準(zhǔn)確地識別出其中的重要節(jié)點(diǎn)變得十分困難,這些關(guān)鍵的節(jié)點(diǎn)處于網(wǎng)絡(luò)中十分重要的位置,對整個網(wǎng)絡(luò)的抗毀性[7-8]有至關(guān)重要的作用。

目前,在復(fù)雜網(wǎng)絡(luò)理論中節(jié)點(diǎn)重要性的評價方法主要有節(jié)點(diǎn)度[9]、網(wǎng)絡(luò)介數(shù)[10]、接近中心和PankRank[11]。節(jié)點(diǎn)度只反映了節(jié)點(diǎn)在網(wǎng)絡(luò)局部的重要性。介數(shù)和接近中心算法從網(wǎng)絡(luò)全局角度出發(fā),對節(jié)點(diǎn)在網(wǎng)絡(luò)中所處的位置給出了較為準(zhǔn)確的節(jié)點(diǎn)重要性評價,但是由于它們都需要計(jì)算所有節(jié)點(diǎn)到其他網(wǎng)絡(luò)節(jié)點(diǎn)的最短路徑[12],因此算法復(fù)雜度非常高。文獻(xiàn)[13]提出了基于節(jié)點(diǎn)重要度貢獻(xiàn)的節(jié)點(diǎn)重要性算法,給出了基于m階鄰居節(jié)點(diǎn)重要度貢獻(xiàn)的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要度計(jì)算方法,該算法取得了較好的實(shí)驗(yàn)結(jié)果,但不適用于加權(quán)網(wǎng)絡(luò)。文獻(xiàn)[14]在文獻(xiàn)[12]的基礎(chǔ)上提出了適用于加權(quán)網(wǎng)絡(luò)的節(jié)點(diǎn)重要度改進(jìn)算法,但由于算法復(fù)雜度高,因此不適合用來分析大型網(wǎng)絡(luò)。PankRank算法是由谷歌公司提出的基于隨機(jī)游走的網(wǎng)頁重要性排序算法,該算法主要應(yīng)用在互聯(lián)網(wǎng)領(lǐng)域,且不適合用來分析加權(quán)網(wǎng)絡(luò)。文獻(xiàn)[15-16]提出了k核算法,認(rèn)為網(wǎng)絡(luò)傳播動力學(xué)中最重要的節(jié)點(diǎn)并非傳統(tǒng)的度最大或介數(shù)最大的 Hub 節(jié)點(diǎn),而是具有最大k核值的節(jié)點(diǎn)。該算法從網(wǎng)絡(luò)整體布局的角度提出了節(jié)點(diǎn)重要性的評價方法,具有較低的算法復(fù)雜度,能快速地給出超大型網(wǎng)絡(luò)的節(jié)點(diǎn)重要性評價參數(shù)。但該算法同樣只適用于無權(quán)網(wǎng)絡(luò)。

針對以上算法的問題,本文在k核算法的基礎(chǔ)上,提出基于平衡系數(shù)的復(fù)雜加權(quán)網(wǎng)絡(luò)改進(jìn)k核算法。該算法引入權(quán)重值重新定義了更適用于加權(quán)網(wǎng)絡(luò)的節(jié)點(diǎn)k核值指標(biāo)。將權(quán)重值對評價結(jié)果的影響定量化,并調(diào)整平衡系數(shù)以適應(yīng)不同網(wǎng)絡(luò)的特點(diǎn)。

1 復(fù)雜網(wǎng)絡(luò)

1.1 接近中心算法

節(jié)點(diǎn)的接近中心是它到其他所有節(jié)點(diǎn)的最短距離之和的倒數(shù),表達(dá)式為:

(1)

其中,N是節(jié)點(diǎn)總數(shù),kij是從節(jié)點(diǎn)vi到節(jié)點(diǎn)vj的最短路徑長度。CC值越大,則節(jié)點(diǎn)在全局網(wǎng)絡(luò)中居于中心位置的程度也越大。

1.2 k核算法

k核算法通過遞歸地移去網(wǎng)絡(luò)中所有度值小于或等于k的節(jié)點(diǎn)來描述網(wǎng)絡(luò)結(jié)構(gòu)特征,揭示網(wǎng)絡(luò)層次性質(zhì)。

假設(shè)網(wǎng)絡(luò)G=(V,E) 是由|V|=N個節(jié)點(diǎn)和|E|=E條邊所組成的一個無向網(wǎng)絡(luò),則k核的定義如下:由集合推導(dǎo)出的子網(wǎng)絡(luò)H=(C,E|C),當(dāng)且僅當(dāng)對C中的任意節(jié)點(diǎn)V,其度值均大于k,具有這一性質(zhì)的最大子網(wǎng)絡(luò)的補(bǔ)集被稱為k-核,簡稱Ks,其分解示意圖如圖1所示。

圖1 k核算法分解示意圖

該網(wǎng)絡(luò)被劃分為3層不同的核:最外層的節(jié)點(diǎn)k核值為1,它們處于整個網(wǎng)絡(luò)的邊緣,對網(wǎng)絡(luò)的影響較小。中間層的節(jié)點(diǎn)k核值為2,最里層的節(jié)點(diǎn)k核值為3,它們是處于網(wǎng)絡(luò)中心的節(jié)點(diǎn),對整個網(wǎng)絡(luò)的連通性和完整性有巨大的影響。但是由于k核算法只注重于尋找網(wǎng)絡(luò)中最關(guān)鍵的節(jié)點(diǎn),因此在k核分析中存在大量k核值相同的節(jié)點(diǎn)。例如圖中的節(jié)點(diǎn)1～節(jié)點(diǎn)12的k核值均為1。這也是k核算法的不足之處。

1.3 基于平衡系數(shù)的改進(jìn)k核算法

1.3.1 基本思路

在Kitsak 等人的研究基礎(chǔ)上,本文提出一種針對復(fù)雜加權(quán)網(wǎng)絡(luò)的k核改進(jìn)算法。在加權(quán)網(wǎng)絡(luò)中節(jié)點(diǎn)的度k′和k″定義如下:

(2)

(3)

其中,ki表示節(jié)點(diǎn)i的度,wij表示與節(jié)點(diǎn)i相連的邊的權(quán)重。α和β是在改進(jìn)k核算法中加入的2個調(diào)整參數(shù),用來調(diào)節(jié)節(jié)點(diǎn)的k核值和連邊權(quán)重值對改進(jìn)k核值的影響程度。在選擇α和β的值時,要有一定的科學(xué)依據(jù),合理地選擇這2個值,才能使算法得出的結(jié)果具有與實(shí)際情況相符的科學(xué)性。當(dāng)α和β的取值發(fā)生變化時,反映加權(quán)網(wǎng)絡(luò)節(jié)點(diǎn)重要性的k′核值相應(yīng)地也隨之變化。因此,本文定義了k″值,從該值的定義中可以看出,無論k′如何變化,k″都能用來定量衡量每個節(jié)點(diǎn)的重要性在整個網(wǎng)絡(luò)中的定位,其值類似于反映一個數(shù)值在所有數(shù)值中所占有的百分比。因此,在實(shí)際網(wǎng)絡(luò)分析中,當(dāng)α和β的取值變動時,可以用k″來準(zhǔn)確地反映節(jié)點(diǎn)重要性的變化情況。

為了確定α和β的取值關(guān)系,本文定義了平衡系數(shù)E這一概念,其定義如下:

(4)

其中,k表示網(wǎng)絡(luò)中節(jié)點(diǎn)的k核值,wij表示網(wǎng)絡(luò)中節(jié)點(diǎn)的連邊權(quán)重值之和。通過計(jì)算網(wǎng)絡(luò)中這2個值的總和和合理地設(shè)置平衡系數(shù),能科學(xué)地確定k核值和連邊權(quán)重在節(jié)點(diǎn)重要性評價參數(shù)中的權(quán)重。在不同的網(wǎng)絡(luò)中,可以根據(jù)實(shí)際網(wǎng)絡(luò)的情況調(diào)整這一系數(shù)。例如在城市路網(wǎng)建設(shè)規(guī)劃時,節(jié)點(diǎn)連邊的權(quán)重值即車流量應(yīng)不超過道路設(shè)計(jì)的最大承載量,各節(jié)點(diǎn)的度值一般不超過4。在分析水網(wǎng)情況時,連邊權(quán)重值也應(yīng)考慮到該河流的最大泄洪能力。在本文實(shí)驗(yàn)中,平衡系數(shù)的取值將會多樣化,用以分析該系數(shù)對最終實(shí)驗(yàn)結(jié)果的影響。當(dāng)E=1時:

(5)

經(jīng)過平衡系數(shù)調(diào)整之后的權(quán)重值為:

(6)

在調(diào)整之后的網(wǎng)絡(luò)中,網(wǎng)絡(luò)所有節(jié)點(diǎn)的度值與所有連邊之間的權(quán)重值在數(shù)學(xué)意義上具有同樣的重要性。

1.3.2 算法步驟和復(fù)雜度分析

改進(jìn)的加權(quán)網(wǎng)絡(luò)節(jié)點(diǎn)重要性算法步驟如下:

步驟1選出網(wǎng)絡(luò)中節(jié)點(diǎn)度為1的點(diǎn)并將這些點(diǎn)從網(wǎng)絡(luò)中刪除。

步驟2在刪除步驟1中節(jié)點(diǎn)后得到的新的網(wǎng)絡(luò)圖中找出度為1的網(wǎng)絡(luò)節(jié)點(diǎn)。

步驟3重復(fù)步驟2直至網(wǎng)絡(luò)圖中找不出度為1的節(jié)點(diǎn)。步驟1～步驟3中找出的所有節(jié)點(diǎn)的k核值均為1。

步驟4將網(wǎng)絡(luò)圖中所有k核值為1的點(diǎn)從網(wǎng)絡(luò)圖中刪除,得到一個新的網(wǎng)絡(luò)圖,并尋找該網(wǎng)絡(luò)圖中節(jié)點(diǎn)度為2的點(diǎn)。

步驟5重復(fù)步驟2和步驟3,直至網(wǎng)絡(luò)圖中不再有度為2的節(jié)點(diǎn)。步驟4和步驟5中找出的節(jié)點(diǎn)的k核值均為2。

步驟6按照相同的方法確定網(wǎng)絡(luò)中所有節(jié)點(diǎn)的k核值。

步驟7計(jì)算出網(wǎng)絡(luò)中所有節(jié)點(diǎn)的k核值的總和與網(wǎng)絡(luò)中所有邊的權(quán)重值之和。

步驟8確定平衡系數(shù)E的值,并計(jì)算權(quán)重值之和與k核值之和的比值,將每條邊的權(quán)重值除以這個比值得到新的權(quán)重。

步驟9計(jì)算得到加權(quán)網(wǎng)絡(luò)中的節(jié)點(diǎn)k核值k′并進(jìn)一步計(jì)算出k″。

由以上步驟可以看出,改進(jìn)k核算法并沒有改變k核算法的算法復(fù)雜度O(n),只是在得到節(jié)點(diǎn)的k核值后根據(jù)式(2)算出節(jié)點(diǎn)的改進(jìn)k核值k′,并通過式(3)算出k″。這2個步驟的算法復(fù)雜度均為O(n),因此適用于加權(quán)網(wǎng)絡(luò)的改進(jìn)k核算法的算法復(fù)雜度仍為O(n)。而傳統(tǒng)的介數(shù)中心算法,接近中心算法的算法復(fù)雜度為O(n3)。因此,改進(jìn)k核算法更適合用來分析大型網(wǎng)絡(luò)的節(jié)點(diǎn)重要性。

2 實(shí)驗(yàn)結(jié)果與分析

本文實(shí)驗(yàn)加權(quán)網(wǎng)絡(luò)圖如圖2所示。該加權(quán)網(wǎng)絡(luò)由34個節(jié)點(diǎn)和70條邊構(gòu)成。實(shí)驗(yàn)分別應(yīng)用接近中心算法、k核算法以及改進(jìn)k核算法對網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行分析。在實(shí)驗(yàn)中,改進(jìn)k核算法的平衡系數(shù)E=1,在本文后續(xù)的實(shí)驗(yàn)中,將會改變改進(jìn)k核算法中平衡系數(shù)E的取值,對比不同平衡系數(shù)取值對改進(jìn)k核算法最終排序結(jié)果的影響。并分析網(wǎng)絡(luò)中各類節(jié)點(diǎn)在平衡系數(shù)發(fā)生改變時的重要性變化趨勢。本文加權(quán)實(shí)驗(yàn)結(jié)果如表1所示。

圖2 本文實(shí)驗(yàn)加權(quán)網(wǎng)絡(luò)圖

接近中心算法k核算法改進(jìn)k核算法V1V1V1V3V2V34V34V3V33V33V4V2V9V8V3V4V9V4V20V14V14V29V31V31V2V33V32V24V34V9

表1中分別給出了3種算法的節(jié)點(diǎn)重要性排序。由于節(jié)點(diǎn)數(shù)目較多,因此表中只列出了最關(guān)鍵的10個節(jié)點(diǎn)及其順序。可以比較明顯地看出3種算法對關(guān)鍵節(jié)點(diǎn)的篩選結(jié)果有明顯的不同。除了V1節(jié)點(diǎn)都排在首位之外,其余節(jié)點(diǎn)的位置都不相同。其中考慮網(wǎng)絡(luò)連邊權(quán)重的改進(jìn)k核算法與原k核算法的結(jié)果也出現(xiàn)了較大不同。在原k核算法中,也存在相似節(jié)點(diǎn)的重要性難以區(qū)分的問題,改進(jìn)k核算法則很好地解決了這個問題。

為了說明表1中3種算法得出的結(jié)果的科學(xué)性以及驗(yàn)證改進(jìn)k核算法與原k核算法、接近中心算法相比的優(yōu)勢。在實(shí)驗(yàn)中依次將3種算法最重要的10個關(guān)鍵節(jié)點(diǎn)從網(wǎng)絡(luò)圖中移除,分別得到3種算法在依次移除節(jié)點(diǎn)之后的10張網(wǎng)絡(luò)圖,從移除節(jié)點(diǎn)后網(wǎng)絡(luò)中的失效節(jié)點(diǎn)數(shù)、網(wǎng)絡(luò)中最大連通子圖的節(jié)點(diǎn)數(shù)、網(wǎng)絡(luò)損失的連邊權(quán)重這3個方面進(jìn)行分析,得到的實(shí)驗(yàn)結(jié)果如圖3～圖5所示。從圖3～圖5中可以看出,當(dāng)依次從網(wǎng)絡(luò)圖中移除關(guān)鍵節(jié)點(diǎn)后,網(wǎng)絡(luò)的失效節(jié)點(diǎn)數(shù)、最大連通子圖節(jié)點(diǎn)數(shù)、網(wǎng)絡(luò)損失連邊權(quán)重都發(fā)生了很大變化。改進(jìn)k核算法在移除關(guān)鍵節(jié)點(diǎn)后,失效節(jié)點(diǎn)數(shù)量多于接近中心算法和原k核算法。最大連通子圖節(jié)點(diǎn)數(shù)明顯少于原k核算法,與接近中心算法在移除關(guān)鍵節(jié)點(diǎn)后的最大連通子圖節(jié)點(diǎn)數(shù)相當(dāng)。

圖3 移除節(jié)點(diǎn)數(shù)與失效節(jié)點(diǎn)數(shù)關(guān)系

圖4 移除節(jié)點(diǎn)數(shù)與網(wǎng)絡(luò)最大連通子圖節(jié)點(diǎn)數(shù)關(guān)系

圖5 移除節(jié)點(diǎn)數(shù)與網(wǎng)絡(luò)損失連邊權(quán)重關(guān)系

在圖5中,改進(jìn)k核算法在移除節(jié)點(diǎn)之后損失的連邊權(quán)重一直高于原k核算法和接近中心算法。圖3～圖5的實(shí)驗(yàn)結(jié)果表明,改進(jìn)k核算法移除節(jié)點(diǎn)后對網(wǎng)絡(luò)的破壞效果最明顯,因此,這些節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置更重要,特別是與原k核算法相比,在3個參數(shù)的比較中都較原算法提高了很多,并在整體上優(yōu)于接近中心算法的結(jié)果。

在實(shí)驗(yàn)中,改進(jìn)k核算法的平衡系數(shù)值E=1,在加權(quán)網(wǎng)絡(luò)分析中,權(quán)重對網(wǎng)絡(luò)的影響不盡相同,因此在評價網(wǎng)絡(luò)節(jié)點(diǎn)重要性時,權(quán)重的參考量是一個不完全定量因素,改進(jìn)k核算法引進(jìn)平衡系數(shù)E這一參數(shù)來描述這一變化,為了研究平衡系數(shù)E的取值對網(wǎng)絡(luò)節(jié)點(diǎn)重要性評價的影響,在后續(xù)實(shí)驗(yàn)中,將平衡系數(shù)的取值多樣化,從E=1/32依次乘2至E=32進(jìn)行11次實(shí)驗(yàn)結(jié)果比較,得到的實(shí)驗(yàn)結(jié)果如圖6所示。從圖6中可以看出,當(dāng)平衡系數(shù)取值發(fā)生變化時,相應(yīng)地節(jié)點(diǎn)的重要性參數(shù)值也發(fā)生變化,節(jié)點(diǎn)連邊較多,權(quán)重較大的節(jié)點(diǎn)的重要性相對下降,其他節(jié)點(diǎn)的重要性相對上升。為了更直觀地分析各個節(jié)點(diǎn)的重要性變化情況,實(shí)驗(yàn)選取幾個變化較為明顯的節(jié)點(diǎn),例如重要性下降最明顯的節(jié)點(diǎn)V1、V34、V33,重要性上升最明顯的節(jié)點(diǎn)V5、V11、V29,以及在平衡系數(shù)發(fā)生變化時,重要性排序發(fā)生改變的幾個節(jié)點(diǎn)進(jìn)行兩兩比較的定量分析,后續(xù)實(shí)驗(yàn)的結(jié)果如圖7～圖9所示。

圖6 不同平衡系數(shù)的改進(jìn)k核算法結(jié)果

圖7 節(jié)點(diǎn)重要性分析實(shí)驗(yàn)結(jié)果1

圖8 節(jié)點(diǎn)重要性分析實(shí)驗(yàn)結(jié)果2

圖9 節(jié)點(diǎn)重要性分析實(shí)驗(yàn)結(jié)果3

從圖7可以看出,隨著平衡系數(shù)的增大,k核值在節(jié)點(diǎn)重要性評價參數(shù)中的比重逐漸提高,權(quán)重值的比重相應(yīng)降低,V1、V34、V33等權(quán)重值較大的節(jié)點(diǎn)的重要性逐漸下降,V5、V11、V29等權(quán)重值較小的節(jié)點(diǎn)的重要性逐漸上升。

從圖8中V1與V34、V33的比值曲線中可以看出,隨著平衡系數(shù)的增大,V1節(jié)點(diǎn)較V34、V33節(jié)點(diǎn)的重要性下降速度更快,V5節(jié)點(diǎn)較V11、V29節(jié)點(diǎn)的重要性上升速度更快,因此,V1節(jié)點(diǎn)與V5節(jié)點(diǎn)分別是平衡系數(shù)增大之后重要性變化最大的2個節(jié)點(diǎn)。

圖9中比較了幾個重要性相當(dāng)?shù)墓?jié)點(diǎn)重要性變化關(guān)系,從圖9中可以看出,當(dāng)平衡系數(shù)較小時,在算法得出的結(jié)果中,V32、V7、V30節(jié)點(diǎn)更為重要,隨著平衡系數(shù)的增大,比值曲線都開始發(fā)生變化,當(dāng)曲線經(jīng)過y=1這條線時,2個節(jié)點(diǎn)的重要性次序發(fā)生變化,V31、V9、V14節(jié)點(diǎn)的重要性超過V32、V7、V30。V8節(jié)點(diǎn)的重要性則隨著平衡系數(shù)的增大逐漸逼近節(jié)點(diǎn)V9,即比值曲線無限趨近于1。

在平衡系數(shù)發(fā)生變化的過程中,大部分節(jié)點(diǎn)的重要性并沒有發(fā)生極大變化,因此,在節(jié)點(diǎn)重要性排序中并沒有與平衡系數(shù)為1時的排序有太大的差距,即使改變平衡系數(shù),改進(jìn)k核算法得出的節(jié)點(diǎn)重要性排序結(jié)果相比原k核算法也有極大地提高,比最短路徑算法得出的結(jié)果更具科學(xué)性和合理性。

3 結(jié)束語

本文提出一種適用于加權(quán)網(wǎng)絡(luò)的改進(jìn)k核算法。該算法可解決k核算法只能適用于無權(quán)網(wǎng)絡(luò)以及k核值差距過小無法區(qū)分節(jié)點(diǎn)重要性的問題。在本文實(shí)驗(yàn)中,改進(jìn)k核算法在與k核算法、接近中心的算法比較中得出更準(zhǔn)確的結(jié)果。該算法在依次刪除改進(jìn)k核算法結(jié)果中最重要的10個節(jié)點(diǎn)之后,網(wǎng)絡(luò)受到的破壞程度在失效節(jié)點(diǎn)數(shù)、最大連通子圖、網(wǎng)絡(luò)損失權(quán)重3項(xiàng)指標(biāo)上均比k核算法有了大幅提高,整體優(yōu)于接近中心算法。在后續(xù)實(shí)驗(yàn)中,平衡系數(shù)的改變相應(yīng)地改變了算法最終的結(jié)果,并分析了節(jié)點(diǎn)重要性的變化。但針對不同加權(quán)網(wǎng)絡(luò),如何科學(xué)地調(diào)整平衡系數(shù)以取得更精確的實(shí)驗(yàn)結(jié)果,將是下一步的研究方向。

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

[2] 楊 博,陳賀昌,朱冠宇,等.基于超鏈接多樣性分析的新型網(wǎng)頁排名算法[J].計(jì)算機(jī)學(xué)報,2014,37(4):833-847.

[3] 段松青,吳 斌,王 柏.TTRank:基于傾向性轉(zhuǎn)變的用戶影響力排序[J].計(jì)算機(jī)研究與發(fā)展,2014,51(10):2225-2238.

[4] SEN Pei,LEV M,JOSE S,et al.Searching for Superspreaders of Information in Real-world Social Media[J].Scientific Reports,2014(4):55-67.

[5] 李 棟,徐志明,李 生,等.在線社會網(wǎng)絡(luò)中信息擴(kuò)散[J].計(jì)算機(jī)學(xué)報,2014,37(1):189-206.

[6] 楊 博,陳賀昌,朱冠宇,等.基于超鏈接多樣性分析的新型網(wǎng)頁排名算法[J].計(jì)算機(jī)學(xué)報,2014,37(4):833-847.

[7] 馬潤年,文 剛,邵明志,等.基于抗毀性測度的賦權(quán)網(wǎng)絡(luò)抗毀性評估方法[J].計(jì)算機(jī)應(yīng)用研究,2013,30(6):1802-1804.

[8] 李文鋒,符修文.無線傳感器網(wǎng)絡(luò)抗毀性[J].計(jì)算機(jī)學(xué)報,2015,38(3):625-647.

[9] 閔 磊,劉 智,唐向陽,等.基于擴(kuò)展度的復(fù)雜網(wǎng)絡(luò)傳播影響力評估算法[J].物理學(xué)報,2015,64(8):387-397.

[10] GOH K I,OH E,KAHANG B,et al.Spectra and Eigenvectors of Scale-free Networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2003,67(2).

[11] BRYAN K,LEI S E T.Eigenvector:The Linear Algebra Behind Google[J].SIAM Review,2006,48(3):569-581.

[12] 唐晉韜,王 挺,王 戟.適合復(fù)雜網(wǎng)絡(luò)分析的最短路徑近似算法[J].軟件學(xué)報,2011,22(10):2279-2290.

[13] 張喜平,李永樹,劉 剛,等.節(jié)點(diǎn)重要度貢獻(xiàn)的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要度評估方法[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué),2014,11(3):26-32,49.

[14] 王甲生,吳曉平,廖 巍,等.改進(jìn)的加權(quán)復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要度評估方法[J].計(jì)算機(jī)工程,2012,38(10):74-76.

[15] KITSAK M,GALLOS L K,HAVLIN S,et al.Identifying Influential Spreaders in Complex Networks[J].Nature Physics,2010,6(11):888-893.

[16] 任卓明,劉建國,邵鳳,胡兆龍,郭 強(qiáng).復(fù)雜網(wǎng)絡(luò)中最小K-核節(jié)點(diǎn)的傳播能力分析[J].物理學(xué)報,2013,62(10):474-479.