基于加權(quán)K-階傳播數(shù)的節(jié)點(diǎn)重要性*

黃麗亞 湯平川 霍宥良 鄭義 成謝鋒2)

1)(南京郵電大學(xué),電子與光學(xué)工程學(xué)院,微電子學(xué)院,南京 210023)

2)(射頻集成與微組裝技術(shù)國(guó)家地方聯(lián)合工程實(shí)驗(yàn)室,南京 210003)

1 引 言

復(fù)雜網(wǎng)絡(luò)是現(xiàn)實(shí)系統(tǒng)的抽象表達(dá).網(wǎng)絡(luò)節(jié)點(diǎn)依靠邊相互聯(lián)系,通常存在著重要性差異.節(jié)點(diǎn)重要性是分析設(shè)計(jì)網(wǎng)絡(luò)結(jié)構(gòu)、提升系統(tǒng)魯棒性等研究的重要基礎(chǔ)[1-3].目前,已有諸多研究各自從不同的角度提出了節(jié)點(diǎn)重要性評(píng)價(jià)指標(biāo).

度中心性法[4]認(rèn)為節(jié)點(diǎn)擁有的鄰居數(shù)越多,其直接影響力越強(qiáng).對(duì)食物鏈網(wǎng)絡(luò)[5]、P2P網(wǎng)絡(luò)[6]、電子郵件網(wǎng)絡(luò)[7]以及蛋白質(zhì)網(wǎng)絡(luò)[8]的研究指出,當(dāng)度值較大的節(jié)點(diǎn)被移除后,網(wǎng)絡(luò)結(jié)構(gòu)將變得更加脆弱.此外,度中心性法計(jì)算簡(jiǎn)便,其時(shí)間復(fù)雜度為O(N),適用于網(wǎng)絡(luò)規(guī)模較大的情況.然而,度中心性法未考慮非鄰居節(jié)點(diǎn)的影響,利用的信息較為有限,不能充分地反映網(wǎng)絡(luò)的全局特性和橋連接節(jié)點(diǎn)的重要性.任卓明等[9]在度中心性法的基礎(chǔ)上,將鄰居節(jié)點(diǎn)相互連接的緊密程度,即局部聚類系數(shù)也納入了評(píng)價(jià)體系(下文簡(jiǎn)稱Ren法),結(jié)果雖優(yōu)于度中心性法,但其反映網(wǎng)絡(luò)全局特性的能力仍然有限.此外,Ren法利用趨同化函數(shù)將度與聚類系數(shù)處理后直接加和,并未設(shè)置比例系數(shù),即該方法認(rèn)為二者同等重要,其合理性有待商榷.為了更充分地利用網(wǎng)絡(luò)結(jié)構(gòu)信息,Chen等[10]提出了一種基于多級(jí)鄰居信息指標(biāo)的半局部中心測(cè)度的方法(下文簡(jiǎn)稱Chen法),首先確定節(jié)點(diǎn)的一級(jí)重要性為最近鄰與次近鄰節(jié)點(diǎn)的個(gè)數(shù)之和,再計(jì)算節(jié)點(diǎn)的二級(jí)重要性為所有鄰居節(jié)點(diǎn)的一級(jí)重要性之和,最后定義節(jié)點(diǎn)的三級(jí)重要性為所有鄰居節(jié)點(diǎn)的二級(jí)重要性之和,并作為最終的重要性評(píng)價(jià)指標(biāo).但為了保證較低的算法復(fù)雜度,Chen法僅將分析范圍擴(kuò)展到了次近鄰節(jié)點(diǎn),因而對(duì)網(wǎng)絡(luò)全局特性的挖掘也并非十分充分.介數(shù)中心性[11]指網(wǎng)絡(luò)中所有最短路徑通過(guò)某節(jié)點(diǎn)的占比,是節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)傳播信息的影響或?qū)?jié)點(diǎn)預(yù)期負(fù)載的度量.緊密度[12,13]指由某節(jié)點(diǎn)出發(fā),到達(dá)其余節(jié)點(diǎn)的最短路徑的和的倒數(shù),是將信息從給定節(jié)點(diǎn)傳播到網(wǎng)絡(luò)中其他可達(dá)節(jié)點(diǎn)的時(shí)間的度量.介數(shù)中心性與緊密度雖提高了對(duì)橋節(jié)點(diǎn)的重視程度,但需要計(jì)算任意一對(duì)節(jié)點(diǎn)之間的最短路徑,其時(shí)間復(fù)雜度為O(N3),不適用于大型網(wǎng)絡(luò),且對(duì)隨機(jī)網(wǎng)絡(luò)的解釋也不夠充分.特征向量法[14,15]將網(wǎng)絡(luò)鄰接矩陣最大特征值對(duì)應(yīng)特征向量的元素作為各個(gè)節(jié)點(diǎn)的重要性指標(biāo),本質(zhì)上是將單個(gè)節(jié)點(diǎn)的拓?fù)湫再|(zhì)線性疊加,結(jié)果較為片面.Katz[16]認(rèn)為節(jié)點(diǎn)的重要性正比于網(wǎng)絡(luò)鄰接矩陣A的冪級(jí)數(shù)與單位陣E的差的各列元素之和,其中α為權(quán)重衰減因子.Katz指標(biāo)雖充分利用了網(wǎng)絡(luò)的全局特性,但α卻無(wú)法定量計(jì)算,只能根據(jù)不同的網(wǎng)絡(luò)進(jìn)行人為設(shè)置,且該方法還認(rèn)為節(jié)點(diǎn)影響力隨路徑的增加呈指數(shù)形式衰減,較為主觀.此外,現(xiàn)實(shí)世界中的網(wǎng)絡(luò)均是有限的,而Katz指標(biāo)為了得到收斂形式,使路徑長(zhǎng)度取值無(wú)窮大,其結(jié)果包含了大量的冗余信息.為了解決Katz指標(biāo)存在的問題,Zhang等[17]以網(wǎng)絡(luò)節(jié)點(diǎn)為變量,將其余所有節(jié)點(diǎn)對(duì)當(dāng)前節(jié)點(diǎn)的影響力進(jìn)行加和,并假設(shè)節(jié)點(diǎn)的影響力隨路徑的增加呈高斯形式衰減.該方法在一定程度上解決了Katz指標(biāo)的信息冗余等問題,但節(jié)點(diǎn)影響力的衰減形式仍較為主觀.K-核分解法[18,19]試圖遞歸地移去網(wǎng)絡(luò)中度中心性的值小于等于K的節(jié)點(diǎn),其時(shí)間復(fù)雜度為O(N),相比于度中心性、介數(shù)等指標(biāo)更能反映諸如演員網(wǎng)絡(luò)、社交網(wǎng)絡(luò)等實(shí)際網(wǎng)絡(luò)的節(jié)點(diǎn)重要性.但K-核分解法對(duì)節(jié)點(diǎn)的排序并不細(xì)致,常常賦予大量節(jié)點(diǎn)相同的重要度,不適合于樹狀網(wǎng)絡(luò)和無(wú)標(biāo)度網(wǎng)絡(luò)的分析.PageRank算法[20]認(rèn)為節(jié)點(diǎn)的重要性與隨機(jī)瀏覽者訪問的頻率成正比,被廣泛地應(yīng)用在了網(wǎng)頁(yè)排名等領(lǐng)域,但該算法對(duì)含孤立節(jié)點(diǎn)或社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)會(huì)出現(xiàn)重要性排序不唯一等問題.為了解決該弊端,Lü等[21]提出了LeaderRank算法,在原始網(wǎng)絡(luò)的基礎(chǔ)上,增加了一個(gè)與所有節(jié)點(diǎn)雙向連接的Ground節(jié)點(diǎn).這一操作使網(wǎng)絡(luò)變?yōu)閺?qiáng)連通的,其結(jié)果比PageRank算法更加準(zhǔn)確,但LeaderRank算法不適用于無(wú)向網(wǎng)絡(luò).Zhong等[22]利用網(wǎng)絡(luò)節(jié)點(diǎn)被移除前后流行閾值的差來(lái)表征節(jié)點(diǎn)的全局重要性,并利用度中心性來(lái)表征節(jié)點(diǎn)的局部重要性,最后將歸一化后的全局和局部重要性結(jié)果進(jìn)行加權(quán)求和(下文簡(jiǎn)稱CI法),并利用美國(guó)航空網(wǎng)絡(luò)等九個(gè)真實(shí)網(wǎng)絡(luò)證明了CI法的有效性.然而CI法中全局和局部重要性的加權(quán)系數(shù)對(duì)最終結(jié)果的影響較大.雖然文獻(xiàn)[22]經(jīng)仿真分析歸納指出當(dāng)加權(quán)系數(shù)近似為0.5時(shí)得到的節(jié)點(diǎn)重要性結(jié)果較好,但缺乏更為深入的理論證明.此外,CI法為何選擇度中心性而非其他局部重要性指標(biāo)有待進(jìn)一步說(shuō)明.

以上方法均存在各自的不足,本研究將提出一種新的節(jié)點(diǎn)重要性評(píng)價(jià)方法,即加權(quán)K-階傳播數(shù)法,并試圖利用WS (Watts-Strogatz)小世界網(wǎng)絡(luò)、海豚網(wǎng)絡(luò)、美國(guó)西部電網(wǎng)、芝加哥公路網(wǎng)絡(luò)、網(wǎng)絡(luò)科學(xué)家合著網(wǎng)絡(luò)以及小鼠神經(jīng)纖維束網(wǎng)絡(luò)進(jìn)行仿真分析,以證明該方法的有效性.

2 加權(quán)K-階傳播數(shù)模型

SI (susceptible-infective),SIS (susceptibleinfective-susceptible)和SIR (susceptible-infectiveremoved)等模型[23]被廣泛地應(yīng)用在疾病以及信息傳播等領(lǐng)域,最初均是對(duì)某地區(qū)疾病傳播過(guò)程的抽象.其中,個(gè)體能否恢復(fù)健康和是否具有免疫力是造成上述模型差異的重要因素.SI和SIS模型假設(shè)個(gè)體不具備免疫力,將人群分為易感染者和已感染者兩類.此外,SI模型認(rèn)為個(gè)體一旦被傳染便永久處于已感染狀態(tài),而SIS模型則認(rèn)為個(gè)體被傳染后將以一定概率恢復(fù)為易感狀態(tài),并會(huì)被再次傳染.SIR模型假設(shè)已感染者可被治愈且將具有終身性的免疫力,將人群分為易感染者、已感染者和免疫移出者三類.然而,以上模型均假設(shè)疾病傳播為隨機(jī)接觸,并未考慮個(gè)體間的拓?fù)潢P(guān)系.受上述模型啟發(fā),本文將結(jié)合復(fù)雜網(wǎng)絡(luò)對(duì)已感染者無(wú)法恢復(fù)健康且不具有免疫力的最為簡(jiǎn)單的疾病傳播過(guò)程進(jìn)行抽象,最終得到加權(quán)K-階傳播數(shù)法來(lái)評(píng)價(jià)節(jié)點(diǎn)的重要性,描述如下.

首先給定無(wú)向網(wǎng)絡(luò)圖G(V,E),其中,V={v1,v2,···,vn}為節(jié)點(diǎn)集,共n個(gè)節(jié)點(diǎn),代表個(gè)體;E為邊集,eij表示節(jié)點(diǎn)vi與vj之間的邊.這里假設(shè)疾病傳播過(guò)程中該網(wǎng)絡(luò)的結(jié)構(gòu)不會(huì)發(fā)生變化,且已感染者只能傳染給與其直接接觸的易感染者.現(xiàn)假設(shè)某節(jié)點(diǎn)vi為已感染者,與其相鄰的易感染者集合記為Γ(vi).對(duì)節(jié)點(diǎn)vj∈ Γ(vi)而言,vi將以一定概率 0≤pij≤1 向vj傳播 疾病.同時(shí),vi向vj傳播疾病需要耗費(fèi)一定時(shí)間tij,通常受到邊eij的影響.若除vi外,vj同時(shí)受到其他相鄰的已感染者的傳播,還需進(jìn)行綜合考量.以上描述考慮到了節(jié)點(diǎn)間疾病傳播的概率以及耗時(shí)等因素,但若網(wǎng)絡(luò)邊是無(wú)權(quán)的,且不考慮節(jié)點(diǎn)以及邊的意義,則可進(jìn)一步抽象,作出以下假設(shè)：

1)已感染者會(huì)向其相鄰的所有易感染者傳播疾病;

2)已感染者向其相鄰的易感染者傳播疾病的耗時(shí)相等,并設(shè)為1;

3)易感染者一旦受到其任一相鄰的已感染者的傳播,便轉(zhuǎn)化為已感染者.

在衡量節(jié)點(diǎn)的重要性時(shí),較為常用的方法是分別將各個(gè)節(jié)點(diǎn)設(shè)置為傳染源進(jìn)行疾病傳播,并以網(wǎng)絡(luò)中所有節(jié)點(diǎn)被轉(zhuǎn)化為已感染者的總耗時(shí)作為節(jié)點(diǎn)重要性的評(píng)價(jià)指標(biāo),總耗時(shí)越少,則證明節(jié)點(diǎn)越重要.然而,當(dāng)網(wǎng)絡(luò)非連通時(shí),從不同節(jié)點(diǎn)出發(fā)最終能夠傳播到的節(jié)點(diǎn)總數(shù)未必相同.為了保證一致性,另一種節(jié)點(diǎn)重要性衡量方法仍是將各個(gè)節(jié)點(diǎn)設(shè)置為傳染源,但比較的是在經(jīng)歷相同的傳播時(shí)長(zhǎng)K后網(wǎng)絡(luò)中已感染者的數(shù)量,數(shù)量越大則證明該節(jié)點(diǎn)越重要.基于假設(shè)2可將傳播時(shí)長(zhǎng)K取值離散,并規(guī)定為非負(fù)整數(shù),這與SI等模型中時(shí)間取值連續(xù)的假設(shè)略有不同.其中,當(dāng)K=0 時(shí)可認(rèn)為只有傳染源節(jié)點(diǎn)已被感染,但尚未開始傳播.

此外,基于假設(shè)1和3可以得到以vi為傳染源,傳播了時(shí)長(zhǎng)K后網(wǎng)絡(luò)中已感染者的數(shù)量為

傳播時(shí)長(zhǎng)K的取值是影響節(jié)點(diǎn)重要性評(píng)價(jià)結(jié)果的關(guān)鍵.文獻(xiàn)[24]利用并基于信息熵定義了K-階結(jié)構(gòu)熵HK,衡量了網(wǎng)絡(luò)的異構(gòu)性：

結(jié)構(gòu)熵HK取值越小,網(wǎng)絡(luò)的異構(gòu)性越強(qiáng),并以結(jié)構(gòu)熵序列為依據(jù)研究了WS小世界、BA無(wú)標(biāo)度等網(wǎng)絡(luò)的異構(gòu)性.若從疾病傳播的角度出發(fā),可認(rèn)為HK取值越大,以各個(gè)節(jié)點(diǎn){v1,v2,·· ·,vn}分別作為傳染源的網(wǎng)絡(luò)K-階傳播數(shù)之間的差異越小,即可認(rèn)為各節(jié)點(diǎn)重要性的差異越小,反之差異越大.若僅僅以某單一傳播時(shí)長(zhǎng)下網(wǎng)絡(luò)中已感染者的數(shù)量來(lái)衡量節(jié)點(diǎn)的重要性,可能會(huì)遺漏其他傳播時(shí)長(zhǎng)下的有用信息.因此,本文將對(duì)K取從0至d間的所有時(shí)刻進(jìn)行綜合考察,定義節(jié)點(diǎn)vi的重要性Qvi為

其中

3 典型網(wǎng)絡(luò)的節(jié)點(diǎn)重要性

為了驗(yàn)證加權(quán)K-階傳播數(shù)法在節(jié)點(diǎn)重要性評(píng)估方面的優(yōu)勢(shì),本文將利用WS小世界網(wǎng)絡(luò)、海豚網(wǎng)絡(luò)、美國(guó)西部電網(wǎng)、芝加哥公路網(wǎng)絡(luò)、網(wǎng)絡(luò)科學(xué)家合著網(wǎng)絡(luò)以及小鼠神經(jīng)纖維束網(wǎng)絡(luò)進(jìn)行仿真分析.

3.1 WS小世界網(wǎng)絡(luò)

圖1 隨機(jī)生成的100節(jié)點(diǎn)WS小世界網(wǎng)絡(luò) (a)網(wǎng)絡(luò)結(jié)構(gòu);(b)邊31-33被改連至邊31-72;(c)邊95-96被改連至邊95-53Fig.1.A random WS small-world network with 100 nodes：(a)Network structure;(b)the edge 31-33 is rescheduled to the edge 31-72;(c)the edge 95-96 is rescheduled to the edge 95-53.

小世界網(wǎng)絡(luò)是指同時(shí)具有較短特征路徑長(zhǎng)度以及較大平均聚類系數(shù)的一種網(wǎng)絡(luò)類型.Watts和Strogatz[25]最早提出了一種構(gòu)造小世界網(wǎng)絡(luò)的方法,即將最近鄰耦合網(wǎng)絡(luò)中的邊依概率進(jìn)行隨機(jī)重連,通常將這種網(wǎng)絡(luò)稱為WS小世界網(wǎng)絡(luò).圖1(a)基于100節(jié)點(diǎn)最近鄰耦合網(wǎng)絡(luò)隨機(jī)生成了一個(gè)WS小世界網(wǎng)絡(luò),該最近鄰耦合網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)與其鄰近的左右兩側(cè)各兩個(gè)節(jié)點(diǎn)相連.在隨機(jī)重連后,邊31-33和95-96分別被改連為31-72和95-53,見圖1(b)和圖1(c),其余邊的位置不變.

表1列出了該WS小世界網(wǎng)絡(luò)與同規(guī)模隨機(jī)網(wǎng)絡(luò)的平均聚類系數(shù)、特征路徑長(zhǎng)度等參數(shù).可見,該網(wǎng)絡(luò)的特征路徑長(zhǎng)度為隨機(jī)網(wǎng)絡(luò)的2.49倍,但其平均聚類系數(shù)為隨機(jī)網(wǎng)絡(luò)的近20倍,這是由于邊31-72和95-53的長(zhǎng)程連接提高了網(wǎng)絡(luò)的連通性.

表1 WS小世界網(wǎng)絡(luò)以及同規(guī)模隨機(jī)網(wǎng)絡(luò)的網(wǎng)絡(luò)參數(shù)Table 1.Network features of the WS small-world network and random networks.

現(xiàn)利用加權(quán)K-階傳播數(shù)法對(duì)該網(wǎng)絡(luò)節(jié)點(diǎn)的重要性進(jìn)行分析.圖2(a)為網(wǎng)絡(luò)的K-階結(jié)構(gòu)熵HK,圖2(b)為權(quán)重系數(shù)cK,圖2(c)為歸一化的節(jié)點(diǎn)重要性.此外,圖2(c)中的小圖按色度對(duì)重要性進(jìn)行了標(biāo)注.

由前文所述,節(jié)點(diǎn)95和53,31和72之間的長(zhǎng)程連接提高了網(wǎng)絡(luò)的連通性,若移除上述任一節(jié)點(diǎn),網(wǎng)絡(luò)的特征路徑長(zhǎng)度將大為增加,因此加權(quán)K-階傳播數(shù)法認(rèn)為以上四個(gè)節(jié)點(diǎn)的重要性最高是較為合理的.由于該網(wǎng)絡(luò)是基于最近鄰耦合網(wǎng)絡(luò)構(gòu)造的,而最近鄰耦合網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)與其鄰近的左右兩側(cè)各兩個(gè)節(jié)點(diǎn)相連.因此,與95,53,31,72距離相近的左右各兩個(gè)節(jié)點(diǎn)的重要性應(yīng)當(dāng)相似,且距離95,53,31,72越遠(yuǎn),節(jié)點(diǎn)的重要性越低.例如,移除91,92,99或98中的任一節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)結(jié)構(gòu)造成的影響是相似的;此外,同時(shí)移除99和98相較同時(shí)移除100和1,會(huì)有更多的節(jié)點(diǎn)難以通過(guò)95進(jìn)行長(zhǎng)程通信,因此99和98的重要性高于100和1是較為合理的.值得注意的是,圖2(c)中97的重要性顯著高于96,這是由于邊96-95被斷開,若依賴96進(jìn)行長(zhǎng)程通信需要借助邊95-94,而97與95直接相連,因此通過(guò)97進(jìn)行長(zhǎng)程通信更為便捷.此外,由于邊33-31被斷開,33,34,35等節(jié)點(diǎn)向30,29,28等節(jié)點(diǎn)進(jìn)行短程通信,或經(jīng)由31向72等節(jié)點(diǎn)進(jìn)行長(zhǎng)程通信,均需要依賴節(jié)點(diǎn)32,因此其重要性應(yīng)當(dāng)較高.最后,35,36,37,38等節(jié)點(diǎn)進(jìn)行長(zhǎng)短程通信時(shí)需要依賴33或34;對(duì)35,37等奇數(shù)節(jié)點(diǎn)而言,通過(guò)33或34進(jìn)行通信的效果相同,但對(duì)36,38等偶數(shù)節(jié)點(diǎn)而言,通過(guò)34進(jìn)行通信的效率更高,可見34的重要性大于33,這也可以解釋圖2(c)中36的重要性略高于35等現(xiàn)象.

為了進(jìn)一步證明加權(quán)K-階傳播數(shù)法的有效性,圖3繪制了度中心性、Ren法、Chen法、介數(shù)中心性、特征向量法、Katz指標(biāo)(權(quán)重衰減因子取1.5倍鄰接矩陣最大特征值的倒數(shù))、PageRank算法(阻尼系數(shù)取0.85)以及CI法(權(quán)重系數(shù)取0.5)得出的節(jié)點(diǎn)重要性結(jié)果.由于K-核分解法得到的所有節(jié)點(diǎn)的重要性相同,因此其結(jié)果未在圖3給出.

圖2 基于加權(quán)K-階傳播數(shù)法的WS小世界網(wǎng)絡(luò)節(jié)點(diǎn)重要性結(jié)果 (a)K-階結(jié)構(gòu)熵;(b)權(quán)重系數(shù);(c)節(jié)點(diǎn)重要性Fig.2.Node importance of the WS small-world network based on the weightedK-order propagation number algorithm：(a)TheK-order structure entropy;(b)the weight coefficient;(c)the importance of nodes.

由圖3可知,以上方法認(rèn)為33或96的重要性最低,而加權(quán)K-階傳播數(shù)法卻認(rèn)為33和96的重要性較高.由前文分析可知,雖然在33節(jié)點(diǎn)移除后,網(wǎng)絡(luò)的長(zhǎng)短程通信不會(huì)受到顯著影響,但27,28,29等節(jié)點(diǎn)與34,35,36等節(jié)點(diǎn)間的短程通信,或34,35,36等節(jié)點(diǎn)依靠31進(jìn)行長(zhǎng)程通信只能依賴邊32-34進(jìn)行;同樣,當(dāng)96被移除后,邊95-97將參與所有通信,可見33和96的存在降低了其余重要節(jié)點(diǎn)或邊的負(fù)載,起到了分流的作用,因此認(rèn)為33或96在所有節(jié)點(diǎn)中重要性最低是值得商榷的;度中心性、特征向量法、Katz指標(biāo)、PageRank算法和CI法認(rèn)為72和53的重要性遠(yuǎn)高于31和95,但長(zhǎng)程通信需要同時(shí)依賴以上4個(gè)節(jié)點(diǎn)進(jìn)行,因此節(jié)點(diǎn)31和72或95和53的重要性應(yīng)當(dāng)是相似的;度中心性、Ren法、Chen法、Katz指標(biāo)、PageRank算法和CI法,尤其是K-核分解法對(duì)節(jié)點(diǎn)的排序并不細(xì)致,存在節(jié)點(diǎn)重要性相同的情況;此外,介數(shù)中心性認(rèn)為10,11,12等節(jié)點(diǎn)的重要性高于52,54,71,73等節(jié)點(diǎn),49,51,55,57,74,76等節(jié)點(diǎn)的重要性高于50,52,54,56,73,75等節(jié)點(diǎn),PageRank算法認(rèn)為61,62,63等節(jié)點(diǎn)的重要性高于52,54,71,73等節(jié)點(diǎn),均缺乏較為合理的解釋.可見,加權(quán)K-階傳播數(shù)法對(duì)網(wǎng)絡(luò)通信的刻畫更為細(xì)致,節(jié)點(diǎn)重要性的評(píng)估優(yōu)于以上傳統(tǒng)方法.

3.2 海豚網(wǎng)絡(luò)

為了進(jìn)一步驗(yàn)證加權(quán)K-階傳播數(shù)法的有效性,本文以海豚網(wǎng)絡(luò)為例進(jìn)行研究.Lusseau等[26,27]對(duì)新西蘭道特富爾峽灣(Doubtful Sound)62只寬吻海豚進(jìn)行研究并構(gòu)建了海豚社會(huì)網(wǎng)絡(luò).基于加權(quán)K-階傳播數(shù)法的海豚網(wǎng)絡(luò)節(jié)點(diǎn)重要性結(jié)果如圖4所示,圖4(a)為網(wǎng)絡(luò)的K-階結(jié)構(gòu)熵HK,圖4(b)為權(quán)重系數(shù)cK,圖4(c)為歸一化后的節(jié)點(diǎn)重要性.網(wǎng)絡(luò)中節(jié)點(diǎn)代表海豚,邊表示海豚間的相關(guān)接觸.

表2列出了基于加權(quán)K-階傳播數(shù)法、Ren法、Chen法、介數(shù)中心性、特征向量法、Katz指標(biāo)(權(quán)重衰減因子為1.5倍鄰接矩陣最大特征值的倒數(shù))、PageRank算法(阻尼系數(shù)0.85)、CI法(權(quán)重系數(shù)取0.5)得出的前15個(gè)重要節(jié)點(diǎn)的排序結(jié)果.由于度中心性和K-核分解法存在節(jié)點(diǎn)重要性相等的情況,其排序結(jié)果未在表2列出.其中,基于度中心性法得到的節(jié)點(diǎn)重要性排序結(jié)果(前20個(gè)重要節(jié)點(diǎn))為15 ＞ 38=46 ＞ 34=52 ＞ 18=21=30=58 ＞ 2=14=39=41 ＞ 10=16=19=37=44=51=55;K-核分解法認(rèn)為1,2,7,8,9等37個(gè)節(jié)點(diǎn)的重要性最高且相等.

與度中心性、Ren法、Chen法、特征向量法、Katz指標(biāo)、PageRank算法和CI法不同,加權(quán)K-階傳播數(shù)法認(rèn)為節(jié)點(diǎn)37相對(duì)重要,排在第7位.文獻(xiàn)[27]將該海豚網(wǎng)絡(luò)劃分成了若干小社區(qū),指出37號(hào)海豚曾消失了一段時(shí)間,此時(shí)不同海豚社區(qū)間的互動(dòng)受到了限制,當(dāng)37號(hào)海豚再次出現(xiàn)時(shí),社區(qū)又恢復(fù)了普遍聯(lián)系,Lusseau等[27]指出37號(hào)海豚是社區(qū)間信息交流的關(guān)鍵個(gè)體.因此,加權(quán)K-階傳播數(shù)法認(rèn)為節(jié)點(diǎn)37相對(duì)重要的結(jié)論是較為合理的.然而,37號(hào)海豚處于社區(qū)邊緣,因此介數(shù)中心性認(rèn)為節(jié)點(diǎn)37重要性最高的結(jié)論是值得商榷的.

圖3 基于若干傳統(tǒng)算法的WS小世界網(wǎng)絡(luò)節(jié)點(diǎn)重要性評(píng)價(jià)結(jié)果 (a)度中心性;(b)Ren法;(c)Chen法;(d)介數(shù)中心性;(e)特征向量法;(f)Katz指標(biāo)法;(g)PageRank算法;(h)CI法Fig.3.Node importance of the WS small-world network based on some traditional algorithms：(a)Degree centrality;(b)Ren method;(c)Chen method;(d)betweenness centrality;(e)eigenvector method;(f)Katz index;(g)PageRank;(h)CI method.

此外,加權(quán)K-階傳播數(shù)法提高了對(duì)節(jié)點(diǎn)2和21的重視程度,分別排在第11和第4位,而2和21處于各自海豚社區(qū)偏中心位置,又與37等負(fù)責(zé)信息交流的節(jié)點(diǎn)直接相連,因此該結(jié)論是較為合理的;Ren法、Chen法、特征向量法、Katz指標(biāo)法和CI法認(rèn)為節(jié)點(diǎn)22相對(duì)重要,但該節(jié)點(diǎn)的度中心性與介數(shù)均是較低的;最后,度中心性法和K-核分解法存在節(jié)點(diǎn)重要性相同的情況,排序不細(xì)致.可見,加權(quán)K-階傳播數(shù)法在評(píng)價(jià)海豚網(wǎng)絡(luò)節(jié)點(diǎn)重要性時(shí)適當(dāng)?shù)靥岣吡藢?duì)海豚社區(qū)間信息交流起到關(guān)鍵作用的節(jié)點(diǎn)的重視程度,結(jié)果更為合理.

3.3 基于節(jié)點(diǎn)重要性的蓄意攻擊研究

圖4 基于加權(quán)K-階傳播數(shù)法的海豚網(wǎng)絡(luò)節(jié)點(diǎn)重要性結(jié)果 (a)K-階結(jié)構(gòu)熵;(b)權(quán)重系數(shù);(c)節(jié)點(diǎn)重要性Fig.4.Node importance of the dolphin network based on the weightedK-order propagation number algorithm：(a)TheK-order structure entropy;(b)the weight coefficient;(c)the importance of nodes.

表2 海豚網(wǎng)節(jié)點(diǎn)重要性排序結(jié)果Table 2.Node importance ordering result of the dolphin network.

為了進(jìn)一步驗(yàn)證加權(quán)K-階傳播數(shù)法的優(yōu)越性,本文對(duì)美國(guó)西部電網(wǎng)[25]、芝加哥公路網(wǎng)絡(luò)[28]、網(wǎng)絡(luò)科學(xué)家合著網(wǎng)絡(luò)[29]以及小鼠神經(jīng)纖維束網(wǎng)絡(luò)(Kasthuri_graph_v4)[30]進(jìn)行了節(jié)點(diǎn)重要性研究.其中美國(guó)西部電網(wǎng)共有4941個(gè)節(jié)點(diǎn)和6594條邊,描述了美國(guó)西部的高壓輸電電網(wǎng)結(jié)構(gòu);芝加哥公路網(wǎng)絡(luò)共有1467個(gè)節(jié)點(diǎn)和1298條邊,描述了美國(guó)芝加哥地區(qū)的公路運(yùn)輸情況;網(wǎng)絡(luò)科學(xué)家合著網(wǎng)絡(luò)共有1589個(gè)節(jié)點(diǎn)和2742條邊,描述了從事網(wǎng)絡(luò)理論和實(shí)驗(yàn)的科學(xué)家合著關(guān)系;小鼠神經(jīng)纖維束網(wǎng)絡(luò)共有1029個(gè)節(jié)點(diǎn)和1700條邊,描述了小鼠部分腦皮層中神經(jīng)元間的軸突束連接.美國(guó)西部電網(wǎng)、芝加哥公路網(wǎng)絡(luò)和網(wǎng)絡(luò)科學(xué)家合著網(wǎng)絡(luò)均是無(wú)權(quán)無(wú)向的;小鼠神經(jīng)纖維束網(wǎng)絡(luò)是有權(quán)無(wú)向的,為了適應(yīng)加權(quán)K-階傳播數(shù)法,本文忽略了該網(wǎng)絡(luò)的邊權(quán)信息.以上網(wǎng)絡(luò)的K-階結(jié)構(gòu)熵HK如圖5所示.

由于以上四個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)較多,本文擬采用蓄意攻擊策略對(duì)節(jié)點(diǎn)重要性進(jìn)行研究[31-33].蓄意攻擊策略是指基于節(jié)點(diǎn)重要性由高到低的排序依次攻擊網(wǎng)絡(luò),即移除與節(jié)點(diǎn)相連的所有邊,通過(guò)網(wǎng)絡(luò)結(jié)構(gòu)隨攻擊次數(shù)的變化情況來(lái)評(píng)價(jià)節(jié)點(diǎn)重要性算法的各自特點(diǎn).由于在蓄意攻擊后網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生了變化,因此僅僅依據(jù)原始網(wǎng)絡(luò)的節(jié)點(diǎn)重要性進(jìn)行研究會(huì)存在偏差.為了解決此問題,本文在每次蓄意攻擊后更新節(jié)點(diǎn)排序結(jié)果.此外,若存在重要性相等的情況,將選擇編號(hào)最小的節(jié)點(diǎn)進(jìn)行攻擊.

圖5 K-階結(jié)構(gòu)熵 (a)美國(guó)西部電網(wǎng);(b)芝加哥公路網(wǎng)絡(luò);(c)科學(xué)家合作網(wǎng)絡(luò);(d)小鼠神經(jīng)纖維束網(wǎng)絡(luò)Fig.5.TheK-order structure entropy：(a)The western power grid of the United States;(b)the road transportation network of the Chicago region;(c)the co-authorship network in network science;(d)the axonal tracts network between neurons of mouse.

由于網(wǎng)絡(luò)被攻擊后可能會(huì)出現(xiàn)孤立節(jié)點(diǎn),因此選用網(wǎng)絡(luò)效率來(lái)評(píng)價(jià)網(wǎng)絡(luò)的連通性.網(wǎng)絡(luò)效率的表達(dá)式為

其 中dvivj是 指 節(jié) 點(diǎn)vi和vj之間的最短路徑長(zhǎng)度.由(6)式可知,e值越大,網(wǎng)絡(luò)效率越高;當(dāng)網(wǎng)絡(luò)由孤立節(jié)點(diǎn)組成時(shí)e=0,取值最小.攻擊節(jié)點(diǎn)可能造成網(wǎng)絡(luò)連接通路的中斷,節(jié)點(diǎn)間的最短路徑將有所增大,網(wǎng)絡(luò)效率則會(huì)隨之降低.為了更為直觀地反映被攻擊后網(wǎng)絡(luò)效率的降低情況,依照文獻(xiàn)[9]定義網(wǎng)絡(luò)效率下降率ε為

其中e0為未被攻擊的原始網(wǎng)絡(luò)的網(wǎng)絡(luò)效率.由(7)式可見,ε的取值為[ 0,1],當(dāng)網(wǎng)絡(luò)未被攻擊時(shí)ε=0,當(dāng)網(wǎng)絡(luò)被攻擊時(shí)ε會(huì)隨之升高;最終,當(dāng)所有的邊被刪除時(shí)網(wǎng)絡(luò)效率降至最低,此時(shí)ε=1 .此外,為了進(jìn)一步分析攻擊前后網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化情況,依照文獻(xiàn)[33]將網(wǎng)絡(luò)最大子圖節(jié)點(diǎn)數(shù)設(shè)為γ.圖6和圖7分別繪制了美國(guó)西部電網(wǎng)、芝加哥公路網(wǎng)絡(luò)、網(wǎng)絡(luò)科學(xué)家合著網(wǎng)絡(luò)以及小鼠神經(jīng)纖維束網(wǎng)絡(luò)基于不同節(jié)點(diǎn)重要性的排序方法,其網(wǎng)絡(luò)效率下降率ε和最大子圖節(jié)點(diǎn)數(shù)γ隨攻擊次數(shù)的變化曲線.其中,Katz指標(biāo)的權(quán)重衰減因子為1.5倍鄰接矩陣最大特征值的倒數(shù);PageRank算法的阻尼系數(shù)取0.85;CI法的權(quán)重系數(shù)取0.5.

對(duì)美國(guó)西部電網(wǎng)而言,依照加權(quán)K-階傳播數(shù)法和介數(shù)中心性法的排序結(jié)果進(jìn)行攻擊,網(wǎng)絡(luò)效率下降得最為迅速,僅攻擊約100次后,網(wǎng)絡(luò)效率便下降了近90%;而依據(jù)度中心性、Ren法、Chen法、特征向量法、Katz指標(biāo)、PageRank算法和CI法則需約300次,K-核分解法需約550次,才能達(dá)到同等效果.此外,基于加權(quán)K-階傳播數(shù)法和介數(shù)中心性對(duì)網(wǎng)絡(luò)進(jìn)行攻擊,最大子圖節(jié)點(diǎn)數(shù)降低的速率遠(yuǎn)遠(yuǎn)高于其他方法.以加權(quán)K-階傳播數(shù)法為例,當(dāng)網(wǎng)絡(luò)被攻擊200次后,最大子圖節(jié)點(diǎn)數(shù)僅為154,為原始網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的3%,可認(rèn)為網(wǎng)絡(luò)基本癱瘓.而度中心性、Ren法、Chen法、特征向量法、Katz指標(biāo)和CI法則需攻擊近400次,PageRank算法需650次,K-核分解法需1000次才能達(dá)到相同效果;對(duì)芝加哥公路網(wǎng)絡(luò)而言,依據(jù)加權(quán)K-階傳播數(shù)法、介數(shù)中心性、Chen法、特征向量法、Katz指標(biāo)和CI法進(jìn)行蓄意攻擊,網(wǎng)絡(luò)被破壞的程度較為接近,且優(yōu)于度中心性、Ren法、PageRank算法和K-核分解法.其中,依據(jù)加權(quán)K-階傳播數(shù)法進(jìn)行蓄意攻擊,網(wǎng)絡(luò)效率下降得最為迅速;對(duì)網(wǎng)絡(luò)科學(xué)家合著網(wǎng)絡(luò)而言,依照加權(quán)K-階傳播數(shù)法和介數(shù)中心性進(jìn)行蓄意攻擊,網(wǎng)絡(luò)被破壞的程度較為接近,且優(yōu)于其他算法;對(duì)小鼠神經(jīng)纖維束網(wǎng)絡(luò)而言,依據(jù)加權(quán)K-階傳播數(shù)法、度中心性、介數(shù)中心性、特征向量法、Katz指標(biāo)、PageRank算法和CI法進(jìn)行蓄意攻擊,網(wǎng)絡(luò)被破壞的程度較為接近,且優(yōu)于Ren法、Chen法和K-核分解法.其中,依據(jù)加權(quán)K-階傳播數(shù)法和介數(shù)中心性進(jìn)行蓄意攻擊,網(wǎng)絡(luò)最大子圖節(jié)點(diǎn)數(shù)下降得最為迅速,略優(yōu)于其他算法.

圖6 網(wǎng)絡(luò)效率下降率ε隨攻擊次數(shù)的變化情況 (a)美國(guó)西部電網(wǎng);(b)芝加哥公路網(wǎng)絡(luò);(c)網(wǎng)絡(luò)科學(xué)家合著網(wǎng)絡(luò);(d)小鼠神經(jīng)纖維束網(wǎng)絡(luò)Fig.6.Change of the network efficiency decrease rateεwith attacking times：(a)The western power grid of the United States;(b)the road transportation network of the Chicago region;(c)the co-authorship network in network science;(d)the axonal tracts network between neurons of mouse.

圖7 最大子圖節(jié)點(diǎn)數(shù)γ隨攻擊次數(shù)的變化情況 (a)美國(guó)西部電網(wǎng);(b)芝加哥公路網(wǎng)絡(luò);(c)網(wǎng)絡(luò)科學(xué)家合著網(wǎng)絡(luò);(d)小鼠神經(jīng)纖維束網(wǎng)絡(luò)Fig.7.Change of the node number of the maximum sub-graphεwith attacking times：(a)The western power grid of the United States;(b)the road transportation network of the Chicago region;(c)the co-authorship network in network science;(d)the axonal tracts network between neurons of mouse.

綜上所述,無(wú)論對(duì)美國(guó)西部電網(wǎng)、芝加哥公路網(wǎng)絡(luò)、網(wǎng)絡(luò)科學(xué)家合著網(wǎng)絡(luò)還是小鼠神經(jīng)纖維束網(wǎng)絡(luò)而言,基于加權(quán)K-階傳播數(shù)法進(jìn)行蓄意攻擊,僅需移除少量重要節(jié)點(diǎn)便可實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的充分破壞.

4 結(jié) 論

本文考慮到個(gè)體間的相關(guān)關(guān)系,基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)重新描述了傳染病模型,并將各個(gè)節(jié)點(diǎn)分別設(shè)置為傳染源進(jìn)行疾病傳播,提出了加權(quán)K-階傳播數(shù)法.通過(guò)對(duì)WS小世界網(wǎng)絡(luò)的仿真分析發(fā)現(xiàn),加權(quán)K-階傳播數(shù)法相較于傳統(tǒng)的節(jié)點(diǎn)重要性評(píng)價(jià)指標(biāo)能夠更為綜合地考量長(zhǎng)程連接對(duì)網(wǎng)絡(luò)長(zhǎng)、短程通信的影響;此外,加權(quán)K-階傳播數(shù)法不僅認(rèn)為海豚網(wǎng)絡(luò)社區(qū)中心的重要性較高,且適當(dāng)?shù)靥岣吡藢?duì)社區(qū)間的信息交流起到關(guān)鍵作用的海豚的受重視程度.最后,本文還基于蓄意攻擊策略以美國(guó)西部電網(wǎng)、芝加哥公路網(wǎng)絡(luò)、網(wǎng)絡(luò)科學(xué)家合著網(wǎng)絡(luò)以及小鼠神經(jīng)纖維束網(wǎng)絡(luò)為實(shí)例進(jìn)行了研究.然而,由于目前加權(quán)K-階傳播數(shù)法的求解依賴于網(wǎng)絡(luò)鄰接矩陣的K-階多項(xiàng)式,需要進(jìn)行K—1次矩陣乘法和K次矩陣加法,時(shí)間復(fù)雜度較高.因此需要進(jìn)一步探索K-階傳播數(shù)的物理意義以提出更為便捷的求解方案.此外,小鼠神經(jīng)纖維束網(wǎng)絡(luò)原為有權(quán)網(wǎng)絡(luò),為了適應(yīng)加權(quán)K-階傳播數(shù)法,本文忽略了該網(wǎng)絡(luò)的邊權(quán)信息.因此將加權(quán)K-階傳播數(shù)法進(jìn)行改進(jìn),使其適用于有向有權(quán)網(wǎng)絡(luò),也是后續(xù)研究的重點(diǎn).