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

夏 欣，馬 闖，張海峰*

(1.安徽大學數學科學學院 合肥230601；2.安徽大學互聯網學院 合肥 230601)

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

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

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

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

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

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

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

1.1 影響力最大化問題描述

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

1.2 獨立級聯模型

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

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

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

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

2 改進的度折扣算法

2.1 度折扣算法

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

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

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

2.2 一階改進的度折扣算法

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

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

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

2.3 二階改進的度折扣算法

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

圖1 網絡示例圖

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

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

3 實驗與分析

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

3.1 數據集與實驗設置

表1 4個經驗網絡的結構性質

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

3.2 實驗結果

3.2.1獨立級聯模型

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

1)影響范圍

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

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

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

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

2)傳播速度

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

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

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

3)種子集性質

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

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

圖5 種子節點間平均度隨著種子數的變化情況

圖6 種子節點間平均最短路徑隨著種子數的變化情況

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

圖7 Word網絡種子節點可視化圖

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

3.2.2未知傳播率

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

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

圖8 傳播閾值近似代替傳播率時最終影響范圍

3.2.3敏感性分析

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

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

3.2.4運行時間

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

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

4 結束語

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