社交網絡影響最大化問題研究綜述

王春佳

（西華大學計算機與軟件工程學院，成都610039）

0 引言

在線社交網絡是一種社會個體之間用來分享生活、學習、經驗和觀點的工具和平臺。在線社交網絡又被稱為社交網絡。社交網絡具有平民性、非專業性、無門檻性。社交網絡成為社會個體之間的信息傳播的一種新的方式。因此，在線社交網絡中的信息傳播在多個領域引起了廣泛研究，包括計算機科學、流行病研究等，并成為社交網絡分析中的一個重點研究問題。

信息傳播最大化，又稱影響最大化，是信息傳播研究領域中的一個研究內容，由于其具有的實際研究價值，近年來受到了廣泛關注。本文主要圍繞在線社交網絡（本文關注微博客類，即Twitter、微博）中影響最大化問題的相關研究工作展開綜述，首先概述了社交網絡中的信息傳播并分析了其特點；其次，介紹了國內外研究者對影響最大化問題所做的各類研究工作；最后，對這類研究存在的問題和未來的研究方向進行了概述。

1 社交網絡上的信息傳播

1.1 信息傳播

信息傳播是個人、組織和團體通過符號和媒介交流信息，向其他個人或團體傳遞信息、觀念、態度或情意，以期發生相應變化的活動。在古時候，信息傳播使用的是飛鴿傳書、烽煙、風箏、孔明燈、飛騎、煙花爆竹、派遣信使等。不論是采用的是哪種方式，信息的傳播都受到了地域和時間的限制。后來，由于科技的飛速發展，信息傳播的方式發生改變，出現電話、電報傳真、手機短信、電視等進行信息傳播的媒介。這些現代信息傳播速度較快，但信息量小。隨著互聯網的興起，互聯網被稱為繼報紙、廣播、電視三大傳統媒體之后的“第四媒體”。基于互聯網的網絡媒體集三大傳統媒體的諸多優勢為一體，是跨媒體的數字化媒體。互聯網使信息傳播更快捷、更方便。信息傳播具有以下幾個方面的特點：第一，傳播表現為傳播者、傳播渠道（媒介）、接收者等一系列傳播要素之間的傳播關系；第二，傳播過程是信息傳遞和信息接收的過程，也是傳播者與接收者信息資源共享的過程；第三，傳播者與接收者、相關人群之間，由于信息的交流而相互影響、相互作用。

1.2 社交網絡中信息傳播的特點

微博客類社交網絡中的信息傳播是通過用戶之間的發布行為進行的。信息傳播過程的參與者為：信息發布者、信息內容、信息接收者。

（1）信息發布者

原作者：信息原始內容的編輯者和發布者。

分享者：對信息感興趣，添加內容或不添加內容進行再次發布的信息接收者。

（2）信息內容

信息原文：其中顯示內容信息和原文作者。

加工信息：再次發布的信息接收者所編輯的內容。

（3）信息接收者

能夠接收到傳播過程中的原作者或分享者發布的信息的社交網絡用戶。

信息的發布者和信息的接收者之間是存在單向的或雙向的關聯關系的。“信息發布者-（信息內容）-信息接收者”為信息傳播過程的“元過程”。社交網絡中的信息傳播是由無數個這樣的“元過程”組成。

2 傳播模型

信息傳播最大化問題，又被稱為影響最大化問題（Influence Maximization）。Domingos 和Richardson 是第一個研究影響最大化的人[1-2]。影響最大化問題最早是由Kempe 和Kleinberg[3]描述為一個離散優化算法問題。它研究的對象是一個社交網絡圖，表示為有向圖或無向圖G=（V,E），其中V 表示G 中節點的集合（對應社交網絡中的用戶），E 表示G 中邊的集合（對應社交網絡中用戶之間的社交聯系）。影響最大化問題旨在從G 中找到k 個用戶，這k 個用戶他們所能影響到的用戶范圍最大。由于影響最大化問題中的用戶之間的影響是通過用戶間的信息傳播過程進行定義和量化的，我們先回顧影響最大化問題中所使用的幾類常用的傳播模型。

2.1 獨立級聯模型（Independent Cascade Model，IC）

獨立級聯（IC）是經典常用的且被許多研究者研究使用過的傳播模型[4]。在獨立了級聯模型中，一個社交網絡表示為圖G=( )V,E ，V 為節點集，E 為邊集，每條邊e( u → v )有一個概率puv，puv表示節點u 把其鄰居v 激活的概率。在傳播過程開始的t0時間指定種子集S，這個傳播過程從種子集開始以離散化的時間步驟進行傳播。傳播過程以下述原則進行。在時間t，每個激活狀態的節點u 都嘗試以成功概率puv去激活其指向的每個未激活鄰居v。在此過程中，每個激活節點只能嘗試激活其指向鄰居一次。也就是說一旦這個節點嘗試過激活其指向鄰居，不論其鄰居是否被激活，之后的時間步驟中只是保持激活狀態而不進行激活行為。直到沒有新節點再被激活，整個傳播過程就停止。

2.1 線性閾值模型（Linear Threshold Model，LT）

2.3 觸發模型（Triggering Model，TR）

Kempe 等人[3]提出了可概括IC 和LT 模型的觸發模型（TR）。觸發模型的主要思想在于：對于給定的節點v，分配觸發節點集Tv代替LT 中的閾值，即如果Tv中有節點在步驟t-1 被激活，則v 在步驟t 中被激活。與IC 和LT 模型一樣，觸發模型的整個傳播過程也是離散時間的。傳播過程描述如下：

（1）首先為網絡圖G 中的每個節點隨機選擇一個觸發節點集Tv，Tv是v 的所有鄰居的集合的一個子集，以及選擇一個已激活節點的集合作為初始的種子集；

（2）步驟t 中，對于還未被激活的節點v 而言，只要Tv中有一個節點u 在步驟t-1中被激活，則v 被激活；

（3）重復上個步驟，直到沒有新節點再能被激活，整個傳播過程結束。

2.4 其他模型

不論是IC 模型，還是LT 模型，亦或是TR 模型，都是以離散步驟進行傳播的，即不再有新的節點被激活時停止。然而在實際情況中，傳播過程中節點之間的影響是與時間相關的。因此，有研究者針對這個問題開展了相關研究[7-8]。基于IC 模型的連續時間（Continuous-Time，CT）模型[7]認為節點之間成對傳播的可能性是時間的連續分布。即節點u 的激活時間tu和其鄰居被u 所激活的時間tv滿足條件分布p( tv|tu;αu,v)，其中αu,v為參數。CT 模型預先會給定一個停止時間T>0，時間T 內沒有新節點被激活，傳播過程停止。DynaDiffuse 模型[8]認為節點的傳播速率隨時間呈指數下降趨勢。即給定節點u 的激活時間tu和u 激活v 的初始概率，則u 在時間tv>tu將v 激活的概率為。

又有研究者提出傳播過程中網絡結構是可能發生變化的。Tong 等人[9]提出了動態獨立級聯（Dynamic Independent Cascade，DIC）模型，該模型能夠追蹤真實的社會網絡的動態拓撲結構。在DIC 模型中，種子節點可能以一定的概率無法被激活并且兩個用戶之間的傳播概率服從一個分布，由此來反映一個社會網絡拓撲結構的變化。

3 影響最大化問題

3.1 基于貪心算法的算法

2003 年，Kempe 等人[3]從離散優化的角度提出如何選擇有影響力的種子問題，并證明了該問題是NP 難問題。同時證明了傳播影響函數的次模性并提出了一種近似比為1-1/e-ε 的貪心算法，其中ε 是與社交圖G 和r 相關的常數，r 是計算E[I（S）]估計值時的測量次數。基于IC 和LT，該算法從初始化S 為空集開始，通過向種子集S 中并入使得傳播影響范圍的期望E[I（S）]增長最大的節點，直到種子集S 中包含k 個節點，算法結束。

由于簡單貪心算法的計算時間很長，通過進一步研究次模性質，Leskovec 等人[10]提出了CELF 算法，該算法利用影響函數的子模屬性來計算影響擴散。而后，經過進一步的研究，Goyal 等人[11]提出了CELF++算法優化CELF，并提高了效率。UBLF[12]使用矩陣分析技術減少了CELF 的計算次數，并實現了2 倍到10 倍的加速。Lu 等人[13]提出了CascadeDiscount 算法，使用從ScoreCumulate 模型評估的初始影響中去除節點對鄰居的影響損失來估計節點的邊際收益從而達到減少計算時長的目的。同樣的有好些研究工作[14-15]也對貪心算法進行過改進。雖然改進的貪心算法在傳播概率較小的網絡中性能良好，但是當網絡規模很大或傳播概率很大時，依然是高耗時。

3.2 基于啟發式的算法

最早Domingos 和Richardso[1-2]提出了影響最大化問題：如何從社交圖中尋找t 個初始節點，使得信息的最終傳播范圍最廣，并提出選擇全局影響最大用戶的啟發式算法。啟發式算法避免傳播概率對算法運行時間的影響。

2009 年，Chen 等人[16]提出了新的度折扣啟發式算法，該算法非常有效并且能夠產生良好的影響傳播，其時間復雜度為O（klogn+m）。在提出的方法中，最初將每個節點的度視為其影響力的指標，并以k 步迭代選擇種子。每個迭代步驟中，將影響力最高的節點作為新成員添加到種子集中。如果將節點v 作為新成員添加到集合中，則其鄰居的影響力降低，并且隨后它們被選擇為種子的機會降低。還有一些研究工作[17-18]也是采用這樣的方式。

Bao 等人[19]提出了一種啟發式聚類方法，首先確定每對節點之間的相似度，然后將節點聚類為k 個不同的聚類。然后，選擇每個群集中最具影響力的節點作為種子的成員。

Jiang 等人[20]提出了一種預期擴散值（EDV）度量來近似估計潛在候選種子節點的影響，并采用模擬退火算法來優化和識別有影響的節點。Gong 等人[21]改進EDV，并使用粒子群優化（PSO）算法最大化目標函數。Cui 等人[22]提出了一種使用差分進化算法最大化EDV函數找到種子集的方法。除了節點的影響外，還可以考慮將預算約束定義為IM 的優化問題[23-24]。

3.3 基于反向影響采樣的算法

2014 年，Borgs 等人[25]發現沒有必要對整個圖進行計算而提出一種新的算法思想，即反向影響采樣（Reverse Influence Sampling）。根據RIS 的思想，如果一個節點經常以“影響者”的身份出現，那么它可能是最有影響力的節點的良好候選者。基于該思想Borgs等人[25]提出了一種基于閾值的方法（RIS）。該算法需要運行O( ε-3· k·( n+m)·log2n )，并且以不小于1-1/n-1的概率得到近似比為1-1/e-ε 的近似解。

為了優化生成的子圖的數量和采樣方案，研究者提出了許多改進的方法來緩解基本RIS 算法的不足。Youze Tang 等人[26]提出了TIM 算法，通過使用組合可達性草圖來逐步選擇種子節點，其預期時間復雜度為O( ε-2· ( n+m)·log n )。此外通過改進參數估計，提出了TIM+算法。TIM＋算法具有與TIM 相同的最壞情況下的時間復雜度，但表現出的經驗性能更好。進一步地，唐等人提出IMM[27]來改進TIM/TIM+，IMM 使用一組基于martingale 分析的估計技術，取得比TIM/TIM+更好的性能。

Nguyen 等人[28]提出了兩種命名為SSA 和D-SSA的新穎采樣框架用于IMM[27]方法的優化。盡管基于采樣的算法可以在大規模網絡中有效地選擇k 個有影響力的種子節點，但是它們不可避免地會遭受巨大的存儲成本的問題，因為必須生成大量的RIS 樣本才能提供近似的保證，尤其是在大規模網絡中。為了減少內存消耗，Wang 等人[29]提出一種惰性采樣技術（BKRIS），將IMM[25]速度提高了兩個數量級。

3.4 上下文感知影響最大化

近幾年來，一些研究工作不再聚焦如何從算法層面對影響最大化問題進行研究，而是開始研究基于上下文感知的影響最大化問題。這類問題對傳統的IM問題進行擴展，進一步考慮上下文特征，例如主題，時間和位置。基于主題的影響最大化問題：這類問題需要考慮被傳播內容中的主題信息。這類研究問題又可被細分為節點主題感知[30-31]和邊主題感知[32-33]，均有相關的研究工作開展。基于時間的影響最大化問題：傳統IM 算法是在沒有新激活點的時候停止。在實際情況中，這樣的停止條件不合理。傳播過程是隨著時間逐漸變化的。因此，開始有將時間因素納入傳播過程中的研究開展。這類問題可被分為離散時間感知和連續時間感知。離散時間感知的研究工作[34-35]是將離散步驟作為時間度量，限制步驟長度。連續時間感知的研究工作[36-37]認為時間與傳播過程密切相關。基于位置的影響最大化問題：隨著基于位置的社交網絡的普及，一些研究者[38-39]開始研究基于位置的影響最大化問題。基本思想是最大化目標位置相關用戶的影響范圍。

4 結語

本文概述了影響最大化問題使用的公認傳播模型和幾種基本的算法。影響最大化問題具有很大的現實應用空間和某些方面的技術困難，成為研究熱點之一。同時由于這些現實應用，解決影響最大化問題（尤其是在大型網絡中）時，如何在合理的時間消耗甚至內存成本之間很好地平衡求解精度就成為需要考慮的。因為社交網絡中的網絡結構不是一成不變的，因而影響最大化解決方案的可擴展性、魯棒性是一個難點。隨著越來越多的研究者投入研究，相信這些問題都可以得到解決。