社會網絡影響力最大化問題研究

陳光魯 盧敏

摘要：社會網絡影響力最大化是社會網絡分析領域的一個重要研究問題，該問題旨在尋找出社會網絡中具有最大影響力的節點集合。從社會網絡影響力最大化問題產生背景出發，介紹影響力最大化問題的求解過程與求解過程中用到的基礎模型，歸納總結了現有的幾種主要傳播模型、影響力最大化算法及研究現狀。最后，討論了該研究存在的問題和對未來的展望。

關鍵詞：社會網絡;傳播模型;影響力最大化算法

中圖分類號：TP393 文獻標識碼：A

文章編號：1009-3044（2019）32-0036-03

1概述

近年來，隨著4G網絡技術日漸成熟，5G網絡的迅速發展，微信、微博等社交軟件與抖音、今日頭條等信息傳播軟件的興起，互聯網與網絡基礎設施已經改變了人們的生活方式。通過社會網絡傳播信息已經成為人們日常生活中的一部分，海量交互信息數據得到存儲，社會網絡的研究受到學者們廣泛關注，為研究社會網絡中信息傳播與擴散過程，挖掘具有最大影響力的節點集合，社會網絡影響力最大化問題成為研究熱點。

2基礎知識

2.1影響力最大化問題

影響力最大化問題最初由Domingos和Richardsom提出的I”，即給定一個社會網絡G（V，E），通過特定的影響力傳播模型進行模擬，找到含有K個節點的種子節點集合S（K為整數，且小于給定網絡中的節點數），使得在影響力下激活的種子節點數量最多，公式如下：

2.2求解影響力最大化問題流程圖

影響力最大化問題是依據影響力傳播模型與影響力最大化算法進行求解。影響力傳播模型主要為獨立級聯（Indepen-dent Cascade，IC）模型與線性閾值（Linear Threshold，LT）模型以及它們的擴展模型，影響力最大化算法分為兩類，分別為貪心算法和啟發式算法。求解該問題時，影響力傳播模型與影響力最大化算法是同時存在的，影響力傳播模型的構建影響影響力最大化算法的選擇。求解影響力最大化問題流程圖如圖1。

2.3影響力最大化基礎傳播模型

社會網絡是由代表個人或組織的節點構成的一種社會結構，代表各種社會關系，經由這些社會關系，把從偶然相識的泛泛之交到緊密結合的家庭關系的各種人們或組織串連起來。一般的，社會網絡用圖G（V，E）表示，其中y代表節點集合，E代表邊集，G（V，E）中節點只有兩種激活狀態，分別為活躍（active）狀態、不活躍（inactive）狀態。活躍狀態的節點可以通過一定的概率去激活不活躍狀態的鄰居節點，直到激活行為不再發生時，傳播過程結束，且傳播過程中活躍狀態節點不能變為不活躍，這類傳播模型稱為漸進型模型，主要為Ic模型與LT模型;若傳播過程中節點可以由活躍切換到不活躍狀態，將這類模型稱為對稱型模型，例如傳染病模型嘲，博弈論模型。

在真實社會網絡中，一個人被朋友影響后，顯然這個人并不切換到未受影響的狀態。因此，漸進型模型相比于對稱型模型更適合描述真實的社會網絡中影響傳播。因此，研究社交網絡中影響最大化問題的主要的兩個基本傳播模型是獨立級聯模型和線性閾值模型。

獨立級聯（IC）模型是一種概率模型，該模型在社會網絡圖G（V，E）中各個節點之間都會給定一個在【0，1】的傳播概率p_u，v，即每條邊的概率值;給定一個激活節點集Ao，集合中每個節點“以概率值pu，v去激活自己的鄰居節點v，同時每個節點只有一次機會去激活鄰居節點，一旦失敗，就永遠不能再次激活。假如在激活過程，有節點同時去激活同一個鄰居節點，則該節點會隨機排序被激活順序，使得該激活過程在同一時刻激活完成;當社會網絡中沒有節點進行激活行為時，該傳播過程結束。

3影響力最大化傳播模型

影響力最大化傳播模型的構建直接影響傳播結果，因此，傳播模型在影響力最大化問題中占有至關重要的位置。IC模型與LT模型對現實生活中不同場景下都具有一定的通用性，但也并不完全適用于不同的場景，在不同場景下的構建不同的傳播模型是非常有必要的。因此，基于兩類基礎模型的擴展模型被提出。

3.1IC擴展模型

2003年，Kempe等州首次提出應用獨立級聯模型解決影響力最大化問題。隨后，Kempe等嗍于2005年又提出了一個遞減級聯模型（DCM），該模型考慮了節點間影響衰減效應，當一個節點被其鄰居節點多次激活后，則再有新的鄰居節點激活時概率會下降。

2016年，Hosseini-Pozveh等針對真實社會網絡中存在的不信任因素提出了IC的擴展模型，該模型稱為符號感知級聯（sc）模型，該模型利用真實社會網絡中的不信任因素規定為主動節點對節點執行相反動作或采納相反意見進行建模。

2018年，劉勇等依據TIC模型進一步提出了基于主題一興趣的獨立級聯（TI-IC）模型，該模型利用EM算法求解用戶興趣的主題分布和傳播項的主題分布，通過蒙特卡洛模擬的方法來計算用戶間的影響概率，TI-IC模型與TIC模型相比，TI-IC模型考慮了用戶之間的主題興趣愛好，TIC模型只考慮了朋友之間的興趣在不同主題上的分布程度。

2019年，Hosseini-Pozveh等對真實的網絡中存在的不信任因素提出另一種方案，真實社會網絡中的不信任因素規定為主動節點對節點不再執行相應的動作或采納相應的意見，相應的基于Ic模型擴展構建了包含堵塞節點的符號感知級聯（SC-B）模型，通過與sC模型對比，證明了真實社會網絡中存在不信任因素時節點往往不再執行相應的動作或采納相應的意見。

3.2LT擴展模型

2003年，Kempe等首次提出應用線性閾值模型解決影響力最大化問題。

2016年，Wang等提出了多級姿態的線性閾值模型（LT-MLA），該模型與傳統的線性閾值模型相比，增加了捕捉用戶交互態度狀態和能力。

2018年，張云飛等㈣提出了關聯影響力線性閾值模型（CLT，該模型充分考慮了不同信息傳播過程中的相互促進關系，增加了信息傳播過程的準確性。

2019年，Hosseini-Pozveh等基于線性閾值模型，提出了包含消極節點的信任生成閾值（TG-T-N）模型與包含堵塞節點的信任生成閾值（TG-T-B）模型，同樣證明了真實社會網絡中存在不信任因素時節點往往不再執行相應的動作或采納相應的意見。

3.3其他模型

影響力最大化是一個應用性很強的問題，應用領域廣泛。因此，除基于Ic模型和IT模型的擴展模型外，還有其他傳播模型。如Wang等人提出了一種新的影響擴散模型一流體擴散（Fluidspread）模型，該模型利用流體動力學理論揭示了影響擴散的時間演化過程。譚振華等㈣基于引力學思想提出了一種新的謠言傳播模型GPRModel，該模型充分考慮了用戶間的關系、信息在用戶間的傳播關系、謠言接觸率與轉發率對用戶的影響，對謠言信息的傳播進行量化，構建出GPRModel。

4影響力最大化算法

4.1貪心算法

貪心算法，又稱貪婪算法，該算法的思想是每次求解問題時，都去求解最優解來得到全局最優解。針對影響力最大化問題，Kempe等首次從離散化的角度提出了如何選擇出有影響力的種子節點，并提出用貪心算法來近似求解。貪心算法的優點在于求解精度比較高，可以達到（1-1/e），但該算法的劣勢也很明顯，求解過程時間復雜度較高，用時較長，無法應用到大規模社交網絡計算。針對這一不足，很多優化策略被提出以優化該算法使其能在大規模網絡中運行。Leskove等根據問題的子模性提出了CELF算法，使算法的執行效率提升700多倍。Goyal等人進一步優化了CELF算法，提出了CELF++算法，與CELF算法相比，CELF++算法將效率提高了35%～55%。另外，Chen等㈣提出了兩種改進的貪心算法NewGreedy和MixedGreedy，進一步對傳統貪心算法進行了優化。

4.2啟發式算法

針對貪心算法的低效性，近年來涌現出了大量啟發式算法。Chen等在度的基礎上提出了DegreeDiscount算法，該算法的思想是當一個節點有鄰居節點被選為種子節點時，在計算它的度時要打一定的折扣。Luo等提出首先用PageRank算法對網絡中的節點排序，再從排序較高的節點中選擇種子節點。Song等的動態網絡圖中搜尋種子節點，基本思想是在動態圖的網絡快照的基礎上，隨著時間的推移，每變換一張圖，就在前一階段的種子集合的基礎上，建立種子集合的更新策略。缺點是，算法只針對網絡中邊的增加和消失，權重的改變，并未考慮到節點增加或者減少帶來的影響。Chen等用最大影響力路徑來估算影響力的傳播，并據此提出了PMIA算法，有良好的性能和精確度。

5影響力最大化問題存在的問題與展望

影響力最大化問題存在的問題及展望：

（1）影響力最大化問題中構建傳播模型至關重要，現實中不同場景下構建的傳播模型不同，如何針對不同的場景，構建有效且適合該場景的模型，值得研究者們注意。

（2）現有的影響力傳播模型多數為靜態傳播模型，但現實社會網絡時時刻刻都在發生變化，如何構建有效的動態傳播模型是研究者們值得研究的重要問題。

（3）影響力最大化算法主要分為貪心算法和啟發式算法，貪心算法時效差，啟發式算法精度低，如何保證精度高的情況下，時效高的算法有待研究。

（4）現實世界中的復雜網絡有很多，如交通系統中的城市網、生態系統中的神經元網等等，能否將影響力最大化問題應用到這些復雜網絡中，來解決復雜網絡中的相關問題。

6總結

社會網絡中影響最大化問題具有很強的學術價值與實踐意義，是近年來的研究熱點之一。本文從影響力最大化問題、影響傳播模型、影響力最大化算法三個方面進行總結歸納，對影響傳播模型與影響力最大化算法相關成果進行了介紹。隨著研究不斷深入，該方向將取得巨大突破，可以有效解決更多實際問題。