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

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

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

1 引 言

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

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

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

2 方 法

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

2.1 中心性指標

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

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

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

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

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

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

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

首先對網絡中的節(jié)點進行重新排序,使連接緊密的節(jié)點的次序也相近；然后繪制網絡的區(qū)域密度曲線,并找出曲線上的波谷點；最后在波谷點兩側選取一定比例的節(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é)點的連接的數量最多的節(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是網絡中最大度節(jié)點的度.

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

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

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

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

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

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

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

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

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

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

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

輸入:網絡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é)點的個數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é)點數:[n1,n2,...,nk+1].

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

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

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

10)C=C∪Ci.

11)ENDFOR.

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

下面以Football網[24]為例來說明具體的探測方法,假設要探測的傳播源的個數m=12.首先利用(1)式,對網絡節(jié)點進行重新編號,并利用(2)式和(3)式,計算每個節(jié)點的區(qū)域密度.然后,以橫坐標為節(jié)點序列,縱坐標為區(qū)域密度,繪制出節(jié)點區(qū)域密度曲線圖,如圖1(a)所示.接下來,尋找區(qū)域密度曲線的谷點,得到谷點的節(jié)點序列[1,77,89,115,4,36,65,22,13,43],記錄各谷點之間的節(jié)點數目,記為[15,15,15,17,14,9,9,13,8]；然后,根據(4)式計算各谷點處應該選取的傳播源個數,記為[2,2,2,2,1,1,1,1]；最后,在每個谷點的左右兩邊各取一半的傳播源,比如在第一個谷點77號的前面選取1個,那么在77號的后面選0個傳播源,因為谷點本身就已經作為傳播源了,以此類推,最終選取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網的多影響力節(jié)點識別 (a)網絡的區(qū)域密度曲線；(b)網絡的劃分情況,不同顏色代表不同的社團；(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 傳播模型

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

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

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

3.2 數據描述

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

表1 網絡的基本信息表Fig.1.Basic structural properties for networks.

3.3 結 果

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

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

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

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

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

接下來,研究不同識別方法所得的影響力節(jié)點之間的平均距離和平均度的情況.圖4是考慮不同識別方法所獲取的影響力節(jié)點之間的平均距離隨傳播源個數的變化情況,其中傳播源的個數m是從20開始,每次增加20,一直到200.可以看出,相比較于其他識別方法,利用RDC方法選取的傳播源之間的平均距離要大很多,并隨選取的傳播源個數的增加,平均距離呈現增大的趨勢.由此可以看出,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é)點的平均度隨傳播源個數的變化情況,其中傳播源個數m的設定與圖4相同.可以看出,RDC方法選取的傳播源的平均度要小于其他的識別方法.由選取傳播源的指導思想可知,傳播源間的分布分散和自身重要兩者不可兼得.雖然RDC方法選取的傳播源的平均度比其他方法都要小,但從圖5中的藍色虛直線(即網絡的平均度)可以看出,選擇的這些傳播源不是“不重要”的節(jié)點,這些節(jié)點的平均度比各自網絡的平均度都要大.而且隨著選取的傳播源個數的增加,RDC方法的平均度基本保持不變.由此可以看出,RDC方法選取的傳播源彼此間分布較分散,而且各個傳播源自身也比較重要.

圖5 不同方法選取的傳播源的平均度與傳播源數量間的關系,其中藍色虛線代表每個網絡的平均度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討論了不同的參數α對傳播模型的影響,紅色方框中的部分是本文采用的α值,可以發(fā)現隨著α的變化,傳播范圍會呈現一定的無規(guī)則的波動.因此本文采用了文獻[21]提供的默認參數平均度,雖然不是在所有的網絡都是最優(yōu)的,但是總體表現較好.

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

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