基于改進的度折扣方法研究社交網(wǎng)絡影響力最大化問題

夏 欣，馬 闖，張海峰*

(1.安徽大學數(shù)學科學學院 合肥230601；2.安徽大學互聯(lián)網(wǎng)學院 合肥 230601)

在線社交平臺如Twitter、Weibo、WeChat、Facebook等已經(jīng)成為人們生活中不可或缺的重要工具，引起了不同領域的學者對社交網(wǎng)絡的廣泛關注與研究，如社交網(wǎng)絡上的影響力最大化問題、鏈路預測、社團發(fā)現(xiàn)及推薦系統(tǒng)等[1-4]。其中影響力最大化問題因其普遍的應用場景而被廣泛研究，如在廣告投放和市場營銷中如何用有限的成本選擇具有較大傳播力度的人物、地點投放廣告，使得了解并且購買該產(chǎn)品的用戶最多，從而獲取最大收益。在疾病和謠言的傳播鏈中，控制網(wǎng)絡中影響力大的節(jié)點可以避免其大規(guī)?？焖賯鞑5-6]。

影響力最大化問題是指在一個網(wǎng)絡中選擇一定數(shù)目的節(jié)點作為種子集，通過激活這些種子節(jié)點，使得信息在網(wǎng)絡中傳播，最終希望網(wǎng)絡中被激活的節(jié)點數(shù)最多。影響力最大化算法主要分為3類：貪婪算法、中心性指標和啟發(fā)式算法。

在貪婪算法中，文獻[7]將影響力最大化問題定義為一個離散的優(yōu)化問題，證明了在獨立級聯(lián)模型和線性閾值模型下該問題是一個NP-Hard問題。并進一步提出了近似比為(1?1/e)的爬山貪心算法，在每一步迭代中都選擇當前邊際傳播范圍最廣的節(jié)點加入種子集。文獻[8]利用子模性提出了CELF(cost-effective lazy forward)算法，該算法大大減少了計算時間。文獻[9]提出了改進的CELF++算法，減少了不必要的計算次數(shù)。文獻[10]提出NewGreedy算法，以傳播概率保留網(wǎng)絡中的邊，根據(jù)子圖的連通性考慮節(jié)點加入種子集的增益。由于NewGreedy算法無法保證子模性，文獻[11]提出了一個靜態(tài)的貪婪算法StaticGreedy算法，能夠解決影響力最大化中的精確度可擴展性問題。貪婪算法雖然能找到影響力較大的種子節(jié)點，但其時間復雜度太高，不適用于大型網(wǎng)絡。

第二類解決影響力最大化問題的方法是基于網(wǎng)絡的拓撲結構對節(jié)點的影響力排序，使用中心性指標對網(wǎng)絡中的節(jié)點排序，選擇前K個中心性指標最大的節(jié)點作為種子節(jié)點[12]?；诰W(wǎng)絡結構定義的中心性指標有度中心性指標、接近度中心性及介數(shù)中心性等[13-16]。文獻[17]系統(tǒng)回顧了關鍵點識別中的概念和度量，并對問題和方法進行了分類，通過廣泛的實證分析，比較不同方法的適用性。此外，很多學者提出新的影響力排序方法，如文獻[18]認為種子節(jié)點應該分散在網(wǎng)絡中，定義了GCC (generalized closeness centrality)指標。文獻[19]提出網(wǎng)絡節(jié)點的H指數(shù)衡量節(jié)點的重要性。文獻[20]通過構造算子說明了節(jié)點的度、H指數(shù)和核數(shù)之間的關系，該關系被定義為DHC定理。文獻[21]結合節(jié)點的K-shell值和節(jié)點間最短路徑長度，將K-shell值看做節(jié)點重力，提出重力中心性指標。

使用中心性指標選取種子節(jié)點，忽略了節(jié)點間的重疊性，可能造成傳播過程中的冗余，為了尋找更加高效的解決方法，啟發(fā)式算法被相繼提出。如文獻[22]考慮局部影響區(qū)域迭代節(jié)點的全局影響力提出了IRIE (influence ranking influence estimation)算法。文獻[23]通過節(jié)點間的簡單路徑近似計算節(jié)點的傳播影響力，并且考慮不同的優(yōu)化方法減少擴展中迭代調用的次數(shù)，提出了Simpath算法。文獻[24]介紹了識別網(wǎng)絡中單個有影響力節(jié)點的方法、特點和性能，同時介紹利用啟發(fā)式算法尋找多個影響力節(jié)點的研究方法。文獻[25]考慮種子集到其他節(jié)點的最短路徑得到種子集影響范圍，提出SPM(shortest-path model)算法。文獻[26]基于節(jié)點相似性提出了啟發(fā)式的聚類算法，選取聚類質心作為種子節(jié)點獲得較大傳播范圍。文獻[10]基于節(jié)點的度提出了啟發(fā)式的度折扣(degree discount,DD)算法，度折扣算法比貪婪算法的運行速度快了近千倍，并且能達到與貪婪算法較為接近的效果，因此受到廣泛關注。

雖然度折扣算法具有快速、高效的特性，但該算法還有許多需要改進的地方，這些不足之處是制約該算法性能進一步提升的關鍵因素。首先，度折扣算法在計算節(jié)點的期望影響力時沒有考慮鄰居的差異性，而是簡單地認為每個未激活的鄰居節(jié)點對該節(jié)點期望影響力的貢獻是相同的，導致計算期望影響力的公式不夠精確。其次，度折扣算法沒有考慮節(jié)點之間共同鄰居數(shù)的影響，不能充分降低傳播的冗余性，比如節(jié)點i和j之間有許多共同鄰居，如果節(jié)點j已被選擇為種子節(jié)點，則節(jié)點i被感染的可能性也很高，因為他們之間有多條可能的傳播路徑，此時再選擇節(jié)點i作為種子節(jié)點會導致傳播的冗余效應[27]。針對以上兩個問題，本文首先對度折扣算法中計算期望影響力的公式進行修正，然后基于共同鄰居數(shù)引入冗余弱化效應進一步改進度折扣算法。

1 影響力最大化與傳播模型

1.1 影響力最大化問題描述

用網(wǎng)絡圖G=(V,E)表 示社交網(wǎng)絡，其中V是節(jié)點集，代表社交網(wǎng)絡中的用戶；E是邊集，代表社交網(wǎng)絡中用戶之間的關系。影響力最大化問題就是在網(wǎng)絡中找出K個節(jié)點作為種子集S，然后按照規(guī)定的傳播模型將信息傳播給鄰居節(jié)點，使得最終能影響的節(jié)點數(shù)最多。在特定的傳播模型M下，任意種子節(jié)點集S的影響力可以表示為σM(S)。因此，網(wǎng)絡上影響力最大化問題的形式化定義為：

1.2 獨立級聯(lián)模型

在獨立級聯(lián)模型(independent cascading model,IC)中，網(wǎng)絡中的節(jié)點有兩種可能的狀態(tài)：未激活態(tài)和激活態(tài)。同時為網(wǎng)絡中的每條邊(i,j)分配一個[0,1]間的概率值βij作為信息在該條邊上的傳播概率。IC模型具體傳播過程如下：

1)在t=0時刻，選定K個節(jié)點構成種子集S0，僅將種子集中節(jié)點設為激活狀態(tài)，其余節(jié)點為未激活狀態(tài)。

2)在t+1時 刻，每一個激活節(jié)點i∈St，以概率βij嘗試激活鄰居中的未激活節(jié)點j。若激活成功，則該鄰居節(jié)點j由未激活狀態(tài)轉為激活狀態(tài)，否則仍保持未激活狀態(tài)。并且每個激活節(jié)點只有一次激活鄰居的機會，無論是否成功激活，該節(jié)點在下一輪將不具有激活能力。節(jié)點j有多個種子鄰居時，每個種子鄰居都獨立的激活節(jié)點j，如種子節(jié)點i和h均 為節(jié)點j的鄰居，則j被激活的概率為1?(1?βij)(1?βhj)。

3)直到某個時刻，網(wǎng)絡中所有節(jié)點都不再具有激活其他節(jié)點能力時，傳播過程結束。

2 改進的度折扣算法

2.1 度折扣算法

度折扣算法的基本思想是：假設節(jié)點j是節(jié)點i的鄰居，如果j已被選為種子節(jié)點，那么在基于度中心性指標考慮節(jié)點i是否作為種子節(jié)點時，應該對連邊(i,j)打 折扣，因為i對j不能產(chǎn)生額外的影響。假設所有邊的激活概率都相同，均為β。當節(jié)點i的鄰居中有si個激活種子時，i被激活的概率為1?(1?β)si， 此時i節(jié)點能被鄰居節(jié)點激活，其期望影響力與直接將i節(jié)點選為種子節(jié)點的期望影響力相同，即此時選擇節(jié)點i作為種子節(jié)點不增加額外的影響力(對期望影響力的貢獻為0)。由于節(jié)點i沒有被激活的概率為(1?β)si，當節(jié)點i被選為種子時，其能激活的節(jié)點數(shù)為1+(di?si)β，其中“1”表示節(jié)點i被激活，“(di?si)β”表示被激活的鄰居數(shù)。因此考慮節(jié)點i選為種子時，其產(chǎn)生的期望影響力為：

當節(jié)點i鄰居中沒有種子節(jié)點時，i作為種子節(jié)點產(chǎn)生的期望影響力為：1 +diβ?B。設 γ是對鄰居中每個種子節(jié)點的度折扣，則siβγ?B?A，可以得到γ=2+(di?si)β，因此，當節(jié)點i有si個種子鄰居時，它的度折扣值定義為：

度折扣算法的基本步驟為：第一輪中沒有種子節(jié)點，所有節(jié)點的度都沒有被折扣，所以直接選擇網(wǎng)絡中度最大的節(jié)點作為第一個種子；接下來每一輪根據(jù)式(3)計算每個未被激活節(jié)點的度折扣值ddi，并選擇最大的一個節(jié)點加入種子集；循環(huán)更新計算直到選出K個種子節(jié)點加入種子集S。

2.2 一階改進的度折扣算法

度折扣算法認為所有非激活的鄰居對節(jié)點i貢獻的期望影響力都是相同的，即為β。實際上這些未激活鄰居對節(jié)點i貢獻的期望影響力是不同的，如節(jié)點i有兩個未激活鄰居j和l， 如果節(jié)點j的鄰居中已經(jīng)有很多種子，而節(jié)點l的鄰居中沒有種子節(jié)點，如果節(jié)點j和l均 被激活，則節(jié)點l有更大的可能性是被i激活的，而節(jié)點j很可能被其他節(jié)點激活。因此節(jié)點j和l對 節(jié)點i期望影響力的貢獻是截然不同的，如圖1a所示，其中實心黑色節(jié)點處于激活狀態(tài)，空心節(jié)點為未激活狀態(tài)?；诖?，本文對計算期望影響力的公式進行如下修正(IDD1算法)：

式中，aij表示鄰接關系，aij=0表示節(jié)點i與j沒有連邊，aij=1表 示節(jié)點i與j有連邊。在考慮節(jié)點i的期望影響力時需要考慮非激活鄰居節(jié)點自身鄰居中種子節(jié)點的數(shù)量，若這些非激活鄰居周圍種子節(jié)點越多，則對i貢獻的期望影響力越小。

IDD1算法的基本步驟為：第一輪中直接選擇網(wǎng)絡中度最大的節(jié)點作為第一個種子；接下來每一輪根據(jù)式(4)計算每個非激活節(jié)點的期望影響力Iei，選擇最大的一個節(jié)點加入到種子集；循環(huán)更新計算直到選出K個種子加入S。

2.3 二階改進的度折扣算法

在選擇多個節(jié)點作為種子節(jié)點時，除了要考慮節(jié)點自身的重要性，另一個重要因素是如何確保種子節(jié)點在網(wǎng)絡上分布充分分散，避免傳播的冗余性?？紤]如下情景：節(jié)點i與節(jié)點j之間有許多共同鄰居，對于IC模型而言，若節(jié)點j已經(jīng)被選擇為種子節(jié)點，則節(jié)點i有很大的概率被激活(通過直接連邊激活和多個共同鄰居激活)，此時再選擇節(jié)點i作為種子節(jié)點對提高傳播影響力的作用是非常有限的，因此選擇的種子節(jié)點之間應該避免有多個共同鄰居的情況，如圖1b所示。基于此，本文在IDD1算法基礎上引入基于共同鄰居數(shù)的冗余弱化機制，保證種子節(jié)點的分布足夠分散。令Cij為節(jié)點i和j的共同鄰居數(shù)，定義節(jié)點i的影響期望力為Cei，則：

圖1 網(wǎng)絡示例圖

式中， α>0是可調參數(shù)，如果 α太大會導致所有鄰居的貢獻為0，若 α太小會導致鄰居的貢獻差異性被忽略，本文取α =0.05。

IDD2算法的基本步驟如下：首先選擇網(wǎng)絡中度最大的節(jié)點作為第一個種子；之后每一輪根據(jù)式(5)計算其他未激活節(jié)點的Cei，選擇 Cei值最大的節(jié)點作為種子；循環(huán)更新計算直到選出K個種子加入S。

3 實驗與分析

本文在4個真實網(wǎng)絡上對本文提出的IDD1算法和IDD2算法進行性能測試，使用IC模型與一些啟發(fā)式算法進行比較，包括度折扣算法(DD)、度中心性算法(degree)以及隨機選擇種子算法(random)。本文沒有與貪婪算法進行比較，一方面是因為貪婪算法的時間復雜度太高，對于規(guī)模上萬的節(jié)點非常耗時。另一方面，如文獻[10]所述，度折扣算法雖然是一種啟發(fā)式算法，但是該算法的性能接近于貪婪算法。實驗結果表明了本文提出的IDD1算法和IDD2算法性能均優(yōu)于度折扣算法，因此更接近于貪婪算法。另外這兩個算法均是基于局部網(wǎng)絡結構的啟發(fā)式算法，與度折扣算法的時間復雜度接近。

3.1 數(shù)據(jù)集與實驗設置

表1 4個經(jīng)驗網(wǎng)絡的結構性質

本文使用IC模型作為傳播模型，每條邊上的激活概率均為β，從最終激活節(jié)點的比例、傳播速度以及運行時間3方面比較不同算法的優(yōu)劣性。為了保證結果的可靠性，所有方法均獨立傳播1000次取平均結果。

3.2 實驗結果

3.2.1獨立級聯(lián)模型

本文在4個真實網(wǎng)絡上比較了不同算法選擇種子集的影響范圍和傳播速度，并且定義了種子集的平均度和平均最短路徑長度解釋模型的有效性。

1)影響范圍

圖2顯示了不同算法產(chǎn)生的最終傳播范圍隨著種子數(shù)K的變化情況，用 σ(S)表示激活節(jié)點占網(wǎng)絡的比例。前3個網(wǎng)絡的傳播率均設為0.1，由于第4個網(wǎng)絡傳播閾值較小，傳播率設置為0.06。由圖2可知：度折扣算法比度中心性算法以及隨機算法更能提高傳播范圍，而本文提出的IDD1算法雖然只是對度折扣算法的公式進行簡單修正，但實驗結果表明該算法在4個真實網(wǎng)絡均優(yōu)于度折扣算法。當考慮冗余弱化機制時，IDD2算法能夠更加明顯地提高擴散范圍。對于網(wǎng)絡規(guī)模比較小的TAP網(wǎng)絡而言，在種子數(shù)較小時，IDD1算法優(yōu)勢比較明顯，而對于較大的網(wǎng)絡而言，IDD1的優(yōu)勢在種子數(shù)較多時能更加凸顯。

圖2 最終影響范圍隨著種子數(shù)的變化情況

圖3是在固定種子數(shù)的情況下進一步研究最終傳播范圍隨著不同傳播概率β的變化情況，其中TAP網(wǎng)絡20個種子，Ca-GrQc和PGP網(wǎng)絡50個種子，Ca-CondMat網(wǎng)絡70個種子。實驗結果再次表明，IDD1算法比度折扣算法更能提高擴散范圍，而引入冗余弱化機制的IDD2算法則在所有網(wǎng)絡上都是效果最顯著的。

圖3 最終影響范圍隨著傳播率的變化情況

2)傳播速度

本文在固定種子數(shù)量以及傳播率β的情況下，比較不同算法對傳播速度的影響，如圖4所示。其中，TAP網(wǎng)絡固定β=0.1，K=20；Ca-GrQc網(wǎng)絡和PGP網(wǎng)絡固定β=0.1，K=50；Ca-CondMat網(wǎng)絡固定β=0.06，K=70。t表示信息傳播的迭代過程，用σt(S)記錄每次傳播后網(wǎng)絡中激活節(jié)點比例。從實驗結果可以看出IDD1算法從一開始就以較快的速度擴散信息，并且最終傳播范圍也高于已有算法。

圖4 影響范圍隨著時間的變化情況

IDD2算法在前幾步傳播過程中傳播范圍略低于度折扣算法和IDD1算法，這是由于IDD2算法選擇的種子在網(wǎng)絡中較為分散，因此需要經(jīng)過一個短暫的醞釀過程。經(jīng)過一小段時間后(3～6個時間步)，IDD2算法的傳播速度快速反超其他算法，并且得到的最終傳播范圍在所有算法中最廣。從圖2～圖4可以發(fā)現(xiàn)，無論是最終傳播范圍還是傳播速度，相比于其他算法，IDD1和IDD2算法都能取得更好的性能。

3)種子集性質

式中，Lij是 節(jié)點i和節(jié)點j的最短路徑長度；〈L〉S指標越大，種子之間越分散。

此外，種子節(jié)點的平均度〈d〉S隨種子數(shù)的變化情況如圖5所示，而種子節(jié)點間平均最短路徑〈L〉S隨種子數(shù)的變化情況如圖6所示。其中TAP網(wǎng)絡、Ca-GrQc網(wǎng)絡和PGP網(wǎng)絡的傳播率設為0.1，Ca-CondMat網(wǎng)絡的傳播率設為0.06。從圖5和圖6可以發(fā)現(xiàn)，雖然度中心性算法能保證種子節(jié)點的〈d〉S最大，但是基于該算法得到的〈L〉S值均小于度折扣算法以及IDD1和IDD2算法對應的值。反之，雖然隨機算法能保證種子節(jié)點的〈L〉S值最大，但是 〈d〉S值最小。度中心性算法和隨機算法只能保證影響力最大化中兩個關鍵因素中的某一條：1)種子節(jié)點自身很重要；2)種子節(jié)點足夠分散地分布在網(wǎng)絡上。度折扣算法以及改進算法得到的〈d〉S值雖然小于度中心性算法對應的值，但是遠高于隨機算法得到的值，并且〈L〉S大于度中心性算法對應的值。因而度折扣算法及改進算法平衡了種子節(jié)點自身的重要性和種子節(jié)點之間距離兩個因素，可以更有效地擴大傳播范圍。尤為重要的是，雖然IDD1選擇的種子節(jié)點的〈d〉S值以及〈L〉S值和度折扣算法對應的值都非常接近，但是該算法的傳播范圍更廣、傳播速度更快(如圖2～圖4)。因為IDD2算法充分考慮了冗余弱化機制，所以該算法得到的〈L〉S值比其他非隨機算法得到的值都大。當然，基于IDD2算法選出的種子節(jié)點的〈d〉S值也一定程度地變小，但是遠高于隨機算法得到的〈d〉S值。IDD2算法在IC模型中的最優(yōu)性能也說明，對于IC模型而言，種子節(jié)點間的分散程度是能否保證影響力最大化的一個尤為重要的因素。

圖5 種子節(jié)點間平均度隨著種子數(shù)的變化情況

圖6 種子節(jié)點間平均最短路徑隨著種子數(shù)的變化情況

為了更為直觀地表明改進算法選取出種子節(jié)點的特點，本文對Word網(wǎng)絡[31]進行可視化分析，圖7中節(jié)點的大小與度成正相關。分別使用度中心性算法、IDD1算法和IDD2算法選取20個種子節(jié)點，傳播率設為0.1。種子節(jié)點在網(wǎng)絡中用實心黑點標記，通過可視化可以直觀地看出，IDD1算法選出的種子節(jié)點仍包含了部分大度節(jié)點，IDD2算法選取的種子節(jié)點則更加均勻地分散在網(wǎng)絡中，種子節(jié)點的度也相對減小。

圖7 Word網(wǎng)絡種子節(jié)點可視化圖

另外也測試了這些算法在線性閾值模型(linear threshold model,LT)中的性能，IDD1算法效果仍優(yōu)于度折扣算法，然而IDD2算法在LT模型中效果一般，這是由于當種子節(jié)點過于分散時，LT模型的激活條件難以滿足，故不適用于LT模型。

3.2.2未知傳播率

在度折扣算法中，作者假設節(jié)點真實傳播率是已知的，因而利用真實傳播率計算節(jié)點的期望影響力，但在實際情況下，鑒于問題的復雜性，很難知道真實傳播率的大小。為了解決此問題，一個科學、折中的方法是用傳播閾值近似代替真實傳播率，這樣做的合理性在于：傳播率太小信息不能傳播，而傳播率太大時，任何一種方法都能使得信息大范圍傳播，此時再研究哪種方法能保證影響力最大沒有太大意義。接下來的問題是：如果基于傳播閾值計算式(3)～式(5)，IDD1算法和IDD2算法是否仍然具有更優(yōu)異的表現(xiàn)。

圖8顯示了傳播閾值近似代替?zhèn)鞑ヂ蕰r最終影響范圍。將前3個網(wǎng)絡的真實傳播率設為0.1，第4個網(wǎng)絡的真實傳播率設為0.06，而期望影響力是用 βth代 替 β計算得到的，然后比較了不同算法對最終影響范圍σ(S)的影響。從圖8可以發(fā)現(xiàn)，對于IC模型而言，IDD1算法依然優(yōu)于度折扣算法，IDD2算法在檢查影響力最大化方面的性能更加突出。

圖8 傳播閾值近似代替?zhèn)鞑ヂ蕰r最終影響范圍

3.2.3敏感性分析

考慮IDD2算法中參數(shù)α的取值情況，本文進行了敏感性分析，其中TAP網(wǎng)絡固定 β=0.1，K=20；Ca-GrQc網(wǎng)絡和PGP網(wǎng)絡固定 β=0.1，K=50，Ca-CondMat網(wǎng)絡固定β=0.06，K=70。針對不同的網(wǎng)絡，如果網(wǎng)絡較為稠密，則節(jié)點共同鄰居數(shù)較多；若網(wǎng)絡較為稀疏，共同鄰居數(shù)很少。此時若α太大，指標將趨于0，若α 太小，鄰居的貢獻差異性易被忽略，因此本文在[0,0.1]的范圍內(nèi)觀察IDD2算法的性能。當α=0時，IDD2算法退化為IDD1算法，即為IDD1算法的最終影響范圍。從圖9可以看出 α取值在0.01～0.1時，IDD2算法效果均優(yōu)于IDD1算法，并且α取值為0.02～0.1時，效果相對穩(wěn)定，因此本文將實驗參數(shù)統(tǒng)一為0.05。

圖9 參數(shù)α 對IDD2算法的最終影響范圍的影響

3.2.4運行時間

圖10比較了不同算法選擇50個種子的運行時間，TAP網(wǎng)絡、Ca-GrQc網(wǎng)絡和PGP網(wǎng)絡傳播率設為0.1，Ca-CondMat網(wǎng)絡設為0.06。由圖可知，IDD1算法和IDD2算法的運行時間略高于度折扣算法?？紤]冗余弱化機制的IDD2算法運行時間最長，這是因為在考慮節(jié)點度折扣時需要考慮每個鄰居節(jié)點的種子鄰居數(shù)，故復雜度要高于原度折扣算法，但度折扣算法相較于貪婪算法仍然具有高效性。

圖10 不同算法選擇種子節(jié)點的運行時間

4 結束語

研究社交網(wǎng)絡影響力最大化問題具有重要的理論意義和應用價值，在眾多檢測算法中，由于度折扣算法具有快速、高效的性能，受到學者們的廣泛關注。考慮到度折扣算法在計算節(jié)點期望影響力時沒有區(qū)別對待鄰居中未激活節(jié)點的差異性，本文對計算期望影響力的公式進行了修正，得到了一階改進的度折扣(IDD1)算法。為了進一步保證選擇的種子節(jié)點充分分散地分布在網(wǎng)絡上，本文提出了二階改進的度折扣(IDD2)算法。通過在4個真實網(wǎng)絡上的實驗結果表明，IDD1算法影響的最終傳播范圍和傳播速度均優(yōu)于度折扣算法，而IDD2算法在IC模型上擴大影響力范圍的效果尤為突出。通過計算種子節(jié)點之間的平均度以及平均距離，闡述了為何本文提出的算法能更有效地擴大傳播范圍。此外，考慮到真實傳播率難以獲取，本文利用傳播閾值代替真實傳播率計算期望影響力，研究結果表明本文提出的算法依然有效。