康玲 項(xiàng)冰冰 翟素蘭 鮑中奎 張海峰

(安徽大學(xué)數(shù)學(xué)科學(xué)學(xué)院,合肥 230601)

(2018年5月23日收到；2018年6月27日收到修改稿)

1 引 言

隨著信息技術(shù)的發(fā)展以及經(jīng)濟(jì)的全球化,人類的社會活動(dòng)日趨網(wǎng)絡(luò)化,像在線社交網(wǎng)絡(luò)、科研合作網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、電力網(wǎng)絡(luò)以及與人自身相關(guān)的新陳代謝網(wǎng)絡(luò)等不斷進(jìn)入人們的視野.另外,這些網(wǎng)絡(luò)的數(shù)據(jù)規(guī)模與日劇增,內(nèi)在結(jié)構(gòu)也變得日益復(fù)雜.面對這些大規(guī)模的復(fù)雜網(wǎng)絡(luò),能否有效識別其中具有影響力的節(jié)點(diǎn),具有重要的理論意義和實(shí)際應(yīng)用價(jià)值,已被廣泛應(yīng)用于疾病傳播、謠言擴(kuò)散、新產(chǎn)品的推廣以及交通擁堵的治理等方面[1?6].

一些中心性指標(biāo)如度中心性[7]、介數(shù)中心性[8]、接近中心性[9]、特征向量中心性[10],k-shell分解等[11]相繼被提出來識別網(wǎng)絡(luò)中的影響力節(jié)點(diǎn).近年來,Chen等[12]考慮了節(jié)點(diǎn)的高階鄰居信息,提出一種基于多級鄰居信息的半局部指標(biāo)來進(jìn)行節(jié)點(diǎn)的排序；考慮到網(wǎng)絡(luò)的結(jié)構(gòu)洞節(jié)點(diǎn)對網(wǎng)絡(luò)傳播的作用,韓忠明等[13]以及蘇曉萍和宋玉蓉[14]結(jié)合結(jié)構(gòu)洞理論,利用鄰域的結(jié)構(gòu)洞來探測網(wǎng)絡(luò)中的最具影響力節(jié)點(diǎn)；Radicchi和Castellano[15]提出非回溯性指標(biāo)并結(jié)合滲流理論來進(jìn)行關(guān)鍵節(jié)點(diǎn)的識別.由于信息在網(wǎng)絡(luò)中的傳播,不僅與節(jié)點(diǎn)間的最短路徑有關(guān),還與節(jié)點(diǎn)間最短路徑的條數(shù)以及傳播率有關(guān).阮逸潤等[16]在文獻(xiàn)[17]的基礎(chǔ)上提出一種改進(jìn)的SP(傳播概率)指標(biāo)來評估節(jié)點(diǎn)的影響力.然而,以上對影響力節(jié)點(diǎn)的研究主要基于單個(gè)影響力節(jié)點(diǎn)來開展,但事實(shí)往往并非如此,像一些疾病、謠言或廣告的傳播可能來自多個(gè)不同的傳播源,所以網(wǎng)絡(luò)中往往存在多個(gè)影響力節(jié)點(diǎn).Hu等[18]在帶有社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)中探討了多影響力節(jié)點(diǎn)的識別問題,并發(fā)現(xiàn)每個(gè)社團(tuán)的hub點(diǎn)(大度節(jié)點(diǎn))往往具有很強(qiáng)的傳播能力.然而,當(dāng)傳播源的個(gè)數(shù)超過社團(tuán)數(shù)目時(shí),該方法將無能為力.Zhao等[19]將圖論中的著色方法引入復(fù)雜網(wǎng)絡(luò)中,提出一種多影響力節(jié)點(diǎn)的識別方法,但該方法有時(shí)不能保證傳播源間的分布足夠分散；Guo等[20]提出了改進(jìn)的著色方法.可以看出,對復(fù)雜網(wǎng)絡(luò)影響力節(jié)點(diǎn)的識別研究還處于初始階段,仍有許多問題有待進(jìn)一步改進(jìn).

多影響力節(jié)點(diǎn)識別的指導(dǎo)性思想是:選取的節(jié)點(diǎn)間的分布要較為分散,且自身要足夠重要,這樣能在保證傳播非冗余的同時(shí),使得傳播范圍盡可能的廣.但兩者之間要想同時(shí)滿足幾乎不可能,只能在兩者之間尋求一個(gè)平衡.在網(wǎng)絡(luò)的核心-邊緣(core-periphery)和社團(tuán)結(jié)構(gòu)探測中,我們提出一種統(tǒng)一的方法,即通過繪制網(wǎng)絡(luò)的區(qū)域密度曲線(region density curve),然后利用曲線的峰值點(diǎn)來確定網(wǎng)絡(luò)的核(core)節(jié)點(diǎn)或者社團(tuán)內(nèi)部的節(jié)點(diǎn),進(jìn)而用局部擴(kuò)張的方法來獲得網(wǎng)絡(luò)的核心邊緣(coreperiphery)結(jié)構(gòu)和社團(tuán)結(jié)構(gòu)[21].通過對網(wǎng)絡(luò)區(qū)域密度曲線的進(jìn)一步分析,發(fā)現(xiàn)區(qū)域密度曲線的波谷點(diǎn)正是連接核心與邊緣(core-periphery)、或者社團(tuán)和社團(tuán)之間的橋梁節(jié)點(diǎn).與其他節(jié)點(diǎn)相比,橋梁節(jié)點(diǎn)在網(wǎng)絡(luò)的傳播過程中具有很重要的影響力[22],并且分布較為分散.鑒于此,本文提出基于區(qū)域密度曲線的多影響力節(jié)點(diǎn)識別方法(RDC),并在不同的網(wǎng)絡(luò)上利用疾病和謠言兩種不同的傳播模型進(jìn)行了實(shí)驗(yàn)分析,結(jié)果表明,RDC能夠很好地識別網(wǎng)絡(luò)中的多影響力節(jié)點(diǎn),而且能夠保證選取的這些影響力節(jié)點(diǎn)之間分布較為分散,自身也足夠重要.

2 方 法

假設(shè)網(wǎng)絡(luò)是一個(gè)無權(quán)無向圖G(V,E),其中V表示網(wǎng)絡(luò)中的節(jié)點(diǎn),E表示網(wǎng)絡(luò)中的連邊.首先,給出幾種常用的中心性指標(biāo),本文將以這些作為所提方法的比較指標(biāo).

2.1 中心性指標(biāo)

度中心性(DC),被定義為節(jié)點(diǎn)的鄰居數(shù)目,即

介數(shù)中心性(BC),是以經(jīng)過某個(gè)節(jié)點(diǎn)的最短路徑的數(shù)目來刻畫節(jié)點(diǎn)的重要性指標(biāo),即

其中,njk為從節(jié)點(diǎn)j到節(jié)點(diǎn)k的最短路徑的數(shù)目,n為從節(jié)點(diǎn)j到節(jié)點(diǎn)k的條最短路徑中經(jīng)過節(jié)點(diǎn)i的最短路徑的數(shù)目.

k-shell方法(KS)的具體步驟如下:首先把網(wǎng)絡(luò)中度為1的節(jié)點(diǎn)及其所連接的邊去掉,剩下的網(wǎng)絡(luò)中會出現(xiàn)一些度為1的節(jié)點(diǎn),再將這些度為1的節(jié)點(diǎn)去掉,直到所剩的網(wǎng)絡(luò)中沒有度為1的節(jié)點(diǎn),則所有被去掉的節(jié)點(diǎn)稱為1-shell；然后繼續(xù)上面的方法,去掉剩下的網(wǎng)絡(luò)中度為2的節(jié)點(diǎn)及其相連的邊,直至不再有度值為2的節(jié)點(diǎn)為止,則這一輪所有被去除的節(jié)點(diǎn)及其連邊稱為網(wǎng)絡(luò)的2-shell.依次類推,直到所有的節(jié)點(diǎn)都被分到相應(yīng)的k-shell.

度折扣方法(DDC)是由Chen等[23]提出的,其思想是:設(shè)v是節(jié)點(diǎn)u的鄰居集,如果u已被選作傳播源,當(dāng)基于度中心性考慮v作為下一個(gè)傳播源時(shí),為避免傳播冗余,我們不應(yīng)該再考慮uv的邊,應(yīng)對v的度進(jìn)行折扣減1.

將圖論中的圖著色方法引入復(fù)雜網(wǎng)絡(luò),Zhao等[19]使用Welsh-Powell算法將網(wǎng)絡(luò)分成若干個(gè)獨(dú)立的子集,以保證每一個(gè)獨(dú)立子集中的任意兩點(diǎn)都不相連.然后基于某個(gè)中心性指標(biāo),在最大的獨(dú)立子集中選取按指定的中心性指標(biāo)排序靠前的m個(gè)節(jié)點(diǎn)作為多傳播源.在文中,我們比較了基于度中心性、介數(shù)中心性以及k-shell中心性等著色方法,分別標(biāo)記為DCC,BCC和KSC.

2.2 基于區(qū)域密度曲線的多影響力節(jié)點(diǎn)探測

首先對網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行重新排序,使連接緊密的節(jié)點(diǎn)的次序也相近；然后繪制網(wǎng)絡(luò)的區(qū)域密度曲線,并找出曲線上的波谷點(diǎn)；最后在波谷點(diǎn)兩側(cè)選取一定比例的節(jié)點(diǎn)作為影響力節(jié)點(diǎn),具體步驟如下[21].

1)對節(jié)點(diǎn)進(jìn)行排序,使連接緊密的節(jié)點(diǎn)次序也相近

定義一個(gè)初始集合U=?,初始化V′=V.U作為存儲有序序列,V′=V/U為待選集合.首先,從V中選擇一個(gè)中心性指標(biāo)比較好的節(jié)點(diǎn)N2加入到序列U中；然后,計(jì)算V′中各節(jié)點(diǎn)的C(i,U)值,C(i,U)值最大的節(jié)點(diǎn)作為節(jié)點(diǎn)序列的第二個(gè)節(jié)點(diǎn)N2,即選擇與U中節(jié)點(diǎn)的連接的數(shù)量最多的節(jié)點(diǎn)加入到U中.若同時(shí)找到兩個(gè)或兩個(gè)以上的節(jié)點(diǎn),選擇度大的節(jié)點(diǎn)添加到U中；更新V′和U,按照上面的方法依次進(jìn)行,最后可得U={u1,u2,...,uN},V′=?.

其中,aij表示節(jié)點(diǎn)i與j是否相連,如果相連aij=1,否則aij=0；d(i)是節(jié)點(diǎn)i的度,dmax是網(wǎng)絡(luò)中最大度節(jié)點(diǎn)的度.

2)繪制網(wǎng)絡(luò)的區(qū)域密度曲線

為了刻畫網(wǎng)絡(luò)中某個(gè)區(qū)域S內(nèi)部點(diǎn)的連接密度,定義S的區(qū)域密度CD(S)為

其中n′為區(qū)域S內(nèi)節(jié)點(diǎn)的數(shù)量,m′為區(qū)域S內(nèi)連接的邊的數(shù)量.

給定參數(shù)值α,即核的最小尺寸,在文中取作網(wǎng)絡(luò)的平均度.在節(jié)點(diǎn)序列U中,將排序?yàn)閞的節(jié)點(diǎn)Ur的區(qū)域密度定義為序號為r?α?1至r的節(jié)點(diǎn)組成的子圖的區(qū)域密度,即

然后,將各節(jié)點(diǎn)的區(qū)域密度繪制在二維直角坐標(biāo)系中,即獲得網(wǎng)絡(luò)的區(qū)域密度曲線(密度曲線如圖1(a)所示).在文獻(xiàn)[21]中,通過對該區(qū)域密度曲線的分析可以探測出核心-邊緣(core-periphery)結(jié)構(gòu)、社團(tuán)結(jié)構(gòu)等,而且可以找出連接不同社團(tuán)之間的橋粱節(jié)點(diǎn).基此,我們利用此方法來探測網(wǎng)絡(luò)中的多影響力節(jié)點(diǎn).

3)多影響力節(jié)點(diǎn)的選取

首先,通過上面繪制的區(qū)域密度曲線,找出處在波谷位置的節(jié)點(diǎn).注意到區(qū)域密度曲線的第1個(gè)節(jié)點(diǎn)的RD值為0,第2個(gè)會達(dá)到峰值(因?yàn)閮蓚€(gè)節(jié)點(diǎn)有連接就是全連接),故第一個(gè)節(jié)點(diǎn)的RD值不是有效值.另外,區(qū)域密度曲線的末端代表的都是些比較稀疏的節(jié)點(diǎn),與社團(tuán)以及核心邊緣結(jié)構(gòu)等沒有多大的聯(lián)系,因此選擇多傳播源時(shí),不考慮區(qū)域密度曲線這兩個(gè)波谷位置的節(jié)點(diǎn).

然后,利用區(qū)域密度曲線,計(jì)算出各谷點(diǎn)之間的節(jié)點(diǎn)數(shù),并確定各谷點(diǎn)處要選取的傳播源的個(gè)數(shù).假設(shè)要求探測m個(gè)有影響力的節(jié)點(diǎn),通過區(qū)域密度曲線觀測到波谷位置的節(jié)點(diǎn)序號為[N0,N1,...,Nk,Nk+1](其中N0和Nk+1為上面討論的兩類節(jié)點(diǎn)),同時(shí)記錄每個(gè)節(jié)點(diǎn)之間的節(jié)點(diǎn)數(shù)[n1,n2,...,nk+1](其中ni(i=1,2,...,k)代表Ni和Ni+1之間的節(jié)點(diǎn)數(shù),如下例中圖1(a)標(biāo)注的n4),則在各個(gè)谷點(diǎn)處選取傳播源個(gè)數(shù)為[m1,m2,...,mk], 其中第i(i=1,2,...,k)個(gè)谷點(diǎn)Ni處的傳播源個(gè)數(shù)mi定義為

因?yàn)槲覀兪菑墓赛c(diǎn)Ni所在位置的兩邊選取一定比例的傳播源,所以分母會出現(xiàn)系數(shù)2,相當(dāng)于 (n1+n2)+ (n2+n3)+...+ (nk?2+nk?1) + (nk?1+nk).

最后,在各個(gè)谷點(diǎn)位置的左右兩邊各選取一半比例的傳播源,利用各谷點(diǎn)確定的傳播源放在一起,即是要探測的多傳播.具體算法如下.

算法1 節(jié)點(diǎn)進(jìn)行排序

輸入:網(wǎng)絡(luò)G(V,E).

輸出:節(jié)點(diǎn)排序U(有序集合).

1)初始化:U=?,V′=V.

2)選擇最大接近中心性節(jié)點(diǎn)N2,U← N2,V′=V′/N2.

3)WHILE V′?= ?DO.

4)FOR i∈Γ(U)∪V′DO.

5)通過(1)式計(jì)算C(i,U).

6)N2=argmax(C(i,U))(若存在多個(gè)最大

i值,取度最大的節(jié)點(diǎn))

7)ENDFOR.

8)U ← N2,V′=V′/N2.

9)ENDWHILE.

算法2 尋找多個(gè)影響力節(jié)點(diǎn)

輸入:節(jié)點(diǎn)排序U多影響力節(jié)點(diǎn)的個(gè)數(shù)K.

輸出:多影響力節(jié)點(diǎn)的集合C.

1)初始化C=?.

2)FOR Ui∈U DO.

3)通過(3)式計(jì)算RD(i).

4)ENDFOR.

5)計(jì)算RD曲線的有效谷點(diǎn)序號為:[N0,N1,...,Nk,Nk+1](其中N0和Nk+1為文中討論的兩類節(jié)點(diǎn)).

6)統(tǒng)計(jì)谷點(diǎn)之間的節(jié)點(diǎn)數(shù):[n1,n2,...,nk+1].

7)通過(4)式計(jì)算每個(gè)谷點(diǎn)處要尋找的影響力節(jié)點(diǎn)的個(gè)數(shù)[m1,m2,...,mk].

8)FORi∈ [1,...,K]DO.

9)在Ni谷點(diǎn)處前后共取Mi個(gè)節(jié)點(diǎn)記為Ci.

10)C=C∪Ci.

11)ENDFOR.

其中Γ(U)表示U中所有節(jié)點(diǎn)的鄰居.下文中用RDC來表示本文提出的方法.

下面以Football網(wǎng)[24]為例來說明具體的探測方法,假設(shè)要探測的傳播源的個(gè)數(shù)m=12.首先利用(1)式,對網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行重新編號,并利用(2)式和(3)式,計(jì)算每個(gè)節(jié)點(diǎn)的區(qū)域密度.然后,以橫坐標(biāo)為節(jié)點(diǎn)序列,縱坐標(biāo)為區(qū)域密度,繪制出節(jié)點(diǎn)區(qū)域密度曲線圖,如圖1(a)所示.接下來,尋找區(qū)域密度曲線的谷點(diǎn),得到谷點(diǎn)的節(jié)點(diǎn)序列[1,77,89,115,4,36,65,22,13,43],記錄各谷點(diǎn)之間的節(jié)點(diǎn)數(shù)目,記為[15,15,15,17,14,9,9,13,8]；然后,根據(jù)(4)式計(jì)算各谷點(diǎn)處應(yīng)該選取的傳播源個(gè)數(shù),記為[2,2,2,2,1,1,1,1]；最后,在每個(gè)谷點(diǎn)的左右兩邊各取一半的傳播源,比如在第一個(gè)谷點(diǎn)77號的前面選取1個(gè),那么在77號的后面選0個(gè)傳播源,因?yàn)楣赛c(diǎn)本身就已經(jīng)作為傳播源了,以此類推,最終選取12個(gè)傳播源[96,77,37,89,84,115,85,4,36,65,22,13].圖1(c)所示為選取的影響力節(jié)點(diǎn)及其位置情況,其中紅色圓圈代表的節(jié)點(diǎn)就是我們找到的12個(gè)傳播源,可以看出,這些節(jié)點(diǎn)并不是所謂的大度節(jié)點(diǎn),恰恰相反的是,有些節(jié)點(diǎn)的度卻很小,比如圖中的37號,13號以及96號節(jié)點(diǎn),但這些節(jié)點(diǎn)往往都位于不同社團(tuán)的交界處.這也正好滿足我們所尋找傳播源的條件,傳播源之間能盡可能的分散,避免傳播的冗余.

圖1 Football網(wǎng)的多影響力節(jié)點(diǎn)識別 (a)網(wǎng)絡(luò)的區(qū)域密度曲線；(b)網(wǎng)絡(luò)的劃分情況,不同顏色代表不同的社團(tuán)；(c)紅色的節(jié)點(diǎn)為RDC方法選取的12個(gè)影響力節(jié)點(diǎn)Fig.1.Identification of multiple influential nodes on the football network:(a)Region density curve of the network；(b)original structure,where nodes with the same color are in the same community；(c)the twelve red nodes are influential nodes which are identified by the RDC method.

3 實(shí)驗(yàn)分析

3.1 傳播模型

很多文獻(xiàn)中已經(jīng)指出,節(jié)點(diǎn)的影響力是依賴于傳播的動(dòng)力學(xué)[25,26].因此,在本文分別考慮兩種疾病傳播動(dòng)力學(xué),疾病傳播的SIR模型和謠言傳播模型,進(jìn)而更全面地來比較不同傳播源探測方法.

在疾病傳播模型中,網(wǎng)絡(luò)中的節(jié)點(diǎn)分為三類,易感者(S),感染者(I),恢復(fù)者(R).一個(gè)感染者(I)以一定的傳播率將疾病傳染給易感的鄰居(S),傳播完自己的所有鄰居后,感染者以一定的恢復(fù)率變?yōu)榛謴?fù)者[27].在這里,為了更清晰地區(qū)分不同的傳播源探測方法,僅考慮每個(gè)感染者每次僅與一個(gè)鄰居接觸,即單傳的SIR模型.

在謠言傳播模型中,將網(wǎng)絡(luò)節(jié)點(diǎn)分為三類,無知者(S),傳播者(I),已知者(R).一個(gè)傳播者(I)以一定的概率將謠言傳播給相鄰的無知者(S),當(dāng)傳播者接觸到另一個(gè)傳播者或已知者時(shí),最初的傳播者就會失去傳播謠言的興趣,以一定的概率變?yōu)橐阎遊28].本文考慮恢復(fù)率μ=0.1的情況.

3.2 數(shù)據(jù)描述

將不同的多影響力節(jié)點(diǎn)識別方法在六個(gè)真實(shí)網(wǎng)絡(luò)中進(jìn)行比較,包括Email,Yeast,SciMet,Kohonen,HEP,PGP.表1是網(wǎng)絡(luò)的一些基本信息,其中N,M為網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)和邊數(shù),?k?和C為網(wǎng)絡(luò)的平均度和聚類系數(shù),L和D為網(wǎng)絡(luò)的平均短路徑長度和直徑[29].

表1 網(wǎng)絡(luò)的基本信息表Fig.1.Basic structural properties for networks.

3.3 結(jié) 果

為便于比較不同的多影響力節(jié)點(diǎn)識別方法,首先選取m個(gè)傳播源,然后分別依據(jù)SIR疾病傳播、遙言傳播模型,去模擬網(wǎng)絡(luò)的動(dòng)力學(xué)過程,直到網(wǎng)絡(luò)中沒有處于感染態(tài)的節(jié)點(diǎn),最后以網(wǎng)絡(luò)中恢復(fù)節(jié)點(diǎn)的比例來衡量識別方法的性能.為了保證實(shí)驗(yàn)結(jié)果的可靠性,對傳播過程文中進(jìn)行了100次平均.

為便于比較不同方法的結(jié)果,定義一個(gè)相對比率指標(biāo)?如下[19]:

其中,Ri表示在某種傳播源識別方法(如DCC,KS,KSC,BC,BCC,DDC,RDC)下最終恢復(fù)節(jié)點(diǎn)的比例,RDC是采用度中心性方法時(shí)最終恢復(fù)節(jié)點(diǎn)的比例.?＞0意味著當(dāng)前使用的方法要優(yōu)于度中心性的方法,?＞0的值越大表示當(dāng)前方法的優(yōu)勢越明顯.

首先,利用SIR疾病傳播模型,在六個(gè)實(shí)際網(wǎng)絡(luò)上對不同的識別方法進(jìn)行比較.實(shí)驗(yàn)結(jié)果表明,面對SIR疾病傳播時(shí),本文提出的基于區(qū)域密度曲線的識別方法(RDC)都要優(yōu)于其他方法,尤其是當(dāng)傳播率較小時(shí),優(yōu)勢非常明顯.即使傳播率增大到一定程度,RDC方法還是要優(yōu)于其他方法.另外,隨著選取的傳播源個(gè)數(shù)的增多,這種優(yōu)勢越發(fā)明顯(見圖2和圖3).圖2是在SIR疾病傳播模型下,不同識別方法相對于度中心性指標(biāo)所得的結(jié)果,其中傳播率β從0.05到0.5,每次增加0.05,恢復(fù)率μ=0.1. 圖2(a)—(f),(g)—(l),(m)—(r)表示傳播過程中選取的傳播源個(gè)數(shù)分別為30,50,90.

緊接著,在上面的六個(gè)實(shí)際網(wǎng)絡(luò)上,考慮了不同識別方法在謠言傳播模型中的效果.實(shí)驗(yàn)結(jié)果表明,在謠言傳播機(jī)理下,RDC方法仍然要優(yōu)于其他的多影響力節(jié)點(diǎn)識別方法.隨著選取的傳播源個(gè)數(shù)的增加,RDC方法的優(yōu)勢越發(fā)明顯.圖3是在謠言傳播模型下的實(shí)驗(yàn)結(jié)果,參數(shù)的設(shè)定與SIR疾病傳播模型下的相同.圖3(a)—(f),(g)—(l),(m)—(r)表示傳播過程中選取的傳播源個(gè)數(shù)分別為30,50,90.

接下來,研究不同識別方法所得的影響力節(jié)點(diǎn)之間的平均距離和平均度的情況.圖4是考慮不同識別方法所獲取的影響力節(jié)點(diǎn)之間的平均距離隨傳播源個(gè)數(shù)的變化情況,其中傳播源的個(gè)數(shù)m是從20開始,每次增加20,一直到200.可以看出,相比較于其他識別方法,利用RDC方法選取的傳播源之間的平均距離要大很多,并隨選取的傳播源個(gè)數(shù)的增加,平均距離呈現(xiàn)增大的趨勢.由此可以看出,RDC方法獲取的傳播源彼此之間較為分散,能夠很好地避免傳播的冗余.

圖2 對于SIR疾病傳播模型,不同識別方法與疾病傳播率之間的關(guān)系Fig.2.For SIR model,the relative ratios? for different indices as functions of transmission rate β are compared in six real networks.

圖3 對于謠言傳播模型,不同識別方法與疾病傳播率之間的關(guān)系Fig.3.For rumor propagation model,the relative ratios ? for different indices as functions of transmission rate β are compared in six real networks.

圖5是不同識別方法所獲取的影響力節(jié)點(diǎn)的平均度隨傳播源個(gè)數(shù)的變化情況,其中傳播源個(gè)數(shù)m的設(shè)定與圖4相同.可以看出,RDC方法選取的傳播源的平均度要小于其他的識別方法.由選取傳播源的指導(dǎo)思想可知,傳播源間的分布分散和自身重要兩者不可兼得.雖然RDC方法選取的傳播源的平均度比其他方法都要小,但從圖5中的藍(lán)色虛直線(即網(wǎng)絡(luò)的平均度)可以看出,選擇的這些傳播源不是“不重要”的節(jié)點(diǎn),這些節(jié)點(diǎn)的平均度比各自網(wǎng)絡(luò)的平均度都要大.而且隨著選取的傳播源個(gè)數(shù)的增加,RDC方法的平均度基本保持不變.由此可以看出,RDC方法選取的傳播源彼此間分布較分散,而且各個(gè)傳播源自身也比較重要.

圖5 不同方法選取的傳播源的平均度與傳播源數(shù)量間的關(guān)系,其中藍(lán)色虛線代表每個(gè)網(wǎng)絡(luò)的平均度Fig.5.The effects of the number of multiple spreaders m on the average degree ?k?mare compared in six real networks.Dotted line in each subfigure denotes the average degree of the network.

圖6和圖7討論了不同的參數(shù)α對傳播模型的影響,紅色方框中的部分是本文采用的α值,可以發(fā)現(xiàn)隨著α的變化,傳播范圍會呈現(xiàn)一定的無規(guī)則的波動(dòng).因此本文采用了文獻(xiàn)[21]提供的默認(rèn)參數(shù)平均度,雖然不是在所有的網(wǎng)絡(luò)都是最優(yōu)的,但是總體表現(xiàn)較好.

圖6 對于SIR傳播模型,不同傳播率下參數(shù)α與相對比率?的關(guān)系Fig.6.For SIR model,the effects of parameter α on the relative ratios ? for different transmission rates β are compared in six real networks.

圖7 對于謠言傳播模型,不同傳播率下參數(shù)α與相對比率?的關(guān)系Fig.7.For rumor propagation model,the effects of parameter α on the relative ratios? for different transmission rates β are compared in six real networks.

4 結(jié) 論

多影響力節(jié)點(diǎn)識別的指導(dǎo)性思想是:選取的節(jié)點(diǎn)彼此間的分布要較為分散,而且自身要足夠重要,但兩者不可兼得.本文提出一種基于網(wǎng)絡(luò)區(qū)域密度曲線的多影響力節(jié)點(diǎn)識別方法,該方法基于網(wǎng)絡(luò)的局部信息,計(jì)算的時(shí)間復(fù)雜度較低.應(yīng)用兩種不同的傳播動(dòng)力學(xué)模型,在六個(gè)真實(shí)網(wǎng)絡(luò)上進(jìn)行了數(shù)據(jù)實(shí)驗(yàn),結(jié)果表明本文提出的識別方法要優(yōu)于其他的識別方法,而且選中的影響力節(jié)點(diǎn)之間的分布較為分散,自身也較為重要.本文僅考慮無向無權(quán)網(wǎng)絡(luò),下一步可考慮將本文的方法推廣至有向有權(quán)網(wǎng)絡(luò)中.