陳光魯 盧敏

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

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

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

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

1概述

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

2基礎知識

2.1影響力最大化問題

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

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

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

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

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

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

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

3影響力最大化傳播模型

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

3.1IC擴展模型

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

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

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

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

3.2LT擴展模型

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

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

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

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

3.3其他模型

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

4影響力最大化算法

4.1貪心算法

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

4.2啟發(fā)式算法

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

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

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

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

（2）現(xiàn)有的影響力傳播模型多數(shù)為靜態(tài)傳播模型，但現(xiàn)實社會網(wǎng)絡時時刻刻都在發(fā)生變化，如何構建有效的動態(tài)傳播模型是研究者們值得研究的重要問題。

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

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

6總結

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