社交網(wǎng)絡(luò)中延遲競爭傳播的研究進展

李 陽

(國家信息中心 北京 100045)

1 時延競爭影響力概述

1.1 研究背景

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

1.2 時延競爭影響力問題

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

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

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

2.1 經(jīng)濟模型

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

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

2.2 疾病模型

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

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

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

2.3 信息模型

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

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

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

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

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

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

3 未來展望

3.1 總 結(jié)

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

3.2 展 望

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

1) 時延建模的刻畫.

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

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

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

3) 跨網(wǎng)跨域傳播的協(xié)同.

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