社交網絡中延遲競爭傳播的研究進展

李 陽

(國家信息中心 北京 100045)

1 時延競爭影響力概述

1.1 研究背景

現實世界中2種及2種以上實體(如產品或觀點)競爭傳播的情況普遍存在，社交網絡中二元甚至多元競爭研究在市場營銷、謠言抑制、病毒傳播等場景中得到了深化應用.例如，某公司發布了新款手機，一段時間后另一家公司也開發了新款手機參與市場競爭；謠言信息傳播一段時間后，辟謠機制展開競爭傳播以消除負向影響.這種競爭傳播過程往往是存在時滯的，稱為時延競爭.如何開展時延競爭下的影響力傳播研究，在社交網絡應用中具有重要的現實意義.

1.2 時延競爭影響力問題

以上研究即是時延競爭的影響力最大化問題.以二元正負信息競爭為例，給定社交網絡圖結構(其中用節點代表用戶，用邊代表用戶之間的關系)和競爭傳播模型，節點可以表示為正向激活態、負向激活態和未激活態.問題可以描述為：當負向信息傳播時間t(或已形成一定規模的負向節點集kN)，如何發現一個規模為kP的正向節點集(也稱為種子集)競爭傳播，將影響力最大化到社交網絡上的其他用戶，實現抑制負向影響力的效果.

2 時延競爭影響力研究進展

有關時延競爭影響力傳播的研究最初從經濟領域展開；隨著理論聚焦的逐漸深入，疾病模型、信息模型得到廣泛的研究，在理論建模和量化計算方面取得了一系列的研究成果.

2.1 經濟模型

時延競爭研究源于經濟學領域的斯塔克爾伯格領導模型[1-2]，出自1934年德國經濟學家斯塔克爾伯格的著作“Marktform und Gleichgewicht”.該模型主要描述的是商業市場中，主導企業(Leader)占據市場先發位置，跟隨企業(Follower)根據Leader對于己方決策的反應調整至最優決策以便最大化收益.這比較符合時延競爭傳播場景中，面對先行啟動的信息傳播，后序啟動的節點集如何選擇策略以符合己方最大化傳播.之后，Bharathi等人[3]提出一種適用于后序啟動節點集的近似算法以解決信息競爭傳播問題.Kostka等人[4]基于定位理論概念探討了確定性擴展模型，認為先行節點的發現算法是一個NP-Hard問題.Clark等人[5]采用馬爾可夫擴散模型對時序競爭問題進行研究，表明基于馬爾可夫擴散模型的目標函數具有子模特性.Hemmati等人[6]在一個雙層規劃模型上考慮時序競爭的2類節點，這需要采用確定性線性閾值擴散模型進行研究.Taninmis等人[7]提出采用雙層模型解決時序競爭問題.

經濟模型給時延競爭研究帶來了新穎參考，對于研究后序節點的競爭策略提供了應用視角和案例借鑒，也為研究方向的拓展提供了基礎.

2.2 疾病模型

一些研究者聚焦于病毒傳播機制的拓展研究，目前比較常用的是采用免疫策略控制疾病的傳播：Pastor-Satorras等人[8]基于無標度網絡特性分析了目標免疫策略；Cohen等人[9]依靠局部信息提出熟人免疫策略.部分研究者從節點免疫的角度出發進行研究：Kitsak等人[10]認為最有影響力的節點位于網絡的核心層，隨后提出了基于中心免疫的策略[11-12]；Zhang等人[13-14]研究如何選擇一個節點集，使得疾病傳播過程中網絡中被感染的節點最小化；Lü等人[15]對網絡拓撲中關鍵節點的識別進行梳理回顧，為節點免疫提供了思路.還有研究者采用輕量級的免疫方式，通過對網絡中的特定邊進行阻斷來有效降低節點之間的交互和傳播速度：Kimura等人[16-17]、Tong等人[18]和Kuhlman等人[19]研究面向邊級別的免疫策略對抗疾病傳播、計算機病毒的擴散以及謠言的傳播；Khalil等人[20]通過剪枝網絡結構來抑制惡意信息的傳播.

隨著網絡的動態變化，一些跟進的免疫策略也在不斷拓展.Gómez等人[21]采用微觀馬爾可夫鏈方法構建動力學方程，分析了疾病傳播過程中的關鍵特性.Wu等人[22]與Yang等人[23]基于傳播模型研究了動態免疫方法，但是他們的研究主要聚焦于優化動態系統的參數，而非對網絡結構中的最優節點進行免疫.

疾病模型在競爭傳播研究中得到廣泛應用，面向節點和面向邊的免疫策略被持續提出，相關實驗成果為時延競爭的趨勢分析提供了支撐，如何繼續下沉節點之間的交互成為難點所在.

2.3 信息模型

在競爭影響力最大化研究[24]中，自身影響力最大化的競爭傳播不一定導致對手影響力最小化.尤其在未給定先行種子節點策略的情況下，競爭影響力最大化問題不具備子模單調性，難以確定最優解的計算[25].

在最初的時延競爭最大化研究中，Carnes等人[26]基于獨立級聯(independent cascade, IC)模型進行擴展，分別提出距離模型和波傳播模型來刻畫2個產品在網絡中的競爭傳播.研究顯示對于Leader節點的最優選擇策略是具有高度數的節點，對于Follower節點的選擇策略證明屬于NP-Hard問題，但是這2個拓展模型均假設節點間距為1，限制了實際場景中的應用范圍.Bharathi等人[27]基于IC模型進行擴展提出了CP(competing processes)模型，在模型中引入積極影響和消極影響2個對立的傳播過程，但文獻提出的先行者最優的動態規劃方法僅適用于樹狀圖，給實踐應用帶來一定的局限性.

之后，研究者們逐漸加大了在實踐方面的探索，在數據場景中進行定量分析，取得了一系列的研究成果：Chen等人[28]根據真實網絡中信息擴散存在的時滯現象，提出面向競爭傳播的IC-M模型，該模型在IC模型的基礎上給每條邊(v,w)引入1個相遇概率m，該概率值決定了節點v與w相遇的頻度；Lin等人[29]考慮到種子節點選擇的多輪次場景需求，提出基于Q學習模型計算競爭方的最優策略，通過評估最終激活節點規模來篩選獲勝的競爭方；Bozorgi等人[30]基于競爭型線性閾值(linear threshold, LT)模型進行擴展，通過計算每個節點的影響力增益并基于社區劃分的方法選擇后序啟動節點集；Li等人[31]考慮到時間限制和時間延遲對信息傳播的影響，提出基于CELF策略的貪心算法降低蒙特卡洛的模擬次數，在真實數據集上的實驗顯示該算法優于常見的啟發式算法；Pham等人[32]在時間限制下提出基于輪詢的近似算法，實驗顯示該算法在競爭影響力問題上具有較好的可擴展性；Chen[33]等人基于競爭型轉移概率提出最低代價的影響力最大化算法，通過對每個節點設置一維向量來標記競爭選擇的概率，實驗顯示該算法具有極好的傳播范圍，同時也維持了合理的運行時間.

一些研究者從抑制對方影響力傳播的角度出發展開競爭傳播研究工作.加州大學的Budak等人[34]于 2011年首先基于IC模型進行擴展，研究如何選擇最優策略傳播權威信息來抑制已存在謠言的擴散問題.他們認為早期傳播范圍的模擬計算缺乏約束條件，將導致全網模擬并消耗大量的運行時間，并證明了抑制謠言傳播問題可以采用貪心算法獲得近似最優解.Nguyen等人[35]面向社交網絡研究錯誤信息的抑制傳播問題，即如何在時間t內找到1個初始節點集傳播正確信息，使得最終錯誤消息的傳播范圍小于給定比例.Wang等人[36]研究了動態阻斷算法，且分析了信息擴散階段的動態特征，但在實驗中仍采用了原始信息傳播模型.Rawale等人[37]在貪心算法的基礎上提出1種動態阻斷算法，并給每個節點分配1個可容忍的時間閾值，該算法可以在每個輪次對篩選的節點集進行增量式阻斷.Yan等人[38]認為在Follower節點先行啟動的情況下，選擇后序節點集需要考慮閾值限定下的最小代價問題.

還有一些研究者聚焦時間因素對競爭傳播的影響機理：Gomez-Rodriguez等人[39]認為以往工作較少考慮影響策略選擇的相關因素，研究時間因素在信息擴散中的作用，提出基于連續時間的影響力傳播模型，對時延競爭傳播模型研究提供了較好的借鑒；Ribeiro等人[40]主要研究競爭信息的延遲傳播問題，分析處于激活狀態的節點如何被競爭信息再次激活，并提出在此情況下影響力傳播計算不再具有子模特性和單調性；Yuan等人[41]提出部分反饋模型(partial-feedback model)，認為在時間間隔內持續選擇種子節點可以最小的節點規模實現最大化的影響力傳播；Wang等人[42]提出基于流體擴散的影響力傳播模型，通過運用流體動力學理論揭示擴散過程的時間演化.

針對基于信息模型的時延競爭，研究者們從微觀交互機理和宏觀趨勢分析2方面進行了理論探討和實驗測試，并結合時間因素對競爭傳播進行對比分析.隨著場景需求的不斷擴展，需要更多的啟發式方法來進行深入研究.

3 未來展望

3.1 總 結

社交網絡中的時延競爭在市場營銷、謠言抑制等領域具有現實需求，尤其在二元甚至多元信息的競爭傳播中，后序啟動的競爭傳播往往存在滯后性.研究者們從經濟模型、疾病模型、信息模型等角度展開時延競爭影響力傳播分析，在理論模型、方法驗證、場景應用等方面取得了一系列的研究成果.但是，當前研究還存在一定的挑戰：一方面當前研究多聚焦于根據先行者的策略來選擇后序節點集，這些都是確定性的信息源，很多場景中先行者的策略是未知的、不確定的；另一方面當前研究多聚焦于單一網絡的競爭傳播，但往往時滯的競爭傳播會跨網跨域傳播，涉及傳播模型的競爭機制更新等.

3.2 展 望

未來圍繞影響力的時延競爭傳播還存在繼續深入的研究點，如時延建模的刻畫、不確定信息源策略選擇、跨網跨域傳播的協同等.

1) 時延建模的刻畫.

目前的時延建模過程主要基于IC模型和LT模型的擴展應用.隨著研究的深入：一方面，當前研究聚焦于時序狀態下先行傳播的固化擴散，實際場景中信息傳播存在級聯的動態衰減，不是恒定不變的；另一方面，研究者們已經對考慮時延因素[43-44]的影響力傳播進行分析，下一步還需立足節點之間的拓撲距離、社區距離等拓撲變化，分析時間因素對傳播概率以及傳播模型的影響機理[45-46]，進一步提升面向實際場景的適應性.

2) 不確定信息源策略選擇.

目前主要圍繞先行者預知的傳播策略，研究后序節點如何開展競爭傳播.但實際場景中先行者的傳播策略大多是未知的.隨著研究的深入：一方面，在探索未知的先行者傳播源時，如何利用網絡局部拓撲的先驗知識進行學習，對于網絡關鍵節點的推斷至關重要；另一方面，如何提出自適應的后序競爭策略來提升競爭傳播的針對性和時效性，都需要進一步的場景化探索與驗證.

3) 跨網跨域傳播的協同.

目前的信息傳播過程主要圍繞單一網絡結構進行，但實際場景中的信息傳播是跨網跨域傳播[47-48].隨著研究的深入：一方面，跨網跨域的網絡結構可能是同質的，也可能是異質的，異質網絡結構對競爭傳播的影響機理還需要進一步量化計算；另一方面，跨網跨域的網絡結構也在不斷生長和演化，多重網絡演化對傳播機理、傳播模式、傳播規律等的影響問題需要進一步的統計和探索.