面向社交網絡中影響力傳播研究進展

李 陽

(國家信息中心 北京 100045)

1 影響力概述

影響力的研究最初從商業領域開始，隨著社交網絡應用的快速普及，影響力的研究也逐漸從應用場景向理論探索不斷深入.

1.1 研究背景

隨著社交網站及其相關應用的快速發展，人們越來越多地將活動轉移到社交網絡中，如在Twitter、Facebook和新浪微博上關注朋友和名人的最新動態.社交網絡也提供了一個合適的機會，可以進行快速的信息擴散.例如，許多公司在新浪微博、Twitter、Facebook等網站上投放他們的新產品、品牌廣告或者發布公共信息.公司開發了新產品，希望投放到市場，因此有限地選取一些高影響力用戶，通過這些用戶向他們的朋友以及朋友的朋友推薦該產品.公司希望通過這種口口相傳的方式最大化地影響社交網絡上的用戶，使得他們最終購買該產品.社交網絡的影響力傳播過程如圖1所示:

圖1 社交網絡的影響力傳播過程

1.2 影響力概念

影響力通常是指用一種別人所樂于接受的方式來改變他人思想和行動的能力[1].在社交網絡上，影響力泛指用戶的行為可以影響其朋友或者粉絲也作出類似的行為.基于微觀角度進行思考，從用戶的歷史數據或者靜態屬性展開分析，對用戶之間的影響力進行量化反映了用戶以多大概率或者多大程度來影響其朋友或者粉絲采取類似的行為.

1.3 影響力問題描述

面向影響力問題的研究主要聚焦在影響力最大化(influence maximization, IM)問題，具體可以描述為：給定如圖1所示的社交網絡圖(其中節點代表用戶，邊代表用戶之間的關系)，一個具體的傳播模型和節點集規模k，如何選定規模為k的節點集合P最大化地傳播影響力，即最終影響的總節點數σ(P)最大化.

2 影響力傳播研究進展

研究者們從拓撲結構著手影響力傳播研究，隨著研究的深入，發現貪心算法可以維持最優的影響力傳播范圍，成為研究者們改進和優化的焦點.后續為了進一步提升算法的可擴展性，一些啟發式算法被接連提出，并在相關實驗中得到驗證.

2.1 拓撲結構

早期的影響力傳播研究從拓撲結構展開，認為具有較好連通性的節點有助于信息傳播，因此研究者們認為在網絡中處于中心位置或具備某些拓撲性質(如節點的度、中心度等拓撲指標)的節點具有較高的影響力.然而，基于無標度網絡的生成特點，高拓撲的節點常常優先被鏈接，這樣就造成節點的影響力覆蓋范圍重復較大.

2.2 貪心算法

隨著社交網絡的興起，研究者們開始從信息傳播模型出發，在社交網絡中模擬信息傳播，根據傳播范圍來度量節點的影響力.Domingos等人[2-3]提出社交網絡中個人的網絡價值概念，并對影響力定義為：基于預知的信息傳播模型，從初始節點出發的信息能傳播到達的范圍.通常采用的信息傳播模型包括線性閾值(linear threshold, LT)模型[4]和獨立級聯(independent cascade, IC)模型[5]，其中節點狀態一般分為激活態和未激活態.在IC模型中，每個邊具有1個激活概率，激活節點獨立激活其處于未激活狀態的鄰居.在LT模型中，每個邊具有1個影響權重，每個節點隨機選擇(或預先計算)1個激活閾值，如果該節點的已激活鄰居節點的影響權重之和大于該節點的激活閾值，則認為該節點被激活.

基于上述2個模型，Kempe等人[6]系統地討論了求解影響力最大化問題的時間復雜度是NP-Hard的，但可以通過貪心算法在多項式時間內求得近似最優解.實驗表明貪心算法在不同模型上獲得的解集明顯優于基于拓撲結構的解集，主要缺點是時間復雜度過大，因此研究者們陸續提出一些基于貪心算法的優化方案.Leskovec等人[7]提出CELF方法，該方法利用影響力最大化問題目標函數的子模性，有效降低了模擬計算次數，但是其選擇范圍是整個網絡節點，導致其最差時間復雜度等于原始貪心算法.Goyal等人[8]在此基礎上進行優化并提出了CELF++算法，進一步減少了蒙特卡羅模擬次數，降低了時間復雜度.Chen等人[9]基于IC模型提出了NewGreedy策略，通過對網絡中所有邊進行預刪的方式，在每輪蒙特卡羅模擬中同時計算各候選節點的影響力收益，但這種方法相較CELF方法僅在第1輪計算中具有優勢.

隨后，社交網絡的拓撲結構被納入影響力傳播的研究中.Wang等人[10]和Cao等人[11]分別提出了CGA方法與OASNET方法，分別利用貪心算法和動態規劃方法按社區挑選種子節點，在對節點性能進行蒙特卡羅模擬時僅將影響力局限在該節點所屬社區，這樣做雖然能降低部分計算開銷，但是忽略了社區之間的邊損失以及全局性的影響力度量，造成影響力傳播范圍要弱于Chen等人[9]的NewGreedy策略.Borgs等人[12]提出一個影響力傳播估算方法，通過對社交網絡的拓撲結構隨機生成一個超圖，重復地在超圖中選擇最大度的節點，但是該方法缺乏場景數據的驗證.Cohen等人[13]提出一個改進的貪心算法SKIM，針對原始貪心算法的每輪迭代進行優化，有效降低了時間復雜度.Tang等人[14]提出一個2階段的影響力最大化算法，通過計算初始節點集最大化傳播范圍的最低邊界來進行參數估計和數值采樣，進一步降低了時間復雜度，甚至更優于CELF++算法.Wang等人[15]提出一個多路徑的異步閾值模型MAT，提出的IV-Greedy算法基于公開數據集在傳播范圍和運行時間方面取得了較優的性能.

2.3 啟發式算法

由于貪心算法的時間復雜度較大, 為了進一步提高算法的可擴展性，研究者們提出了一系列啟發式算法，如BentweenessCentrality[16]，k-shell[17]，PageRank[18]，LeaderRank[19]等，用于發現社交網絡中的高影響力節點.Chen等人[9]提出DegreeDiscount方法，該方法僅針對均勻IC模型且僅考慮節點對一階鄰居的影響力，在傳播概率較小時效果良好.Chen等人[20-21]提出了PMIA方法和LDAG方法，分別基于IC模型和LT模型在真實社交網絡中進行實驗分析，每輪通過探索局部結構來選擇新的種子節點.實驗表明這2種方法能獲得更好的解集，但影響力傳播范圍和計算開銷容易受拓撲結構影響[22].Kimura等人[23]提出基于最短路徑的SPM/SP1M方法，Narayanam等人[24]提出基于Shapley值的方法，雖然這2種方法能夠獲得較好的解，但可擴展性差.

隨著研究方法的不斷深入，一些可擴展性強的啟發式算法被陸續提出.Jiang等人[25]引入模擬退火算法來解決均勻IC模型上的影響力最大化問題.Goyal等人[26]提出一種針對LT模型的啟發式算法Simpath，基于節點的鄰接路徑來評估節點的影響力，并采用參數來控制影響力傳播和運行時間之間的平衡.Jung等人[27]基于影響力排名和影響力估計提出一個啟發式算法IRIE，通過對種子節點進行增量影響力預測，降低內存占用空間和運行時間.Zhou等人[28]提出UBLF算法，通過貪心算法構建一個上界函數來降低蒙特卡羅模擬次數，在公開數據上的實驗結果表明，當種子節點集較小時，可以較CELF方法獲得2～10倍的加速比.Galhotra等人[29]從鄰接路徑出發設計了一個可擴展的啟發式算法，與CELF++算法相比降低了內存占用空間.Galhotra等人[30]提出一個觀點累計交互模型(opinion-cum-interaction, OI)，并提出一個2階段的啟發式算法，通過進一步降低運行時間來進行影響力傳播.Cordasco等人[31-32]提出一個高效的啟發式算法，適用于在樹狀圖、環形圖和完全圖的拓撲結構中開展影響力計算，并擴展到有向圖網絡結構中[33].

基于上述工作，研究者們的視角也在不斷拓展，如積極探索心理、群體等對傳播機理的影響.Zhu等人[34]認為群體心理在影響力傳播中發揮著重要作用并提出D-SSA算法，該算法在加權社交網絡中可獲得近似最優解.Kermani等人[35]考慮節點之間的異質性提出可變的概率傳播，針對種子節點集的最小化和傳播范圍的最大化同時進行約束，提出魯棒的優化模型進行影響力計算.Wang等人[36]首次在多關系社交網絡中研究影響力最大化問題，認為群體對節點的影響要遠大于鄰居節點的影響.Chen等人[37]運用隨機選擇模型對節點之間的影響進行概率計算，采用基于馬爾科夫決策過程的增強學習對影響力最大化問題進行建模，與隨機規劃相比可以大幅降低時間復雜度.

3 總結與展望

3.1 總 結

目前研究者們針對影響力最大化問題進行了系統研究，分別立足拓撲結構、貪心算法、啟發式算法等形成了一系列的研究成果，在學術界深化了理論基礎，在產業界得到了應用實踐.但是當前研究還是存在一定的挑戰：一方面，當前的傳播模型基于經典的IC模型和LT模型進行擴展，不能深入反映用戶的興趣分布、交互行為等特性對影響力傳播的影響；另一方面，當前研究多聚焦于靜態社交網絡的拓撲結構，忽略了網絡的生長特性、動態變化等對影響力傳播的影響.

3.2 展 望

未來圍繞影響力的最大化傳播還存在繼續深入的研究點，如傳播模型的深度構建、大規模網絡計算和動態在線計算等.

1)傳播模型深度構建.

實際場景中的傳播模型機理是復雜的，未來傳播模型構建需要進一步的深度刻畫：一是研究者們加入主題因素[38-40]的影響進行探索，深化節點之間的主題語義、情感分析等內容屬性，運用自然語言、機器學習等技術分析主題因素對傳播影響的傾向變化；二是立足節點之間的交互行為、偏好傾向等行為屬性，運用統計分析技術探討行為屬性對傳播影響的微觀作用.

2)大規模網絡計算.

根據無標度網絡的生長特性，社交網絡的節點、鏈接日益增長，拓撲結構的規模日益增大.截至2022年1月，在全球覆蓋國家規模較大的社交網絡平臺中，Facebook達到約29.1億用戶、YouTube達到約25.62億用戶、WhatsApp達到約20億用戶、Twitter達到約4.36億用戶[41].迭代式的全網模擬計算已經無法滿足現實需求，需要更大規模的網絡計算：一是面向大規模社交網絡的拓撲結構，在有限節點預算的情況下繼續設計啟發式算法，進一步提升算法穩定性；二是立足傳播范圍評估問題設計分布式算法，面向影響力傳播展開并行計算，進一步降低時間復雜度，以不斷適應日益增長的規模需求.

3)動態在線計算.

目前的網絡結構研究主要圍繞靜態網絡展開，即節點固定以及節點之間的鏈接關系固定，但實際場景中的社交網絡是實時變化的[42-43].未來一方面圍繞動態網絡中的變化特性進行統計分析，增量式的在線計算將成為研究的重點；另一方面圍繞動態網絡中的節點生長與鏈接關系統計并分析其演化規律，為進一步的網絡拓撲預測提供支撐.