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

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

0 引 言

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

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

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

1.1 影響力最大化問題

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

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

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

(1)

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

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

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

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

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

(1)S←{}

(2) fori=0 tokdo:

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

(4)S←S∪{u}

(5) returnS

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

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

(2)

向S添加節(jié)點u時，影響力增益可用式(3)計算

(3)

(4)

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

(5)

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

(6)

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

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

本文用到的主要符號見表1。

表1 符號

2 提出的方法

2.1 設(shè)計思想

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

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

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

2.2 識別增益上限增加的節(jié)點

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

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

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

輸出： 影響力有提升的節(jié)點集合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)計算節(jié)點u在節(jié)點v上獲得的最大影響力提升，步驟(6)計算u前驅(qū)節(jié)點在v上獲得的提升，步驟(9)計算u在v后繼節(jié)點上獲得的提升；步驟(3) 和步驟(7)則收集影響力有提升的節(jié)點。

2.3 識別未發(fā)生變化節(jié)點

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

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

輸出： 查找節(jié)點最大可能排位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é)點

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

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

輸入： 最具影響力種子集S， 種子集個數(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é)點集(步驟(2))，為其中每個節(jié)點嘗試找到在St中的排位(步驟(4))；若找到，則更新St中排在pos的種子節(jié)點。

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

輸入：t時網(wǎng)絡(luò)圖Gt，t時最具影響力集合St， 種子集合個數(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ù)雜性分析

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

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

3 實驗及結(jié)果分析

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

3.1 實驗設(shè)置

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

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

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

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

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

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

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

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

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

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

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

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

3.2 實驗結(jié)果及分析

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

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

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

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

圖1 UNI模型下一跳對比

圖2 TRI模型下二跳對比

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

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

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

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

圖3 UNI模型下二跳對比

圖4 TRI模型下一跳對比

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

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

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

4 結(jié)束語

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