基于反向PageRank的影響力最大化算法

張憲立，唐建新，曹來成

(蘭州理工大學 計算機與通信學院，蘭州 730050)

0 引言

隨著互聯網的發展，各種社交平臺不斷出現，如：Weibo、WeChat、Facebook等，這些社交平臺規模龐大，成為信息傳播的重要方式之一。同時，人與人之間的交互逐漸從線下轉移到線上，使得對傳統社交關系的獲取、追蹤更加容易，針對社會網絡的研究已經成為一個熱點問題。其中，影響力最大化問題就是在網絡中尋找部分節點作為信息傳播的種子節點，使得信息的傳播范圍在網絡上最大化。研究該問題對于病毒式營銷具有重要的意義，考慮一家公司想要利用有限的資金在網絡上推廣它的產品，通過在網絡上選出部分有影響力的人，向他們提供一定的報酬，讓這些有影響力的人在網絡上推廣它的產品，使得網絡中更多的用戶知道，接受該產品，這就是影響力最大化。

Domingos等[1-2]首先將影響力最大化問題作為一個算法問題來研究。隨后，Kempe等[3]將該問題表示成離散的組合優化問題，證明該問題在獨立級聯(Independent Cascade, IC)模型和線性閾值(Linear Threshold, LT)模型下是一個NP-hard問題，并提出一個貪心爬山算法，該算法的傳播范圍能夠達到最優解的(1-1/e-ε)，其中e是自然對數，ε為誤差；然而貪心爬山算法利用蒙特卡洛模擬來評估節點的影響力，迭代選取影響力增益最大的節點，時間復雜度高，不適用于大規模網絡。

為了解決貪心算法的效率問題，Leskovec等[4]提出CELF(Cost-Effective Lazy-Forward)算法，該算法利用目標函數的子模特性，減少蒙特卡洛模擬的次數，實驗結果表明比貪心爬山算法快近700倍。Chen等[5]通過利用蒙特卡洛模擬的結果圖，提出NewGready和MixedGready，進一步優化貪心算法。Cheng等[6]提出靜態貪婪算法StaticGready，時間效率提升兩個數量級。基于減少蒙特卡洛模擬次數的思想，Ohsaka等[7]提出剪枝的蒙特卡洛(Pruned Monte-Carlo, PMC)模擬算法。上述基于貪心思想的改進算法，傳播范圍具有理論保證，但是依然需要蒙特卡洛模擬來計算節點的影響力，難以擴展到大規模網絡上。

針對貪心算法的低效性，一些學者提出大量的啟發式算法。Chen等[5]提出DegreeDiscount，該算法利用度中心性選擇種子節點，同時將種子節點的鄰居的度值打一定的折扣，實驗結果表明傳播范圍優于度中心性算法；曹玖新等[8]提出一種基于k-核的啟發式算法——CCA(Core Covering Algorithm)；王雙等[9]提出一種基于社區的影響力最大化算法；楊書新等[10]介紹了一種基于度和影響力的混合啟發式(Degree and Influence Heuristic, DIH)算法。

李閱志等[11]提出一種基于獨立級聯模型的k-核過濾算法，該算法通過在k-核子圖上運行現有的影響力最大化算法，降低時間復雜度。李敏佳等[12]結合結構洞和度折扣的優勢，設計SHDD(Structure Hole and Degree Discount)算法。孫子力等[13]考慮信息傳播中的衰減現象，設計一種基于社群結構的影響力最大化(Influence Maximization on Internal Decay, IMID)算法。這些基于啟發式的算法時間效率高，但是關于傳播范圍缺乏理論保證，沒有考慮傳播特性，在不同的網絡和傳播模型下傳播范圍不穩定。

為了避免大量的蒙特卡洛模擬，Kimura等[14]提出基于傳播路徑的影響力算法——SPM(Shortest-Path Model)，該算法認為節點的影響力只在最短路徑之間傳播。進一步考慮傳播特性，Chen等[15]提出節點之間的影響力只在最大影響路徑上傳播，設計PMIA(Prefix excluding Maximum Influence Path)算法。考慮所有傳播路徑，Kim等[16]提出IPA(Independent Path Algorithm)。Wu等[17]提出LAIM(Linear time iterative Approach for efficient Influence Maximization)，該算法首先基于多層鄰居迭代計算節點的影響力，然后利用貪心思想選擇影響力增益最大的節點。這類算法將影響力傳播限制在特殊的路徑上或者局部范圍來快速計算節點影響力，時間效率要優于貪心算法，但是關于傳播范圍缺乏理論保證。

最近Borgs等[18]提出反向抽樣(Reverse Influence Sampling, RIS)的思想來解決影響力最大化問題，時間復雜度接近線性，傳播范圍具有理論保證。進一步，Tang等提出TIM/TIM+(Two-phase Influence Maximization)[19]、IMM(Influence Maximization based on Martingale)[20]等基于RIS思想的算法。Nguyen等[21]提出SSA(Stop-and-State Algorithm)和D-SSA(Dynamic Stop-and-State Algorithm)算法。Wang等[22]將抽樣順利引入RIS中，設計BKRIS(Bottom-K sketch based on Reverse Influence Sampling)算法。據悉，這類算法目前是解決影響力最大化問題最好的算法之一，能夠獲得高的傳播范圍，時間效率高，然而這類算法需要存儲大量的抽樣樣本，內存消耗嚴重。

針對現有影響力最大化算法在大規模網絡上難以同時滿足傳播范圍、時間效率和空間效率的問題，本文首先介紹反向PageRank的思想，然后設計一種混合反向PageRank和度中心性的啟發式算法(heuristic algorithm of Mixed PageRank and Degree, MPRD)，最后為了避免選出的種子節點影響力傳播范圍重合，利用相似性方法過濾掉影響范圍重合嚴重的節點，進一步提高算法的傳播范圍。實驗結果表明,MPRD在傳播范圍上接近貪心算法和基于反向抽樣的算法，優于現有的啟發式算法；在運行時間上比貪心算法提高四、五個數量級；同時在內存消耗上優于基于反向抽樣的算法。

1 背景知識

在本文中，網絡表示成圖G=(V,E),其中：V為節點集合，表示個體；E為邊集，表示個體之間的關系。

1.1 傳播模型

傳播模型就是描述信息在網絡中傳播的規則，本文主要介紹三種主流的影響力傳播模型：獨立級聯模型、權重級聯(Weighted Cascade, WC)模型和線性閾值模型[3]。在這些模型中，節點有激活和未激活兩種狀態，激活狀態表示該節點已經接受信息，未激活狀態表明該節點沒有接受信息，即未被影響。同時，激活過程不可逆，節點只能從未激活狀態變為激活狀態。

1)獨立級聯模型和權重級聯模型。在獨立級聯模型中，初始在第0步只有種子集合S是激活狀態，即S0=S，對于在第t步激活的節點u∈St都有且僅有一次機會以puv的概率去激活u周圍未激活的每一個鄰居節點v，無論成功與否，u都不會再去激活v。當有多個激活節點嘗試去激活同一個節點時，激活過程是彼此獨立的，嘗試激活的順序是隨機的。當沒有更多的節點被激活，傳播過程結束。權重級聯模型是獨立級聯模型的一個特例，唯一的不同之處是節點激活概率puv在獨立級聯模型中通常是一個常數，如0.01,0.05等，而在權重級聯模型中puv設置如下：

(1)

1.2 問題定義

定義1 影響力最大化。給定一個網絡G=(V,E)，一個正整數k?|V|，影響力最大化問題就是從網絡中找出k個節點作為種子節點集合T，使得這些節點在某個傳播模型的影響力傳播范圍σ(T)最大化，表示如下：

(2)

其中：T為網絡中任意k個節點集合；S為選出的種子節點集合；σ(T)表示將T作為初始節點所能激活的預期節點數。

2 混合PageRank和Degree的影響力最大化算法

2.1 反向PageRank的思想

PageRank算法[23]是Google公司用來衡量網頁等級和重要性的一種方法，該方法的基本思想是一個網頁的重要性取決于指向它的其他頁面的數量和質量。初始時給所有網頁賦一個初始的PageRank值PR，滿足式(3):

(3)

其中，n為網頁總數，然后將每個網頁的PageRank值迭代平均分配給其所指向的網頁。同時為了避免指向網頁為0的網頁始終將PageRank值分配給自己，設置一個比例因子α將每個節點的PageRank值進行縮減，再把1-α平均分配給每個網頁，以保持網絡總的PageRank值為1，即通過如式(4)進行迭代計算：

(4)

其中:Nin(u)表示指向網頁u的其他網頁集合;Nout(v)表示網頁v指向的其他網頁集合;相應的|Nout(v)|表示這個集合的大小;α通常設為0.85。當迭代次數足夠多時，所有網頁的PageRank值將會收斂。

直接將PageRank算法應用到影響力最大化問題上通常傳播范圍有限，特別是在有向圖中。因為PageRank算法是尋找重要的節點，而影響力最大問題是尋找好的信息傳播源。受PageRank算法思想的啟發，一個節點的影響力不僅與其指向的節點數量有關(度中心性)，而且與其指向節點的質量，即影響力有關。為此一個節點u的影響力Infu可以表示成該節點所指向的鄰居節點的影響力的和，即：

(5)

其中puv表示節點u激活節點v的概率。基于PageRank算法，為每一個節點分配一個初始的影響力，當更新一個節點的影響力時，應該將該節點所指向的每個節點的影響力按照一定的比例進行累加(如式(5))。換言之，每個節點應該將其影響力按照激活概率分配給它的入度鄰居，即反向PageRank的思想，影響力迭代計算如下：

(6)

其中:Nout(u)表示節點u的出度鄰居集合，prouv表示v的入度鄰居u激活v的概率在v的入度鄰居中所占的比例，如式(7)所示：

(7)

其中Nin(v)表示節點v的入度鄰居集合。

2.2 MPRD

實驗中發現反向PageRank算法在有向圖，權重級聯模型下傳播效果好，但是在無向圖或者獨立級聯模型下傳播范圍不穩定。為了提高算法對于模型的魯棒性，本文結合反向PageRank和度中心算法，提出一種混合的啟發式算法MPRD。該算法首先利用反向PageRank的思想，計算節點的影響力(式(6))，然后將節點的度歸一化，使用如式(8)表示節點最終的影響力：

(8)

由于網絡的聚集效應，影響力高的節點經常聚集在一起，形成富人俱樂部現象。啟發式算法選出的種子節點之間影響力范圍容易重合，使得總體的影響力傳播局限在網絡局部，導致算法的傳播范圍有限。為了減少選出的種子節點之間影響力重合，本文利用相似性方法[24]來去掉影響力重合嚴重的節點，進一步提高算法的傳播范圍。該相似性方法定義節點u的相似性Su如下:

(9)

其中:N(S)和N(u)分別表示種子集合S和節點u的一階鄰居;|N(S)∩N(u)|表示它們之間交集的大小，|N(u)|是節點u的一階鄰居數量。該方法在選擇種子節點時，先基于啟發式算法選出候選節點，然后計算該候選節點的相似性，如果相似性小于給定的閾值θ，則將該節點加入種子集合，否則丟棄，迭代選擇下一個節點。加入相似性方法，提出的MPRD的偽代碼如下。

輸入：網絡G，種子節點數k，調節參數s，比例因子α;相似性閾值θ。

輸出：選出的種子節點集合S。

1)

初始化操作

2)

迭代計算每個節點的影響力

3)

對每一個節點u計算

4)

fori=1 tokdo

5)

6)

7)

ifSu<θ

8)

S=S∪{u}

9)

end for

10)

returnS

其中n為網絡中的節點數目，MPRD首先初始化每一個節點的相似性和影響力值(第1)行)。然后基于反向PageRank的思想迭代計算每一個節點的影響力(第2)行)，接著結合度中心性和PageRank計算的影響力作為最終節點的影響力(3)行)。最后基于相似性方法，選出當前影響力值最大的節點計算其相似性，如果相似性小于設置的閾值，則將該節點加入種子集合；否則丟棄，繼續上述過程直到選出k個種子節點(行4)～10))。

算法復雜度分析 MPRD基于反向PageRank迭代計算節點的影響力，通過遍歷節點的入度和出度鄰居來計算分配的影響力，需要的時間為O(r*(n+m))，其中r表示迭代的次數，n和m分別表示網絡中節點的數目和邊的數目。使用堆來存儲節點影響力，選取種子節點需要的時間為O(nlogn+n*max_d)，其中max_d表示節點的最大度，因此算法總的時間復雜度為O((r+logn+max_d)*n+rm)。本文使用鄰接鏈表存儲網絡，MPRD的空間復雜度為O(n+m)。

3 實驗結果與分析

3.1 數據和算法

本文使用6個真實世界的數據集進行實驗，這些數據集都是來自由Jure Leskovec維護的網站(http://snap.stanford.edu/data/)。這些數據集從幾千節點到幾十萬節點，類型豐富，3個無權無向圖和3個無權有向圖，詳細信息如表1所示。

表1 6個真實世界數據集信息匯總 Tab.1 Information of six real-world datasets

本文將反向PageRank算法在有向圖上記作RPageRank，在無向圖中反向PageRank退化為PageRank，RPageRank迭代計算1 000次。在MPRD中，依據原作者建議設置α=0.85，相似性閾值θ=0.9。本文從傳播范圍、運行時間，內存消耗三個方面來驗證所提算法的性能，并選擇如下6個富有代表性的算法在獨立級聯模型和權重級聯模型下進行對比實驗。算法的時間復雜度和空間復雜度如表2所示。

CELF 該算法利用目標函數的子模特性，減少蒙特卡洛模擬的次數，迭代選出影響力增益最大的節點作為種子節點，本文設置蒙特卡洛模擬次數R=10 000。

Degree 利用度中心性直接選出k個度值最大的節點作為種子節點。

PageRank 利用PageRank迭代1 000次計算節點的PR值，選擇k個PR值最大的節點。

PMC 基于剪枝的蒙特卡洛模擬算法，該算法基于節點的權重有向循環圖快速近似計算節點影響力增益，貪心思想選擇種子節點。

IMM 據我們所知，該算法是目前最好的算法之一。IMM基于反向抽樣的思想，具有近線性的時間復雜度，利用鞅分析計算達到理論保證所需要的樣本數量，本文設置ε=0.1，δ=0.01。

LAIM 該算法基于多層鄰居迭代計算節點的影響力，利用貪心思想選擇增益最大的節點，然后將選出的節點和相關的邊刪掉，重新計算節點的影響力。

表2 算法的時間復雜度和空間復雜度對比 Tab.2 Comparison of time complexity and space complexity of different algorithms

本文所有算法用C++編寫，在裝有Linux4.15系統的PC上運行，其硬件配置為3.6 GHz Inter i7- 4970處理器、8 GB內存。

3.2 參數設置

本文計算的傳播范圍就是算法選出的種子節點在某個傳播模型下通過10 000次的蒙特卡洛模擬得出的最終網絡中的激活節點數目。圖1展示了MPRD選取50個種子節點在不同s值時，兩種傳播模型下傳播范圍對比的部分結果。從圖中可以看出，總體上在獨立級聯模型下，傳播范圍隨著s值的增加而不斷增加，當s=0.8時，傳播范圍在大部分網絡中能夠達到最大；而在權重級聯模型下，傳播范圍隨著s值的增加而不斷減少，當s=0.2時，傳播范圍在大部分網絡中能夠達到最大，因此，在本文中，在獨立級聯模型下設置s=0.8，在權重級聯模型下設置s=0.2。

圖1 不同s值的傳播范圍對比Fig. 1 Comparison of propagation range of different s values

3.3 傳播范圍對比

在傳播影響圖中，X軸表示種子節點數目，Y軸表示對應種子節點數下激活的節點數目。沒有特別說明，下文提到的百分比都是在k=50的情況下得出的。

圖2展示了不同算法在6個網絡上，在獨立級聯模型，傳播概率p=0.01的情況下，選擇50個種子節點的傳播范圍。從圖中可以發現，CELF算法總是取得最高的傳播范圍，提出的MPRD和IMM、Degree、PMC在除圖(c)之外的其他五個網絡上取得和CELF幾乎一樣的傳播范圍，而在圖(c)上，提出的MPRD傳播范圍僅僅比CELF少2.7%，但是優于其他所有算法，例如MPRD比Degree、IMM、LAIM、PMC、PageRank的傳播范圍分別提高14.2%、2.4%、3%、4.8%、10.3%。IMM算法可能是參數設置太大導致傳播范圍不理想，需要說明的是IMM在圖(a)上由于內存消耗太大沒有進行實驗。

圖2 IC模型下傳播范圍對比(p=0.01)Fig. 2 Comparison of propagation range under IC model(p=0.01)

PageRank算法在所有的網絡上總是表現很差，但是RPageRank在(d)、(e)、(f)三個有向圖上傳播范圍接近最優的算法，表明反向PageRank思想的有效性。需要說明的是LAIM算法只適用于無向圖，從結果可以發現，這種基于局部鄰居迭代計算節點影響力的方法并不準確，在(a)、(b)和(c)上比最優的CELF傳播范圍分別低29%、4.7%、5.6%。總之，從IC模型的傳播影響圖上，證明提出的反向PageRank思想在有向圖上能夠取得高的傳播范圍，提出的MPRD在傳播范圍上接近CELF算法，優于其他所有算法。

圖3為不同算法在6個真實網絡中WC模型下的傳播范圍。

圖3 WC模型下傳播范圍對比Fig. 3 Comparison of propagation range under WC model

從圖3中可以看出，提出的MPRD和CELF、IMM、PMC在所有的網絡上幾乎都取得最高的傳播范圍。Degree算法在6個數據集上的傳播范圍都低于MPRD，例如在(a)、(b)、(c)、(e)上比MPRD的傳播范圍低7.4%、15.7%、22.6%、8.7%。PageRank算法在(a)和(b)上傳播范圍接近CELF算法，但是在其他4個網絡上表現較差，表明該算法的不穩定性；然而RPageRank算法在(d)、(e)、(f)三個有向圖上傳播范圍接近CELF算法，表明RPageRank算法在有向圖，WC模型下的有效性。LAIM算法在(b)和(c)上選取50個節點的傳播范圍接近最優算法，但是在其他種子節點數目下表現不穩定，例如在(c)上選擇10個種子節點的傳播范圍比CELF低28.2%。

總之，實驗結果表明，RPageRank算法在有向圖上的傳播范圍接近最優算法，提出的MPRD在所有的網絡上，兩種傳播模型下都能和當前最優的CELF取得接近的傳播范圍，而優于其他算法，證明混合反向PageRank和度中心性的MPRD對于網絡和模型的魯棒性。從結果也可以看出，Degree算法在IC模型下表現良好，但是在WC模型下表現一般，因此在IC模型下s的值設置較大，MPRD偏向選擇度大的節，而在WC模型下s的值較小，算法偏向選擇反向PageRank值大的節點，綜合兩者的優勢，提出的MPRD在傳播范圍上表現穩定。

3.4 運行時間對比

圖4顯示了不同算法在6個網絡，兩種傳播模型下，選擇50個種子節點所需要的時間。X軸表示不同網絡和算法，Y軸表示以10為底的對數坐標下的運行時間。提出的MPRD和RPageRank和PageRank運行時間相似，統一記作MRPD。從圖中可以看出：CELF算法的運行時間遠遠高于其他算法，例如在CA-HepPh網絡，IC模型下，CELF需要53 144 s，而本文提出的MPRD只需要2.2 s。Degree是運行最快的算法，而提出的MPRD的運行時間和其他算法類似，都略高于Degree。除CELF之外的所有算法在所有的網絡，兩種傳播模型下，運行時間都在100 s之內，遠遠優于CELF算法，表明這些算法能夠處理大規模的網絡。

圖4 不同算法在兩種模型上的運行時間對比Fig. 4 Running time comparison of different algorithms on two models

3.5 運行空間對比

圖5展示了不同算法在6個網絡，兩種傳播模型下，選擇50個種子節點需要的內存空間，X軸表示網絡和算法，Y軸表示內存消耗。從圖中可以看出IMM和PMC都是內存消耗的算法，例如在email網絡，IC模型下，IMM和PMC分別需要2.3 GB和1.4 GB內存，而本文提出的MPRD只需要0.099 GB內存，而且IMM算法在dblp網絡，IC模型下由于內存消耗超過機器內存而沒有進行實驗。通過內存空間對比，證明本文的MPRD相比IMM和PMC，在內存消耗方面更容易擴展到大規模的網絡上。

圖5 不同算法在兩種模型上的運行空間對比Fig. 5 Memory usage comparison of different algorithms on two models

通過在6個網絡，兩種傳播模型下，將提出的MPRD與CELF、Degree、PageRank、IMM、LAIM、PMC 6種算法從傳播范圍、運行時間、運行空間三個方面進行對比實驗。結果表明提出MPRD：在傳播范圍上接近最優的CELF算法；但是時間效率上與其他算法接近，比CELF快四、五個數量級；內存消耗上比IMM，PMC更容易擴展到大規模網絡上。總之，提出的MPRD能夠在傳播范圍、時間效率和內存消耗三個方面取得良好的平衡，能夠擴展到大規模網絡上。

4 結語

本文提出一種混合反向PageRank和度中心性的啟發式算法MPRD來解決大規模網絡上影響力最大化問題。該算法從啟發式算法的角度，結合反向PageRank和度中心性評估節點影響力，然后使用相似性方法選擇種子節點。實驗結果表明所提出的MPRD在傳播范圍上接近最優的算法，而且時間效率高，內存消耗小。該算法不足之處是參數太多。接下來的工作將從以下幾個方面進行。首先，不同網絡中最優的s是不同的，在IC模型中設置為0.8，WC模型中設置0.2只是大多數情況下最優的選擇，未來將探索最優的s值與網絡特性之間的關系，為不同網絡設置更合理的s值；其次，將探索MPRD在其他模型下的表現，例如LT模型和投票模型；最后將在網絡中加入主題信息，探索更實用的影響力最大化算法。