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

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

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

0 引 言

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

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

1 相關技術及問題定義

1.1 影響力最大化問題

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

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

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

(1)

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

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

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

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

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

(1)S←{}

(2) fori=0 tokdo:

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

(4)S←S∪{u}

(5) returnS

1.2 基于跳步的獨立級聯模型

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

(2)

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

(3)

(4)

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

(5)

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

(6)

1.3 動態網絡中的影響力最大化問題

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

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

表1 符號

2 提出的方法

2.1 設計思想

網絡拓撲結構的小變化一般情況下不會引起影響力節點的大變動，這是增量式算法能以實現的基礎依據[11,18]。對發生變化后的前后兩個網絡Gt和Gt+1， 增量算法分析ΔGt， 盡可能充分利用Gt的結果St， 快速獲得Gt+1對應St+1。

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

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

2.2 識別增益上限增加的節點

當網絡的Gt拓撲結構發生增邊ΔGt={(u,v)} 變化，部分節點可通過在新增邊 (u,v) 傳播，影響其它節點。然而，由于信息傳播局限于h≤2跳步以內，因此僅有節點u及其前驅Rv能夠利用 (u,v) 進行傳播，進而提升它們影響力的上限。這些節點的查找及其影響力上限的更新方法如算法2所示。

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

輸入： 網絡圖G， 邊u→v， 跳數h

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

2.3 識別未發生變化節點

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

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

輸出： 查找節點最大可能排位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 替換新節點

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

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

輸入： 最具影響力種子集S， 種子集個數k， 跳數h， 插入位置pos

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

(2) fori=postokdo

(3) foreachv∈VSi-1docurv=false

(4) while true do

(6) ifcurv=truethensi=u*, break

(8) returnS

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

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

輸入：t時網絡圖Gt，t時最具影響力集合St， 種子集合個數k， 跳數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 復雜性分析

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

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

3 實驗及結果分析

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

3.1 實驗設置

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

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

表2 網絡數據集

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

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

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

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

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

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

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

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

為得到動態圖，實驗中對網絡圖進行100次隨機加邊，取算法響應加邊的平均運行時間作為結果輸出。

3.2 實驗結果及分析

3.2.1 大規模網絡對比

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

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

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

圖1 UNI模型下一跳對比

圖2 TRI模型下二跳對比

實驗中還發現在大多數情況下，很少出現替換影響增益最大節點、且算法最壞的情況，即重新計算所有種子節點的情況，很少出現。綜上，本文提出的IC-HopInc算法可有效應對大規模網絡拓撲結構變化。

3.2.2 小規模網絡對比

本節實驗在dolphins、football數據集上進行，比較算法為找到k=1,10,20,30個最大影響力節點所需時間。和上節實驗一樣，網絡數據分別設置UNI概率值和TRI概率值。

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

圖3 UNI模型下二跳對比

圖4 TRI模型下一跳對比

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

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

綜上實驗結果和分析，無論是在大規模還是小規模網絡上，HopInc算法運行時間均少于UBI和IncInf動態跟蹤算法，也少于基于跳步傳播的靜態影響力最大化算法算法，驗證了HopInc算法的高效性。

4 結束語

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