陳光魯 盧敏

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

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

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

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

1概述

近年來，隨著4G網(wǎng)絡(luò)技術(shù)日漸成熟，5G網(wǎng)絡(luò)的迅速發(fā)展，微信、微博等社交軟件與抖音、今日頭條等信息傳播軟件的興起，互聯(lián)網(wǎng)與網(wǎng)絡(luò)基礎(chǔ)設(shè)施已經(jīng)改變了人們的生活方式。通過社會網(wǎng)絡(luò)傳播信息已經(jīng)成為人們?nèi)粘Ｉ钪械囊徊糠郑Ａ拷换バ畔?shù)據(jù)得到存儲，社會網(wǎng)絡(luò)的研究受到學(xué)者們廣泛關(guān)注，為研究社會網(wǎng)絡(luò)中信息傳播與擴散過程，挖掘具有最大影響力的節(jié)點集合，社會網(wǎng)絡(luò)影響力最大化問題成為研究熱點。

2基礎(chǔ)知識

2.1影響力最大化問題

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

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

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

2.3影響力最大化基礎(chǔ)傳播模型

社會網(wǎng)絡(luò)是由代表個人或組織的節(jié)點構(gòu)成的一種社會結(jié)構(gòu)，代表各種社會關(guān)系，經(jīng)由這些社會關(guān)系，把從偶然相識的泛泛之交到緊密結(jié)合的家庭關(guān)系的各種人們或組織串連起來。一般的，社會網(wǎng)絡(luò)用圖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ā)生時，傳播過程結(jié)束，且傳播過程中活躍狀態(tài)節(jié)點不能變?yōu)椴换钴S，這類傳播模型稱為漸進型模型，主要為Ic模型與LT模型;若傳播過程中節(jié)點可以由活躍切換到不活躍狀態(tài)，將這類模型稱為對稱型模型，例如傳染病模型嘲，博弈論模型。

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

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

3影響力最大化傳播模型

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

3.1IC擴展模型

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

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

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

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

3.2LT擴展模型

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

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

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

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

3.3其他模型

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

4影響力最大化算法

4.1貪心算法

貪心算法，又稱貪婪算法，該算法的思想是每次求解問題時，都去求解最優(yōu)解來得到全局最優(yōu)解。針對影響力最大化問題，Kempe等首次從離散化的角度提出了如何選擇出有影響力的種子節(jié)點，并提出用貪心算法來近似求解。貪心算法的優(yōu)點在于求解精度比較高，可以達到（1-1/e），但該算法的劣勢也很明顯，求解過程時間復(fù)雜度較高，用時較長，無法應(yīng)用到大規(guī)模社交網(wǎng)絡(luò)計算。針對這一不足，很多優(yōu)化策略被提出以優(yōu)化該算法使其能在大規(guī)模網(wǎng)絡(luò)中運行。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等在度的基礎(chǔ)上提出了DegreeDiscount算法，該算法的思想是當(dāng)一個節(jié)點有鄰居節(jié)點被選為種子節(jié)點時，在計算它的度時要打一定的折扣。Luo等提出首先用PageRank算法對網(wǎng)絡(luò)中的節(jié)點排序，再從排序較高的節(jié)點中選擇種子節(jié)點。Song等的動態(tài)網(wǎng)絡(luò)圖中搜尋種子節(jié)點，基本思想是在動態(tài)圖的網(wǎng)絡(luò)快照的基礎(chǔ)上，隨著時間的推移，每變換一張圖，就在前一階段的種子集合的基礎(chǔ)上，建立種子集合的更新策略。缺點是，算法只針對網(wǎng)絡(luò)中邊的增加和消失，權(quán)重的改變，并未考慮到節(jié)點增加或者減少帶來的影響。Chen等用最大影響力路徑來估算影響力的傳播，并據(jù)此提出了PMIA算法，有良好的性能和精確度。

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

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

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

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

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

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

6總結(jié)

社會網(wǎng)絡(luò)中影響最大化問題具有很強的學(xué)術(shù)價值與實踐意義，是近年來的研究熱點之一。本文從影響力最大化問題、影響傳播模型、影響力最大化算法三個方面進行總結(jié)歸納，對影響傳播模型與影響力最大化算法相關(guān)成果進行了介紹。隨著研究不斷深入，該方向?qū)⑷〉镁薮笸黄?，可以有效解決更多實際問題。