基于區(qū)域密度曲線識別網(wǎng)絡上的多影響力節(jié)點?

康玲 項冰冰 翟素蘭 鮑中奎 張海峰

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

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

1 引 言

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

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

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

2 方 法

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

2.1 中心性指標

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

因為我們是從谷點Ni所在位置的兩邊選取一定比例的傳播源,所以分母會出現(xiàn)系數(shù)2,相當于 (n1+n2)+ (n2+n3)+...+ (nk?2+nk?1) + (nk?1+nk).

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

算法1 節(jié)點進行排序

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

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

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

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

3)WHILE V′?= ?DO.

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

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

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

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

7)ENDFOR.

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

9)ENDWHILE.

算法2 尋找多個影響力節(jié)點

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

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

1)初始化C=?.

2)FOR Ui∈U DO.

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

4)ENDFOR.

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

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

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

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

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

10)C=C∪Ci.

11)ENDFOR.

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

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

圖1 Football網(wǎng)的多影響力節(jié)點識別 (a)網(wǎng)絡的區(qū)域密度曲線；(b)網(wǎng)絡的劃分情況,不同顏色代表不同的社團；(c)紅色的節(jié)點為RDC方法選取的12個影響力節(jié)點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 實驗分析

3.1 傳播模型

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

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

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

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

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

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

3.3 結 果

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

為便于比較不同方法的結果,定義一個相對比率指標?如下[19]:

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

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

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

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

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

圖3 對于謠言傳播模型,不同識別方法與疾病傳播率之間的關系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é)點的平均度隨傳播源個數(shù)的變化情況,其中傳播源個數(shù)m的設定與圖4相同.可以看出,RDC方法選取的傳播源的平均度要小于其他的識別方法.由選取傳播源的指導思想可知,傳播源間的分布分散和自身重要兩者不可兼得.雖然RDC方法選取的傳播源的平均度比其他方法都要小,但從圖5中的藍色虛直線(即網(wǎng)絡的平均度)可以看出,選擇的這些傳播源不是“不重要”的節(jié)點,這些節(jié)點的平均度比各自網(wǎng)絡的平均度都要大.而且隨著選取的傳播源個數(shù)的增加,RDC方法的平均度基本保持不變.由此可以看出,RDC方法選取的傳播源彼此間分布較分散,而且各個傳播源自身也比較重要.

圖5 不同方法選取的傳播源的平均度與傳播源數(shù)量間的關系,其中藍色虛線代表每個網(wǎng)絡的平均度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ī)則的波動.因此本文采用了文獻[21]提供的默認參數(shù)平均度,雖然不是在所有的網(wǎng)絡都是最優(yōu)的,但是總體表現(xiàn)較好.

圖6 對于SIR傳播模型,不同傳播率下參數(shù)α與相對比率?的關系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ù)α與相對比率?的關系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é)點彼此間的分布要較為分散,而且自身要足夠重要,但兩者不可兼得.本文提出一種基于網(wǎng)絡區(qū)域密度曲線的多影響力節(jié)點識別方法,該方法基于網(wǎng)絡的局部信息,計算的時間復雜度較低.應用兩種不同的傳播動力學模型,在六個真實網(wǎng)絡上進行了數(shù)據(jù)實驗,結果表明本文提出的識別方法要優(yōu)于其他的識別方法,而且選中的影響力節(jié)點之間的分布較為分散,自身也較為重要.本文僅考慮無向無權網(wǎng)絡,下一步可考慮將本文的方法推廣至有向有權網(wǎng)絡中.