基于跳步的增量式影響力最大化算法

黃 穎，梁春泉，楊澤寬，曹曉旭，武文君

(西北農(nóng)林科技大學(xué) 信息工程學(xué)院，陜西 楊陵 712100)

0 引 言

影響力最大化是在線(xiàn)社交網(wǎng)絡(luò)中的重要問(wèn)題，對(duì)口碑營(yíng)銷(xiāo)、輿情控制等眾多應(yīng)用的實(shí)施起著關(guān)鍵性作用[1,2]。給定一個(gè)網(wǎng)絡(luò)和參數(shù)k，該問(wèn)題旨在找出其中k個(gè)用戶(hù)，在某種傳播模型下發(fā)起信息傳播，使得最終受影響用戶(hù)總數(shù)最大化[3,4]。常見(jiàn)傳播模型有獨(dú)立級(jí)聯(lián)和線(xiàn)性閾值模型；在這二者下，影響力最大化問(wèn)題均為NP-hard[5]。針對(duì)該問(wèn)題，經(jīng)典算法采用貪心策略、啟發(fā)式地選擇影響力增益最大者作為輸出[5]。為提高貪心算法效率，學(xué)術(shù)界提出兩類(lèi)方法：利用上限值減少評(píng)估每個(gè)節(jié)點(diǎn)影響力的重復(fù)次數(shù)[6,7]；利用傳播局部化特性降低單次評(píng)估所需時(shí)間[8,9]。

現(xiàn)有算法大多僅處理靜態(tài)網(wǎng)絡(luò)，然而在線(xiàn)社交網(wǎng)絡(luò)天然動(dòng)態(tài)，其中影響力用戶(hù)會(huì)隨著網(wǎng)絡(luò)結(jié)構(gòu)變動(dòng)而變化[10,11]。部分研究開(kāi)始解決動(dòng)態(tài)網(wǎng)絡(luò)中影響力最大化問(wèn)題[10,12-17]，但并非用來(lái)應(yīng)對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變動(dòng)。為此，文獻(xiàn)[11，18]提出了跟蹤動(dòng)態(tài)網(wǎng)絡(luò)中最大影響力節(jié)點(diǎn)的算法。然而這些算法應(yīng)對(duì)任何變動(dòng)都需要重新選擇k個(gè)節(jié)點(diǎn)作為輸出，且每選一個(gè)節(jié)點(diǎn)均需要評(píng)估剩下節(jié)點(diǎn)的影響力，降低效率。本文同樣關(guān)注網(wǎng)絡(luò)結(jié)構(gòu)持續(xù)變化下跟蹤影響力用戶(hù)的問(wèn)題，受文獻(xiàn)[8]啟發(fā)，提出一種基于跳步(hop)的增量式算法。利用影響傳播的跳步局部化特點(diǎn)，算法快速識(shí)別無(wú)需變化的節(jié)點(diǎn)，并增量地替換過(guò)時(shí)節(jié)點(diǎn)；最后在真實(shí)數(shù)據(jù)集上實(shí)驗(yàn)驗(yàn)證了算法的執(zhí)行效率。

1 相關(guān)技術(shù)及問(wèn)題定義

1.1 影響力最大化問(wèn)題

社交網(wǎng)絡(luò)可建模為有向圖G=(V,E)， 其中頂點(diǎn)集V表示所有用戶(hù)，邊集E={(u,v)|u∈V,v∈V} 表示用戶(hù)u與v之間聯(lián)系。每條邊e=(u,v)∈E關(guān)聯(lián)著一個(gè)概率值pu,v∈[0,1]， 用來(lái)表示信息傳播過(guò)程中用戶(hù)u對(duì)v的激活概率。對(duì)于有向邊(u,v)， 稱(chēng)節(jié)點(diǎn)v為u的鄰居，則Nu={v|(u,v)∈E} 為u鄰居集；稱(chēng)u是v的逆鄰居，則Rv={v|(u,v)∈E} 為v的逆鄰居集。

給定社交網(wǎng)絡(luò)G和參數(shù)k， 影響力最大化問(wèn)題旨在從網(wǎng)絡(luò)G中選擇種子集S*∈V且|S*|=k， 按照某種傳播策略，由S*中的節(jié)點(diǎn)開(kāi)始級(jí)聯(lián)地激活其它節(jié)點(diǎn)，使得最終激活節(jié)點(diǎn)的期望總數(shù)σ(S*) 最大化，如式(1)所示

σ(S*)=Max(σ(S)|S?V,|S|=k)

(1)

本研究采用獨(dú)立級(jí)聯(lián)傳播模型，給定一個(gè)種子集S∈V， 其傳播過(guò)程如下：初始化種子集S為激活狀態(tài)；從S開(kāi)始，每個(gè)新激活節(jié)點(diǎn)u有一次機(jī)會(huì)以概率pu,v激活其尚未激活的每個(gè)鄰居節(jié)點(diǎn)v∈Nu； 傳播不斷向前推進(jìn)，直至沒(méi)有新節(jié)點(diǎn)被激活。

在獨(dú)立級(jí)聯(lián)模型下，影響力最大化問(wèn)題為NP-hard難題[5]。利用評(píng)估函數(shù)σ(S) 的子模塊性質(zhì)和邊際效應(yīng)，可設(shè)計(jì)一個(gè)近似比為1-1/e的貪心算法，如算法1所示[5]。算法啟發(fā)式地選擇令影響力增益最大者加入種子集S。

算法1： Greedy(k,σ(·))

輸入： 種子集個(gè)數(shù)k， 評(píng)估種子影響力函數(shù)σ(·)

輸出： 最具影響力種子集S

(1)S←{}

(2) fori=0 tokdo:

(3)u←argmaxu∈VS((σ(S∪{u})-σ(S))

(4)S←S∪{u}

(5) returnS

1.2 基于跳步的獨(dú)立級(jí)聯(lián)模型

算法1的關(guān)鍵步驟是計(jì)算影響力σ(S)， 進(jìn)而計(jì)算增益Δσ(S,u)=σ(S∪{u})-σ(S)， 但不幸的是準(zhǔn)確獲取σ(S) 是一個(gè)#P-hard難題[9]。早期研究通過(guò)多次蒙特卡羅模擬獲得評(píng)估值，時(shí)間開(kāi)銷(xiāo)巨大。文獻(xiàn)[8]通過(guò)實(shí)證發(fā)現(xiàn)在蒙特卡羅模擬中，大多數(shù)激活節(jié)點(diǎn)都產(chǎn)生于傳播過(guò)程中的前幾個(gè)跳步，特別是傳播跳步數(shù)h≤2時(shí)。因此，為提高效率，文獻(xiàn)[8]提出采用h跳步內(nèi)傳播的期望值σh(S)估算σ(S)， 用Δσh(S,u) 估算Δσ(S,u)。 當(dāng)h≤2時(shí)，由于傳播路徑不存在回路，可以直接通過(guò)概率運(yùn)算獲得σh(S) 和Δσh(S,u)。 詳細(xì)計(jì)算過(guò)程參見(jiàn)文獻(xiàn)[8]。

(2)

向S添加節(jié)點(diǎn)u時(shí)，影響力增益可用式(3)計(jì)算

(3)

(4)

向S加入節(jié)點(diǎn)u時(shí)，節(jié)點(diǎn)v的受影響概率將更新為

(5)

貪心算法所需的影響力增益可用式(6)計(jì)算

(6)

1.3 動(dòng)態(tài)網(wǎng)絡(luò)中的影響力最大化問(wèn)題

給定t時(shí)的網(wǎng)絡(luò)Gt， 一個(gè)包含k種子的集合St， 以及經(jīng)過(guò)Δt的網(wǎng)絡(luò)變化ΔG，求新網(wǎng)絡(luò)Gt+Δt=Gt⊕ΔG中影響力最大化種子集St+Δt。 對(duì)ΔG，本文僅考慮增邊的情況。

本文用到的主要符號(hào)見(jiàn)表1。

表1 符號(hào)

2 提出的方法

2.1 設(shè)計(jì)思想

網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的小變化一般情況下不會(huì)引起影響力節(jié)點(diǎn)的大變動(dòng)，這是增量式算法能以實(shí)現(xiàn)的基礎(chǔ)依據(jù)[11,18]。對(duì)發(fā)生變化后的前后兩個(gè)網(wǎng)絡(luò)Gt和Gt+1， 增量算法分析ΔGt， 盡可能充分利用Gt的結(jié)果St， 快速獲得Gt+1對(duì)應(yīng)St+1。

基于上述思路，本文提出一個(gè)有限跳步數(shù)傳播下最具影響力節(jié)點(diǎn)的跟蹤算法。利用有限跳步局部傳播特性，算法通過(guò)比較ΔGt涉及節(jié)點(diǎn)與St中節(jié)點(diǎn)的影響力增益，直接識(shí)別出St中無(wú)需變動(dòng)部分，并增量地替換有可能變動(dòng)部分；二者一起構(gòu)成St+1。 相對(duì)于現(xiàn)有研究[11,18]，本文方法以更直接的方式重復(fù)利用St， 無(wú)需重新評(píng)估和選擇每一個(gè)影響力節(jié)點(diǎn)，因此能更快速獲得St+1。

具體地，在任何時(shí)刻t，本文算法為圖Gt維護(hù)h跳步傳播下最具影響力節(jié)點(diǎn)St={s1,s2,…sk}， 其中節(jié)點(diǎn)按入選時(shí)的影響力增益降序排序?？紤]增邊變化會(huì)引起部分節(jié)點(diǎn)的影響力提升，算法首先識(shí)別出該部分節(jié)點(diǎn)并更新其影響力上限，其次令St與之比較，識(shí)別出St無(wú)需變化部分，最后增量式地替換變化部分。

2.2 識(shí)別增益上限增加的節(jié)點(diǎn)

當(dāng)網(wǎng)絡(luò)的Gt拓?fù)浣Y(jié)構(gòu)發(fā)生增邊ΔGt={(u,v)} 變化，部分節(jié)點(diǎn)可通過(guò)在新增邊 (u,v) 傳播，影響其它節(jié)點(diǎn)。然而，由于信息傳播局限于h≤2跳步以?xún)?nèi)，因此僅有節(jié)點(diǎn)u及其前驅(qū)Rv能夠利用 (u,v) 進(jìn)行傳播，進(jìn)而提升它們影響力的上限。這些節(jié)點(diǎn)的查找及其影響力上限的更新方法如算法2所示。

算法2： MaxGainIncNodes(G,(u,v),h)

輸入： 網(wǎng)絡(luò)圖G， 邊u→v， 跳數(shù)h

輸出： 影響力有提升的節(jié)點(diǎn)集合T

(1)T←{}

(3)T←T∪{u}

(4) ifh== 2 then

(5) foreachw∈Rudo

(7)T←T∪{w}

(8) foreachw∈Nvdo

(10) returnT

算法2中，步驟(2)計(jì)算節(jié)點(diǎn)u在節(jié)點(diǎn)v上獲得的最大影響力提升，步驟(6)計(jì)算u前驅(qū)節(jié)點(diǎn)在v上獲得的提升，步驟(9)計(jì)算u在v后繼節(jié)點(diǎn)上獲得的提升；步驟(3) 和步驟(7)則收集影響力有提升的節(jié)點(diǎn)。

2.3 識(shí)別未發(fā)生變化節(jié)點(diǎn)

算法3： FindIsrtPos(S,u,k,h)

輸入： 最具影響力種子集S， 影響力上限增加的節(jié)點(diǎn)u， 種子集個(gè)數(shù)k， 跳數(shù)h

輸出： 查找節(jié)點(diǎn)最大可能排位left

(1)left←1,right←k

(2) while (left≤right) do

(3)mid←(left+right)/2

(6) else thenright←mid-1

(7) returnleft

2.4 替換新節(jié)點(diǎn)

若影響力上限增加的節(jié)點(diǎn)u在當(dāng)前種子集St中找到插入位置pos，則u有可能成為排在pos的種子節(jié)點(diǎn)，進(jìn)而St中排位在pos位置之后的節(jié)點(diǎn)，由于受邊際效應(yīng)的影響，實(shí)際影響力增益可能會(huì)降低，因此需要重新評(píng)估節(jié)點(diǎn)影響力增益，更新種子集。更新過(guò)程如算法4所示。為提高效率算法初始節(jié)點(diǎn)實(shí)際增益為最大增益(步驟(1))，進(jìn)而采用CELF算法[6]更新S[pos∶k] 部分的種子(步驟(2)～步驟(7))。

算法4： UpdateSeeds(S,k,h,pos)

輸入： 最具影響力種子集S， 種子集個(gè)數(shù)k， 跳數(shù)h， 插入位置pos

輸出： 更新后最具影響力種子集S

(2) fori=postokdo

(3) foreachv∈VSi-1docurv=false

(4) while true do

(6) ifcurv=truethensi=u*, break

(8) returnS

最后，本文提出的基于跳步的增量式影響力最大算法如算法5所示。算法首先獲取影響力上限增加的節(jié)點(diǎn)集(步驟(2))，為其中每個(gè)節(jié)點(diǎn)嘗試找到在St中的排位(步驟(4))；若找到，則更新St中排在pos的種子節(jié)點(diǎn)。

算法5： IC-HopInc(Gt,St,k,h,(u,v))

輸入：t時(shí)網(wǎng)絡(luò)圖Gt，t時(shí)最具影響力集合St， 種子集合個(gè)數(shù)k， 跳數(shù)h， 邊u→v

輸出：t+1最具影響力集合St+1

(1)St+1=St

(2)T←MaxGainIncNodes(G,(u,v),h)

(3) foreachw∈Tdo

(4)pos←FindIsrtPos(St+1,w)

(5) ifpos≤kthen

(6)St+1=UpdateSeeds(St+1,k,pos)

(7) returnSt+1

2.5 復(fù)雜性分析

實(shí)際上，在網(wǎng)絡(luò)單位變化情況下，不管是1跳步還是2跳步傳播，大多數(shù)的非網(wǎng)絡(luò)節(jié)點(diǎn)v∈V-St的影響力上限都不會(huì)瞬間增加到讓它成為一個(gè)可能的種子節(jié)點(diǎn)，因此算法5中的步驟(5)很少成立。算法時(shí)間運(yùn)行取決于步驟(2)和步驟(4)。因此，在1跳情況下，對(duì)大多數(shù)節(jié)點(diǎn)，步驟(2)和步驟(4)單位時(shí)間即可完成O(1)； 在2跳情況下，步驟(2)需要O(Rmax) 時(shí)間，而步驟(4)只需單位時(shí)間，結(jié)合O(Rmax) 循環(huán)，總運(yùn)行時(shí)間僅需O(Rmax)。 下一節(jié)實(shí)驗(yàn)結(jié)果驗(yàn)證了我們算法的高效性。

不論是1跳步傳播還是2跳步傳播的情況下，IC-HopInc都僅需要O(V) 空間去存儲(chǔ)每個(gè)節(jié)點(diǎn)1跳步或2跳步的傳播受影響概率，節(jié)點(diǎn)的影響力增益上限，以及節(jié)點(diǎn)入選種子集的影響力增益。

3 實(shí)驗(yàn)及結(jié)果分析

本部分在5個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)評(píng)估，與最新的跟蹤動(dòng)態(tài)網(wǎng)絡(luò)中最具影響力節(jié)點(diǎn)的算法比較，以運(yùn)行時(shí)間為衡量標(biāo)注，驗(yàn)證本文所提出算法IC-HopInc的高效性。為便于后文討論，在1跳步傳播情況下，命名本文所提出的算法為OneIC-HopInc；在2跳步傳播情況下，命名為T(mén)woIC-HopInc；IC-HopInc則表示這二者。

3.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)中所有評(píng)估算法均采用復(fù)雜網(wǎng)絡(luò)處理工具包Networkx(v2.4)(http://networkx.github.io/)和Python(v3.7)編程語(yǔ)言行實(shí)現(xiàn)。實(shí)驗(yàn)所用計(jì)算機(jī)的信息為：處理器AMD Ryzen 5 1500X 3.50 GHz，內(nèi)存16.0 GB，操作系統(tǒng)Windows 10。

數(shù)據(jù)集：實(shí)驗(yàn)數(shù)據(jù)集來(lái)源于斯坦福數(shù)據(jù)集(http://snap.stanford.edu/)與NewMan個(gè)人數(shù)據(jù)網(wǎng)站(http://www-personal.umich.edu/～mejn/netdata/)。所采用的數(shù)據(jù)集有海豚社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集(dolphin)、美國(guó)大學(xué)橄欖球數(shù)據(jù)集(football)、維基選票網(wǎng)站數(shù)據(jù)集(Wiki-vote)、消費(fèi)者評(píng)論網(wǎng)站數(shù)據(jù)集(soc-Epinions1)和書(shū)籍標(biāo)簽推薦數(shù)據(jù)集(soc-delicious)。表2為具體信息。

表2 網(wǎng)絡(luò)數(shù)據(jù)集

基準(zhǔn)算法：實(shí)驗(yàn)中，本文提出的OneIC-HopInc和TwoIC-HopInc將與下列基準(zhǔn)算法比較：靜態(tài)OneHop算法、靜態(tài)TwoHop算法、UBI算法和IncInf算法，簡(jiǎn)介如下：

(1)OneHop：在1跳步傳播下，采用獨(dú)立級(jí)聯(lián)模型的靜態(tài)影響力最大化算法[8]；

(2)TwoHop：在2跳步傳播下，采用獨(dú)立級(jí)聯(lián)模型的靜態(tài)影響力最大化算法[8]；

(3)UBI：一種影響力節(jié)點(diǎn)跟蹤算法[11]，通過(guò)對(duì)先前輸出St中的節(jié)點(diǎn)做k次替換以提升種子集影響力，從而獲得當(dāng)前的輸出St+1；

(4)IncInf：另一種影響力節(jié)點(diǎn)跟蹤算法[18]，利用先前輸出St、 節(jié)點(diǎn)度最高或節(jié)點(diǎn)度變動(dòng)最高的節(jié)點(diǎn)和變化信息，構(gòu)造候選集并評(píng)估其中每個(gè)節(jié)點(diǎn)影響力增益，從中選擇k個(gè)增益最高者作為當(dāng)前輸出St+1。

數(shù)據(jù)預(yù)處理：由于上述網(wǎng)絡(luò)數(shù)據(jù)集中并未包含傳播概率，實(shí)驗(yàn)中采用研究界廣泛使用的Uniform(UNI) 和Trivalency(TRI)模型設(shè)置網(wǎng)絡(luò)傳播概率[8,11]。

(1)Uniform(UNI)：對(duì)每條邊(u,v)∈E， 設(shè)置傳播概率為pu,v=0.1。

(2)Trivalency(TRI)：對(duì)每條邊(u,v)∈E， 設(shè)置傳播pu,v為{0.1,0.01,0.001}中的一個(gè)隨機(jī)值。

為得到動(dòng)態(tài)圖，實(shí)驗(yàn)中對(duì)網(wǎng)絡(luò)圖進(jìn)行100次隨機(jī)加邊，取算法響應(yīng)加邊的平均運(yùn)行時(shí)間作為結(jié)果輸出。

3.2 實(shí)驗(yàn)結(jié)果及分析

3.2.1 大規(guī)模網(wǎng)絡(luò)對(duì)比

本節(jié)實(shí)驗(yàn)在Wiki-vote、soc-Epinions1、soc-delicious這3個(gè)大型數(shù)據(jù)集上進(jìn)行，比較算法找出k=1,10,100,1000個(gè)最具影響力種子所需時(shí)間；網(wǎng)絡(luò)數(shù)據(jù)分別設(shè)置UNI概率值和TRI概率值。

圖1給出了傳播概率值設(shè)置為UNI時(shí)，OneHop算法、OneIC-HopInc算法和IncInf算法運(yùn)行時(shí)間的曲線(xiàn)。圖2給出了傳播概率值設(shè)置為T(mén)RI時(shí)TwoHop算法、TwoIC-HopInc算法和IncInf算法運(yùn)行時(shí)間的曲線(xiàn)。

從圖1和圖2可看到，在不同概率值設(shè)置下，相同算法的運(yùn)行時(shí)間會(huì)出現(xiàn)略微的差別。同時(shí)可看到隨著需要找出種子數(shù)k不斷增大，所有算法的運(yùn)行時(shí)間也隨之增加。然而，不論是在UNI模型還是在TRI模型下，IC-HopInc算法運(yùn)行時(shí)間均遠(yuǎn)少于靜態(tài)算法和動(dòng)態(tài)算法IncInf。在2跳步傳播情況下(例如TRI模型下Wiki-vote)本文所提算法運(yùn)行時(shí)間與靜態(tài)算法較為接近，其原因是在隨機(jī)加邊過(guò)程中，邊加在當(dāng)前影響力增益最大的節(jié)點(diǎn)上，從而要更新排它之后的所有種子節(jié)點(diǎn)，導(dǎo)致了最差運(yùn)行時(shí)間。但即便最差情況下，IC-HopInc算法的運(yùn)行時(shí)間仍在可接受范圍內(nèi)。此外，可看到IncInf算法在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化較小時(shí)，其運(yùn)行時(shí)間接近于靜態(tài)算法，原因是需進(jìn)行大量計(jì)算，耗費(fèi)大量時(shí)間。

圖1 UNI模型下一跳對(duì)比

圖2 TRI模型下二跳對(duì)比

實(shí)驗(yàn)中還發(fā)現(xiàn)在大多數(shù)情況下，很少出現(xiàn)替換影響增益最大節(jié)點(diǎn)、且算法最壞的情況，即重新計(jì)算所有種子節(jié)點(diǎn)的情況，很少出現(xiàn)。綜上，本文提出的IC-HopInc算法可有效應(yīng)對(duì)大規(guī)模網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化。

3.2.2 小規(guī)模網(wǎng)絡(luò)對(duì)比

本節(jié)實(shí)驗(yàn)在dolphins、football數(shù)據(jù)集上進(jìn)行，比較算法為找到k=1,10,20,30個(gè)最大影響力節(jié)點(diǎn)所需時(shí)間。和上節(jié)實(shí)驗(yàn)一樣，網(wǎng)絡(luò)數(shù)據(jù)分別設(shè)置UNI概率值和TRI概率值。

圖3對(duì)比了傳播概率值設(shè)置為UNI時(shí)，TwoHop算法、TwoIC-HopInc算法、IncInf，以及UBI算法的運(yùn)行時(shí)間。圖4對(duì)比了傳播概率值設(shè)置為T(mén)RI時(shí)，OneHop算法、OneIC-HopInc算法、IncInf算法，以及UBI算法的運(yùn)行時(shí)間。

圖3 UNI模型下二跳對(duì)比

圖4 TRI模型下一跳對(duì)比

從圖3和圖4中可以看到在兩種概率值模型下，UBI算法所需時(shí)間遠(yuǎn)大于基于跳步的靜態(tài)算法、HopInc算法以及動(dòng)態(tài)IncInf算法。當(dāng)需要選擇的種子數(shù)較小時(shí)，HopInc的算法運(yùn)行最快；二跳范圍內(nèi)，靜態(tài)算法以及動(dòng)態(tài)IncInf算法加邊后重新計(jì)算的時(shí)間(特別是在種子集大小為20和30時(shí))與HopInc算法運(yùn)行時(shí)間差別不大，前者原因在于，二跳情況下，HopInc算法在確定受影響范圍內(nèi)受增益最大的節(jié)點(diǎn)浪費(fèi)了時(shí)間或者在替換過(guò)程中遇到最壞情況所造成。后者原因在于拓?fù)渥兓^(guò)小，節(jié)點(diǎn)的選擇類(lèi)似靜態(tài)貪心算法。對(duì)比之前在大規(guī)模網(wǎng)絡(luò)下的運(yùn)行情況來(lái)說(shuō)，即使出現(xiàn)最差的運(yùn)行情況，算法的效果也是較優(yōu)于對(duì)比算法，其運(yùn)行時(shí)間還是在可接受的范圍內(nèi)。

UBI算法采用節(jié)點(diǎn)追蹤實(shí)現(xiàn)節(jié)點(diǎn)替換，但在選擇替換節(jié)點(diǎn)時(shí)，需要進(jìn)行 |V-S| 次的影響評(píng)估，并且需要不斷的去維護(hù)概率矩陣，相比于本文的算法，需要進(jìn)行大量的計(jì)算。經(jīng)過(guò)測(cè)試，即使在僅含1000個(gè)節(jié)點(diǎn)的小圖上，UBI算法在種子集的選擇中運(yùn)行200多個(gè)小時(shí)仍然無(wú)法得到結(jié)果，因此本節(jié)選擇了在數(shù)據(jù)量較小的dolphins和football數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，對(duì)比不同算法運(yùn)行時(shí)間。

綜上實(shí)驗(yàn)結(jié)果和分析，無(wú)論是在大規(guī)模還是小規(guī)模網(wǎng)絡(luò)上，HopInc算法運(yùn)行時(shí)間均少于UBI和IncInf動(dòng)態(tài)跟蹤算法，也少于基于跳步傳播的靜態(tài)影響力最大化算法算法，驗(yàn)證了HopInc算法的高效性。

4 結(jié)束語(yǔ)

本文提出了一個(gè)基于跳步傳播的增量式影響力最大化算法，即HopInc。該算法利用有限跳步傳播特點(diǎn)，快速評(píng)估網(wǎng)絡(luò)變化所涉及節(jié)點(diǎn)的影響力增益上限，與先前輸出結(jié)果比較，識(shí)別無(wú)需變動(dòng)的結(jié)果；同時(shí)快速更新有可能需要變動(dòng)的影響力節(jié)點(diǎn)。在多個(gè)真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，相比靜態(tài)算法和其它最新的動(dòng)態(tài)跟蹤算法，HopInc算法能以更快速度找到動(dòng)態(tài)網(wǎng)絡(luò)中最具影響力節(jié)點(diǎn)。