基于DynamicRank的重要節(jié)點(diǎn)集挖掘算法

朱 華，潘 侃，王 磊，陳端兵,3

(1.云南電網(wǎng)有限責(zé)任公司電力科學(xué)研究院 昆明 650217；2.成都數(shù)之聯(lián)科技股份有限公司 成都 610041；3.電子科技大學(xué)大數(shù)據(jù)研究中心 成都 611731)

0 引 言

現(xiàn)實(shí)生活中，很多復(fù)雜系統(tǒng)如社交、城市交通等網(wǎng)絡(luò)，都可以用圖表示。這些網(wǎng)絡(luò)中，社交網(wǎng)絡(luò)里的官方賬號(hào)、城市交通網(wǎng)絡(luò)里的交通樞紐等少數(shù)節(jié)點(diǎn)對(duì)信息擴(kuò)散起到了關(guān)鍵作用[1]。提早發(fā)現(xiàn)這類關(guān)鍵節(jié)點(diǎn)，一方面，可利用其高影響力加速信息傳播，如產(chǎn)品推廣信息的傳播；另一方面，也能有效地監(jiān)控和預(yù)防現(xiàn)實(shí)生活中可能出現(xiàn)的各種突發(fā)狀況，如社交網(wǎng)絡(luò)中的謠言傳播、交通網(wǎng)絡(luò)中重要路口堵塞導(dǎo)致交通系統(tǒng)癱瘓等。單個(gè)關(guān)鍵節(jié)點(diǎn)的影響力是有限的，一組關(guān)鍵節(jié)點(diǎn)在相互促進(jìn)下會(huì)造成更為廣泛的影響。因此，找到重要傳播源(種子節(jié)點(diǎn)集)對(duì)信息傳播與控制具有重要作用。

在復(fù)雜網(wǎng)絡(luò)中識(shí)別一組有影響力的傳播者，有一種簡(jiǎn)單的方法是依據(jù)節(jié)點(diǎn)重要性排序結(jié)果[2-3]選擇top-K節(jié)點(diǎn)作為初始傳播源(種子集)。目前已有很多節(jié)點(diǎn)重要性排序算法，歸納起來(lái)可分為兩類。一類是基于結(jié)構(gòu)特征的指標(biāo)和方法，通過(guò)捕捉節(jié)點(diǎn)之間的局部連邊信息或路徑信息，衡量節(jié)點(diǎn)的重要性，例如度中心性(Degree)、K-shell中心性[4]和H-index[5]中心性；另外一類是基于路徑和全局隨機(jī)游走的方法[6-8]，利用整個(gè)圖的拓?fù)湫畔⑼诰蛑匾?jié)點(diǎn)。在不考慮時(shí)間開(kāi)銷的前提下，從初始節(jié)點(diǎn)出發(fā)將信息傳播出去，當(dāng)隨機(jī)游走趨于穩(wěn)定時(shí)，信息保留越多的節(jié)點(diǎn)就越重要。

文獻(xiàn)[9]將復(fù)雜網(wǎng)絡(luò)中一組重要節(jié)點(diǎn)識(shí)別問(wèn)題定義為影響力最大化問(wèn)題，提出了獨(dú)立級(jí)聯(lián)(independent cascade，IC)模型和線性閾值(linear threshold，LT)模型兩種求解方法。IC模型假定傳播激活的獨(dú)立性，每個(gè)活躍的節(jié)點(diǎn)以一定概率激活其不活躍的鄰居，而不受其他活躍節(jié)點(diǎn)的影響。LT模型考慮鄰居的聯(lián)合激活，如果一個(gè)非活動(dòng)節(jié)點(diǎn)的活躍鄰居的權(quán)重之和超過(guò)給定閾值，該節(jié)點(diǎn)將被激活。

IC模型利用傳統(tǒng)重要節(jié)點(diǎn)排序方法挖掘重要節(jié)點(diǎn)集，只考慮每個(gè)節(jié)點(diǎn)獨(dú)立的影響力。但是，在影響力傳播過(guò)程中，節(jié)點(diǎn)集內(nèi)的節(jié)點(diǎn)存在相互促進(jìn)和補(bǔ)充的關(guān)系，考慮節(jié)點(diǎn)集內(nèi)部關(guān)系的方法更符合實(shí)際。因此，本文基于DynamicRank[10]方法的單節(jié)點(diǎn)影響力概率計(jì)算模型，提出了多種子節(jié)點(diǎn)的級(jí)聯(lián)傳播概率計(jì)算方法，以捕捉種子集內(nèi)部對(duì)信息傳播的積極促進(jìn)影響。同時(shí)，大多數(shù)貪心策略都存在一個(gè)問(wèn)題，即某些傳播者距離太近，以至于它們的影響可能重疊。因此，在DynamicRank概率排序模型基礎(chǔ)上，本文改進(jìn)純粹貪心迭代策略，降低種子集里重疊鄰居對(duì)影響力傳播帶來(lái)的消極影響，優(yōu)先從種子節(jié)點(diǎn)鄰居以外的節(jié)點(diǎn)中選擇候選節(jié)點(diǎn)。通過(guò)考慮種子集內(nèi)部各節(jié)點(diǎn)之間相互促進(jìn)和抑制2個(gè)方面的影響，挖掘出更高影響力的種子集。相較于目前應(yīng)用較多的基于重要節(jié)點(diǎn)排序方法(K-shell[4]，Degree，H-index[5]，DynamicRank[10])和重要節(jié)點(diǎn)集挖掘方法(VoteRank[11]，EnRenew[12])，本文提出的方法能更準(zhǔn)確、更有效地識(shí)別復(fù)雜網(wǎng)絡(luò)中高影響力節(jié)點(diǎn)集。在4個(gè)實(shí)際網(wǎng)絡(luò)上的實(shí)驗(yàn)表明，本文方法選出的節(jié)點(diǎn)集具有更好的信息擴(kuò)散能力，在Grid數(shù)據(jù)集上，相較于其他基準(zhǔn)方法，本文方法的傳播范圍平均提升了49.3%。

1 相關(guān)工作

針對(duì)影響力最大化問(wèn)題，研究者提出了各種啟發(fā)式算法。例如，文獻(xiàn)[13]提出了一種基于IC模型的Degree-discount啟發(fā)式方法。其基本思想是，在計(jì)算種子集影響力時(shí)，如果節(jié)點(diǎn)v的鄰居節(jié)點(diǎn)u被選為種子節(jié)點(diǎn)，由于兩者的影響力存在重疊，則需要對(duì)節(jié)點(diǎn)v的度數(shù)進(jìn)行度量折扣。文獻(xiàn)[14]考慮弱連接因素，提出了一種通過(guò)將最大化問(wèn)題映射為最優(yōu)滲濾問(wèn)題的集體優(yōu)化方法。

采用貪心算法求解影響力最大化問(wèn)題也是主流研究方向之一，其核心是在每次迭代中選擇當(dāng)前影響力最大的節(jié)點(diǎn)集。在不降低精度的情況下，文獻(xiàn)[15]設(shè)計(jì)了一種改進(jìn)的貪心策略，利用目標(biāo)函數(shù)的子模數(shù)，將計(jì)算代價(jià)降低了兩個(gè)數(shù)量級(jí)。文獻(xiàn)[16]平衡了精度和時(shí)間復(fù)雜度，設(shè)計(jì)了一種離散的貪心求解算法，利用本地網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息，有效識(shí)別最大影響力的節(jié)點(diǎn)集。文獻(xiàn)[11]提出了一種簡(jiǎn)單有效的組節(jié)點(diǎn)選擇方法VoteRank，它通過(guò)投票策略選擇最有影響力的節(jié)點(diǎn)集。VoteRank使用迭代選擇策略，充分利用了節(jié)點(diǎn)的局部信息但忽略了邊的信息。文獻(xiàn)[17]在此基礎(chǔ)上提出了WvoteRank以提升在帶權(quán)圖中重要節(jié)點(diǎn)集挖掘的準(zhǔn)確性。文獻(xiàn)[12]進(jìn)一步利用節(jié)點(diǎn)間的差異，提出了一種基于節(jié)點(diǎn)信息熵的啟發(fā)式算法EnRenew以選擇一組高影響力的節(jié)點(diǎn)。在信息傳播概率函數(shù)的幫助下，文獻(xiàn)[18]根據(jù)所選節(jié)點(diǎn)的局部路徑降低其他節(jié)點(diǎn)的得分，提出了一種基于重排序的方法Re-Rank來(lái)挖掘一組重要節(jié)點(diǎn)集。

2 基于DynamicRank的重要節(jié)點(diǎn)集挖掘方法

本文研究主要針對(duì)無(wú)向無(wú)權(quán)圖G(V,E)。其中，V={v1,v2,…,vn}是節(jié)點(diǎn)集合，E={e1,e2,…,em}是邊集合，n和m分別是節(jié)點(diǎn)數(shù)量和邊數(shù)量，直接與節(jié)點(diǎn)v相連的一階鄰居記為Γ1(v)。為了方便描述，拓展鄰居的定義如下。

定義1高階鄰居。若v是節(jié)點(diǎn)y的一階鄰居，節(jié)點(diǎn)y屬于節(jié)點(diǎn)u的i-1階鄰居Γi-1(u)，那么節(jié)點(diǎn)u的i階鄰居定義為

Γi(u)={v|v∈Γ1(y),y∈Γi-1(u),

v?Γi-1(u),v?Γi-2(u)}

(1)

定義2節(jié)點(diǎn)集的高階鄰居。節(jié)點(diǎn)集S的i階鄰居Γi(S)定義為

(2)

2.1 DynamicRank節(jié)點(diǎn)重要性排序方法

DynamicRank算法利用概率傳播模型，信息以中心節(jié)點(diǎn)為初始傳播源向外傳播，在i階鄰域內(nèi)的所有節(jié)點(diǎn)的感染概率之和反映了該中心節(jié)點(diǎn)的影響力。概率傳播模型中，節(jié)點(diǎn)信息往往都是從低階鄰居向高階鄰居傳播。對(duì)于一個(gè)無(wú)向無(wú)權(quán)圖G(V,E)，假設(shè)節(jié)點(diǎn)u為初始感染節(jié)點(diǎn)，x是節(jié)點(diǎn)u的i-1階鄰居，y是節(jié)點(diǎn)u的i階鄰居。當(dāng)節(jié)點(diǎn)x與y直接相連時(shí)，節(jié)點(diǎn)y將以β的概率被x感染。節(jié)點(diǎn)y被x感染的概率為p+(y|x)=βp+(x)。因此，在初始節(jié)點(diǎn)u的影響下，i階鄰居y不被感染的概率為

(3)

節(jié)點(diǎn)y被感染的概率為

p+(y|u)=1-p-(y|u)

(4)

(3)—(4)式中，中心節(jié)點(diǎn)是u，其初始感染概率為p+(u)=1。

從一個(gè)中心節(jié)點(diǎn)u出發(fā)，在給定鄰域范圍(本文取3階鄰域)下，中心節(jié)點(diǎn)u的影響力為u的3階以內(nèi)鄰居被感染的概率之和，計(jì)算公式為

(5)

2.2 基于DynamicRank的重要節(jié)點(diǎn)集純粹貪心選擇策略

貪心選擇的核心就是計(jì)算節(jié)點(diǎn)集的影響力，而一組節(jié)點(diǎn)的影響力是由種子集中多個(gè)節(jié)點(diǎn)共同決定的。若當(dāng)前的節(jié)點(diǎn)集為S，鄰域內(nèi)節(jié)點(diǎn)y受到節(jié)點(diǎn)集S影響而被感染的概率為

(6)

基于此，節(jié)點(diǎn)集S的影響力可以定義為

(7)

2.3 重要節(jié)點(diǎn)集選擇的增強(qiáng)貪心性選擇策略

當(dāng)一個(gè)節(jié)點(diǎn)u被選為信息的傳播源時(shí)，如果u附近的節(jié)點(diǎn)v1再次被選為傳播源，那么傳播范圍增益很小。因此，最好選擇相距較遠(yuǎn)的節(jié)點(diǎn)v2，以盡可能多地影響周圍的節(jié)點(diǎn)，如圖1所示。也就是說(shuō)，在一個(gè)節(jié)點(diǎn)被選為傳播源后，它的鄰居和鄰居的鄰居被選為傳播源的概率應(yīng)該降低，因此，在每次迭代過(guò)程中，從種子集鄰居以外的節(jié)點(diǎn)集選擇候選節(jié)點(diǎn)，更為合理科學(xué)。

圖1 具有重疊鄰居的種子集選擇策略示意圖Fig.1 Illustration of seeds selection strategy with overlapping neighbors

在利用純粹貪心策略選擇候選節(jié)點(diǎn)時(shí)，可能會(huì)選擇到種子集S的一階鄰居節(jié)點(diǎn)，由于鄰居節(jié)點(diǎn)u與種子節(jié)點(diǎn)直接相連，u有很大概率被種子節(jié)點(diǎn)感染，選取u作為種子節(jié)點(diǎn)意義不大。因此，在純粹貪心基礎(chǔ)上，提出一種增強(qiáng)的貪心選擇策略。候選節(jié)點(diǎn)優(yōu)先從種子集鄰居以外的節(jié)點(diǎn)集V-Γ1(S)中選擇。特別地，當(dāng)圖中所有節(jié)點(diǎn)都是S的鄰居即V-Γ1(S)=Φ時(shí)，從圖中去除當(dāng)前種子集的節(jié)點(diǎn)及其連邊得到新的圖G′。然后，從G′中按上述策略挑選重要節(jié)點(diǎn)加入種子集，具體步驟如下。

1)給定種子集規(guī)模M，根據(jù)DynamicRank排序算法計(jì)算所有節(jié)點(diǎn)的重要性分?jǐn)?shù)，選取分值最高的節(jié)點(diǎn)vmax加入種子集S={vmax}。

4)若|S|=M，輸出最終的種子集S，結(jié)束。否則，若V-Γ1(S)≠Φ，直接返回步驟2繼續(xù)執(zhí)行；若V-Γ1(S)=Φ，則在圖中去除種子集S中的節(jié)點(diǎn)及其連邊，再返回步驟2)繼續(xù)執(zhí)行。

圖2為純粹貪心與增強(qiáng)貪心的重要節(jié)點(diǎn)集選擇對(duì)比的示意圖。為了說(shuō)明增強(qiáng)貪心算法的優(yōu)勢(shì)，對(duì)圖2中的網(wǎng)絡(luò)分別用純粹貪心和增強(qiáng)貪心兩種策略選擇規(guī)模M=5的重要節(jié)點(diǎn)集。兩種方法都利用DynamicRank選出影響力最高的節(jié)點(diǎn)v14作為初始的種子集。經(jīng)過(guò)5次迭代選擇，純粹貪心策略選出的種子集為S1={14,8,12,22,1}，有4個(gè)節(jié)點(diǎn)在社區(qū)1，1個(gè)節(jié)點(diǎn)在社區(qū)2，信息從這組節(jié)點(diǎn)出發(fā)很難傳播到社區(qū)3，實(shí)際上，以這組節(jié)點(diǎn)為初始感染節(jié)點(diǎn)，用SIR傳播模型仿真得到的傳播規(guī)模為11.892(計(jì)算方法見(jiàn)3.1)。而采用增強(qiáng)貪心選擇策略選出的種子集為S2={14,8,22,9,27}，種子節(jié)點(diǎn)分散在3個(gè)社區(qū)中，以S2為初始感染節(jié)點(diǎn)，用SIR傳播模型仿真得到的傳播規(guī)模為12.362。顯然，增強(qiáng)的貪心策略能挖掘出影響力更大的種子集。

圖2 純粹貪心與增強(qiáng)貪心的重要節(jié)點(diǎn)集選擇對(duì)比Fig.2 Comparison of important node set selection for pure greedy and enhanced greedy strategies

3 實(shí)驗(yàn)與討論

論文利用4個(gè)真實(shí)網(wǎng)絡(luò)對(duì)提出的方法進(jìn)行了測(cè)試，并和已有的重要節(jié)點(diǎn)挖掘方法進(jìn)行了對(duì)比分析，包括度中心性(Degree)、 K-shell中心性[4]、H-index中心性[5]、DynamicRank[10]以及重要節(jié)點(diǎn)集挖掘方法VoteRank[11]和 EnRenew[12]。另外，本文方法也和度中心性與K-shell中心性方法的改進(jìn)版本Degree_non和K-shell_non進(jìn)行了對(duì)比，即：當(dāng)選擇一個(gè)節(jié)點(diǎn)作為種子節(jié)點(diǎn)后，它的鄰居將不會(huì)再選為種子節(jié)點(diǎn)[11]。

3.1 傳播模型與評(píng)估方法

(8)

(8)式中：tc是傳播達(dá)到穩(wěn)態(tài)的時(shí)間；nR(tc)是傳播到穩(wěn)態(tài)時(shí)的康復(fù)節(jié)點(diǎn)數(shù)目；n是網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)。

3.2 數(shù)據(jù)集

本文選擇了4個(gè)真實(shí)網(wǎng)絡(luò)進(jìn)行測(cè)試和對(duì)比。4個(gè)網(wǎng)絡(luò)包括：Email[20]，是Rovirai Virgili大學(xué)成員之間的電子郵件交換網(wǎng)絡(luò)；Grid[21]，是美國(guó)西部的某電力網(wǎng)絡(luò)；Yeast[22]，是酵母中的蛋白質(zhì)相互作用的無(wú)向網(wǎng)絡(luò)；Vidal[23]，是表示人類蛋白質(zhì)相互作用的網(wǎng)絡(luò)。這4個(gè)真實(shí)網(wǎng)絡(luò)的基本結(jié)構(gòu)特征如表1所示。表1中：n是節(jié)點(diǎn)數(shù)目；m是邊數(shù)目；〈k〉表示所有節(jié)點(diǎn)的平均度；kmax代表節(jié)點(diǎn)的最大度；〈c〉為所有節(jié)點(diǎn)的平均聚集系數(shù)。

表1 真實(shí)網(wǎng)絡(luò)基本結(jié)構(gòu)特征數(shù)據(jù)Tab.1 Basic structuralproperties of real networks

3.3 實(shí)驗(yàn)及分析

為了比較各個(gè)重要節(jié)點(diǎn)挖掘方法的效果，本文實(shí)驗(yàn)對(duì)不同重要節(jié)點(diǎn)挖掘算法的種子集進(jìn)行了500次SIR傳播仿真實(shí)驗(yàn)，并將500次的平均F(tc)值作為該種子集的影響力。實(shí)驗(yàn)中設(shè)置DynamicRank模型的傳播概率和SIR仿真中的傳染概率均為β=1.2βc。表2顯示了不同重要節(jié)點(diǎn)挖掘算法所得種子集的平均傳播規(guī)模。相比于已有的基于重要節(jié)點(diǎn)排序的重要節(jié)點(diǎn)集挖掘方法Degree、Degree_non、K-shell、 K-shell_non、H-index、DynamicRank，基于投票策略的VoteRank方法，以及基于節(jié)點(diǎn)信息熵的EnRenew方法，本文提出的方法在4個(gè)數(shù)據(jù)集上都取得了最好的結(jié)果。特別地，在Grid數(shù)據(jù)集上，本論文所提方法的影響規(guī)模明顯高于現(xiàn)有的重要節(jié)點(diǎn)集挖掘算法，傳播范圍較上述算法平均提升了49.3%。本文方法挖掘出的種子節(jié)點(diǎn)集影響的節(jié)點(diǎn)規(guī)模可達(dá)到0.121，比較有競(jìng)爭(zhēng)力的VoteRank、EnRenew、Degree_non的影響規(guī)模分別為0.113、0.101、0.112。3種方法平均影響規(guī)模為0.108，本文方法選出的重要節(jié)點(diǎn)集其影響規(guī)模提升了11.7%；同時(shí)，直接基于DynamicRank方法排序結(jié)果選出的種子集，其傳播規(guī)模只有0.065，本文利用級(jí)聯(lián)概率計(jì)算和增強(qiáng)貪心策略優(yōu)化后，挖掘出的種子集的傳播規(guī)模大幅度提升了86%。這說(shuō)明，改進(jìn)DynamicRank中的獨(dú)立傳染概率的級(jí)聯(lián)概率計(jì)算方法能更加有效地衡量種子集的影響力，在貪心選擇過(guò)程中能挖掘出更高影響力的種子集。

表2 SIR模型仿真結(jié)果F(tc)Tab.2 Simulation results F(tc) according to SIR model

圖3為不同種子集規(guī)模下不同算法的性能對(duì)比。由圖3可見(jiàn)，在不同種子集規(guī)模下，相對(duì)于現(xiàn)有的重要節(jié)點(diǎn)集挖掘算法，本文提出的方法取得了更好的結(jié)果。在大部分情況下，本文提出的方法都取得了最好的效果。當(dāng)規(guī)模逐漸變大時(shí)，VoteRank和Degree_non等方法與本文方法相當(dāng)，都能挖掘出圖中影響力較大的關(guān)鍵節(jié)點(diǎn)集。

為了驗(yàn)證本文學(xué)習(xí)模型的魯棒性，對(duì)比分析各方法在不同感染概率下的傳播規(guī)模，如圖4所示。感染概率β=cβc，隨著系數(shù)c的增長(zhǎng)，感染概率β相應(yīng)增加。由圖4可見(jiàn)，在4個(gè)網(wǎng)絡(luò)中，種子集的影響力隨著系數(shù)c的增加而不斷擴(kuò)大。K-shell、DynamicRank和H-index方法的增長(zhǎng)相對(duì)平緩，而本文提出的算法與VoteRank、Enrenew、Degree_non以及K-shell_non方法增長(zhǎng)趨勢(shì)基本一致，增長(zhǎng)相對(duì)快速。

圖3 不同初始化種子集大小下的結(jié)果對(duì)比Fig.3 Results under different initialized seed set sizes

圖4 不同感染概率下的結(jié)果對(duì)比Fig.4 Results under different infection probabilities

4 結(jié) 論

相較于單種子節(jié)點(diǎn)，具有多種子節(jié)點(diǎn)時(shí)，信息在網(wǎng)絡(luò)中的傳播更為復(fù)雜，在傳播過(guò)程中多個(gè)節(jié)點(diǎn)相互影響。本文以DynamicRank為基礎(chǔ)，提出了一種高效的基于貪心選擇策略的重要節(jié)點(diǎn)集挖掘方法，經(jīng)過(guò)多次迭代選擇影響力最高的種子集。本文采用SIR模型，在4個(gè)實(shí)際網(wǎng)絡(luò)上進(jìn)行了實(shí)驗(yàn)和對(duì)比。實(shí)驗(yàn)結(jié)果表明，本文方法在大多數(shù)情況下都優(yōu)于純粹基于重要節(jié)點(diǎn)排序的簡(jiǎn)單選擇方法，也優(yōu)于重要節(jié)點(diǎn)集挖掘的啟發(fā)式方法。不過(guò)，DynamicRank排序方法本身只考慮了3階可達(dá)鄰居，影響范圍有限；而簡(jiǎn)單擴(kuò)展鄰域的范圍一方面將極大增加計(jì)算時(shí)間的開(kāi)銷，另一方面也會(huì)帶來(lái)一定的噪聲干擾。因此，如何基于DynamicRank模型思想設(shè)計(jì)更為有效的方法挑選重要節(jié)點(diǎn)集，是未來(lái)的一個(gè)重要研究方向。同時(shí)，貪心算法每次迭代計(jì)算時(shí)需要遍歷圖中所有節(jié)點(diǎn)，隨著圖規(guī)模的增大，時(shí)間復(fù)雜度將會(huì)大大增加。因此，如何在大規(guī)模網(wǎng)絡(luò)中利用感染率傳播方法有效、快速地挖掘有影響力的傳播者，是另外一個(gè)需要重點(diǎn)研究的問(wèn)題。