李 陽

(國家信息中心 北京 100045)

1 競爭影響力概述

1.1 研究背景

隨著社交網(wǎng)絡中應用場景的不斷擴展，信息傳播從最初的單一傳播向發(fā)布、轉發(fā)、評論以及輿論場演變，市場營銷從如何挖掘有限的種子用戶來最大化商品促銷轉變?yōu)椴煌碳抑g產(chǎn)品的競爭營銷，此外還有候選人在競選中的競爭宣傳、惡意信息的散布與辟謠等.這些信息在傳播過程中相互作用，形成了二元甚至多元信息的競爭傳播.信息的競爭傳播機制與演化規(guī)律探索成為重要的研究課題.

1.2 競爭影響力問題

上述研究即是競爭影響力[1]最大化的常見應用，目前主要分為2類[2]：一類是促進己方影響力最大化傳播，另一類是抑制對手影響力最小化傳播.當未給定初始種子節(jié)點策略時，競爭影響力最大化問題不具備子模單調(diào)性，難以確定最優(yōu)解的計算[3].以二元正負信息競爭為例，給定社交網(wǎng)絡圖結構(其中用節(jié)點代表用戶，用邊代表用戶之間的關系)和競爭傳播模型，節(jié)點可以表示為正向激活態(tài)、負向激活態(tài)和未激活態(tài).當初始節(jié)點傳播某負向信息時，競爭影響力最大化問題描述為：如何發(fā)現(xiàn)規(guī)模為k的節(jié)點集P(也稱為種子集)競爭傳播正向信息，以最大化傳播正向影響力到社交網(wǎng)絡上的其他用戶，實現(xiàn)最大化影響力競爭傳播.

2 競爭影響力傳播研究進展

競爭影響力傳播研究源于生物群體的種群發(fā)展；隨著研究的深入，疾病模型成為研究的重點；信息模型可以量化計算后，信息模型逐漸成為微觀刻畫和全網(wǎng)評估競爭影響力傳播的熱點問題.

2.1 生物群體

自然環(huán)境的種群發(fā)展與人類社會的信息傳播有相似之處.種群動力學作為分析生物群體與環(huán)境之間關系的重要工具，可以用來量化生態(tài)系統(tǒng)中種群之間以及種群與環(huán)境之間的交互關系.王云馳[4]對生態(tài)系統(tǒng)的反應擴散模型進行了系統(tǒng)梳理和全面總結，認為社交網(wǎng)絡可以比作種群的生態(tài)系統(tǒng)，節(jié)點之間的信息交互可以比作種群之間的競爭，并在數(shù)據(jù)集上進行了分析和論證.本文從該研究中獲得了啟發(fā).

18世紀末，英國人口學家Malthus[5]提出了人口增長指數(shù)預報模型，在理想情況下對人口規(guī)模按照指數(shù)增長進行預測，但是未考慮有限的實際條件.比利時數(shù)學家Verhulst[6]提出了阻滯增長的Logistic模型，描述了種群規(guī)模從起始緩慢增長、中間快速增長、到后期資源受限的增長過程.Geroski等人[7]通過信息傳播實驗驗證了該模型的合理性.但Logistic模型是基于單物種的增長過程，不適用于雙物種以及多物種競爭的生態(tài)環(huán)境.Anthony[8]則認為該模型沒有考慮網(wǎng)絡節(jié)點距離對反應擴散過程的影響.

烏克蘭科學家Lotka[9]和意大利科學家Volterra[10]分析了食物鏈的種群之間多物種相互捕食關系，基于Logistic模型增加了競爭系數(shù)并提出了Lotka-Volterra模型，對生態(tài)系統(tǒng)中種群之間的動態(tài)競爭進行動力學分析.Zhu等人[11]和Jiang等人[12]分別在隨機環(huán)境下探討了Lotka-Volterra模型的競爭研究.Kloppers等人[13]、鐘琪等人[14]、Zhang等人[15]基于Lotka-Volterra模型在社會危機和微博輿論中通過建模來分析競爭過程.對于雙種群，劉詠梅等人[16]、蘭月新等人[17]、姜景等人[18]針對謠言和辟謠的競爭機制進行研究，較好地刻畫了這種對立的競爭關系.

Fisher[19]綜合考慮了種群增長在連續(xù)時間、連續(xù)狀態(tài)情形下的動力學影響，在Logistic模型的基礎上擴展了反應擴散過程，提出了Fisher模型.Wang等人[20]在Fisher模型的基礎上提出了2階段的Diffusive Logistic模型，將信息源劃分成一系列子網(wǎng)，將信息傳播過程比作子網(wǎng)內(nèi)部的增長過程與子網(wǎng)之間的擴散過程，對競爭過程展開模擬探討.

綜上，通過將社交網(wǎng)絡的信息競爭過程比作生態(tài)系統(tǒng)的種群增長過程[4]，為社交網(wǎng)絡中的競爭影響力傳播研究提供了一個新穎的視角.雖然如此，上述模型都是建立在平均場理論的假設之上.實際生態(tài)環(huán)境的種群發(fā)展過程中，不同生物、不同種群之間的影響以及種群與環(huán)境之間的影響都可能各不相同，因此種群模型在實際環(huán)境中的應用還存在一定的局限，一些改進與應用還在繼續(xù)探討中.

2.2 疾病模型

疾病在人群中的傳播過程與信息在社交網(wǎng)絡中的傳播過程存在相似之處，因此學術界也開始探索運用疾病模型對信息傳播過程進行建模，研究競爭傳播機理.

疾病傳播研究最早從18世紀60年代對天花傳播研究開始.20世紀20年代倫敦黑死病以及孟買瘟疫爆發(fā)后，研究者們提出了SIR模型[21]以及考慮重復感染的SIS模型[22].最初的疾病模型把節(jié)點分為3種狀態(tài)：易感態(tài)(susceptible,S)，節(jié)點可以一定概率被感染；免疫態(tài)(recovered,R)，節(jié)點被治愈后獲得免疫力；感染態(tài)(infected,I)，節(jié)點可以一定概率轉成免疫態(tài).

研究者們基于疾病模型提出了一系列的改進方法.Ahn等人[23]基于SIS模型提出了一種不對稱耦合的疾病模型.Kitsak等人[24]認為最有效的傳播者是位于網(wǎng)絡核心位置的節(jié)點，并且基于SIS模型展開了相關的實驗分析.Karrer和Newman[25]采用滲流理論對2種病毒傳播過程進行分析，發(fā)現(xiàn)在較大網(wǎng)絡范圍內(nèi)感染性強的病毒能夠存活下來，即“贏家通吃”.Prakash等人[26]認為一個節(jié)點在面臨2種病毒競爭時只能被一種較強的病毒感染，也即“贏家通吃”.Beutel等人[27]基于SIS模型進行改進，提出了一種部分交叉免疫的病毒競爭模型，且采用平均場的方法對2種病毒共存?zhèn)鞑サ母偁庨撝颠M行了分析.但是該模型采用的是完全連接圖，實際網(wǎng)絡大多是無標度網(wǎng)絡，在實際場景中的作用有限.Tsai等人[28]基于博弈論的方法分析了傳染病控制問題，提出一種啟發(fā)式方法來解決抑制影響力最小化問題.

還有研究者將疾病模型應用到謠言的傳播與抑制場景中并取得了一系列的進展.Singh等人[29]討論了如何使用合適的機制來抑制謠言的傳播，發(fā)現(xiàn)網(wǎng)絡的平均度數(shù)越小，采用隨機或者目標免疫的效果越好.Zhang等人[30]在SIR模型的基礎上提出了謠言傳播模型，認為存在2種謠言傳播態(tài).Xia等人[31]基于SIR模型提出了SEIR模型，發(fā)現(xiàn)謠言信息的吸引力不能影響社交網(wǎng)絡中的傳播閾值.在競爭傳播過程中，Liu等人[32]基于SIR模型增加了節(jié)點猶豫態(tài)，并提出SHIR模型研究二元信息的競爭關系，認為轉移概率大的信息將占絕對優(yōu)勢.Xiao等人[33]提出了SKIR模型，其中K狀態(tài)表示該節(jié)點傳播辟謠信息，可以用來描述社交網(wǎng)絡謠言與辟謠的并行傳播過程.

綜上，研究者們借助經(jīng)典的疾病模型對信息的競爭傳播、尤其是謠言的擴散與抑制進行了理論分析和實驗探討，形成了一系列有益的嘗試和研究成果.但是，基于疾病模型以及擴展模型的競爭傳播研究主要還是從趨勢層面進行宏觀刻畫，在現(xiàn)實世界中的二元乃至多元信息競爭機理的細粒度計算上比較受限.

2.3 信息模型

隨著信息模型理論與應用的拓展，研究者們開始在競爭傳播中進行探索.Bharathi等人[34]最先提出競爭條件下的影響力最大化問題，隨后研究者們在獨立級聯(lián)(independent cascade,IC)模型和線性閾值(linear threshold,LT)模型中進行拓展.Borodin等人[35]聚焦多競爭者的影響力問題，基于LT模型提出一種OR模型(original model)，研究節(jié)點在競爭情況下如何決策選擇其中一方的影響力，并證明了該問題屬于NP-Hard問題，可以用貪心算法獲得近似最優(yōu)解.Chen等人[36]考慮到商品本身的質(zhì)量問題會產(chǎn)生消極影響，提出IC-N模型研究如何競爭傳播：當節(jié)點受到鄰居節(jié)點的激活影響時，以概率q轉入積極狀態(tài)，以概率1-q轉入消極狀態(tài)；當網(wǎng)絡圖是樹結構時，采用動態(tài)規(guī)劃的方法給出了近似最優(yōu)解.還有研究者從抑制負向影響力最小化出發(fā)實現(xiàn)競爭傳播的目標.He等人[37]考慮到LT模型下的企業(yè)產(chǎn)品競爭因素，通過讓己方企業(yè)選擇合適的初始節(jié)點集使其最大化傳播，進而抑制對手企業(yè)使其最小化傳播，該問題也被稱為影響阻塞最大化(influence blocking maximization,IBM)問題.He等人認為負面信息容易被人們所接受，因而在傳播階段謠言信息比其他信息獲得更高優(yōu)先級，為了提升可擴展性提出了CLDAG算法，使得運行時間提升了2個數(shù)量級.Bozorgi等人[38]和Liu等人[39]利用社區(qū)劃分算法劃分網(wǎng)絡，計算每個節(jié)點在所屬社區(qū)中的影響力，并提出基于LT模型擴展的抑制擴散模型(diffusion containment model,DCM).Zhu等人[40]通過分析競爭環(huán)境中初始節(jié)點集的規(guī)模選擇問題，研究如何抑制競爭信息的影響力傳播.

為了獲得競爭影響力的量化計算和近似最優(yōu)解，研究者們從貪心算法入手開展競爭影響力傳播研究，形成了一系列的改進和優(yōu)化成果.Nguyen 等人[41]證明使用貪心算法可以得到近似最優(yōu)解.Khalil等人[42]基于預刪邊的方式提出一個貪心算法解決影響力最小化傳播，其目標函數(shù)在LT模型下具有超模特性，可以獲得一個近似最優(yōu)解.Li等人[43]認為社交網(wǎng)絡中的節(jié)點關系可以劃分為正向關系和負向關系，提出了極性相關的影響力最大化問題，并采用貪心算法獲得近似最優(yōu)解.Lin等人[44]提出了面向偏好信息的競爭傳播問題，通過采用概率參數(shù)估計和節(jié)點選擇的2階段貪心算法而具有子模性和單調(diào)性，與距離模型、波傳播模型等相比，在傳播范圍和計算時間之間取得了較好的平衡.Kimura等人[45]通過采用貪心算法來預刪邊的方式解決影響力最小化問題，但不能保證近似最優(yōu)解.Ju等人[46]采用IC-N模型進行研究，通過引入一個質(zhì)量因子q來轉換負向影響力和正向影響力對擴散的影響，進一步優(yōu)化提升傳播范圍.Ni等人[47]從社區(qū)角度來篩選種子節(jié)點并提出貪心算法，通過抑制負向節(jié)點的傳播實現(xiàn)正向影響力的最大化，但是在子社區(qū)內(nèi)展開的貪心算法計算評估限制了可擴展性的提升.Tong等人[48]針對競爭環(huán)境下的影響力最大化問題，通過采用主題建模、社區(qū)劃分等方法來計算節(jié)點的影響概率.

為了更好地提升算法的可擴展性，一些研究者從啟發(fā)式算法入手，進一步降低競爭傳播的計算時間.Tong等人[49]提出通過預刪邊的方式解決最小化影響力問題，采用鄰接矩陣的特征值來確定感染閾值.Ding等人[50]通過對IC模型進行擴展來研究競爭傳播問題，根據(jù)影響力增益自適應地篩選種子節(jié)點集，但是正向優(yōu)先的激活方式限制了應用的實用性.Zhu等人[51]提出使用最低代價的種子集選擇問題來研究競爭影響力問題.Luo等人[52]通過同時考慮用戶觀點以及競爭者策略，提出迭代推斷的啟發(fā)式算法來抑制負向觀點傳播，在競爭影響力的同時也降低了運行時間.Cheng等人[53]針對傳染病爆發(fā)的免疫問題進行了研究，論證了疾病免疫最小化問題和正向影響力最大化問題的轉換，并通過實驗驗證了有效性，在可擴展性上也取得較好的平衡.

社交網(wǎng)絡規(guī)模日益增大，研究視角更加細化和下沉[54-55].部分研究者圍繞競爭傳播模型的約束條件、傳播路徑、圖結構等基礎理論[56-60]不斷深化，從深度學習[61-64]的角度出發(fā)，通過對局部網(wǎng)絡特性的學習來預測推斷全網(wǎng)傳播[65-66]，這樣就避開了局部信息有限的情況下無法開展全網(wǎng)評估計算的現(xiàn)實挑戰(zhàn).與早期的生物群體、疾病模型相比，基于信息模型的競爭研究深化了微觀機制的刻畫、競爭機制的構建以及宏觀量化的統(tǒng)計，但是實際場景的需求也趨于更加復雜和多變，不斷對理論驗證和場景實證進行迭代成為研究的熱點和優(yōu)化方向.

3 總結與展望

3.1 總 結

社交網(wǎng)絡在信息傳播、政務發(fā)布、市場營銷等方面發(fā)揮著重要的作用.從一元信息的最大化傳播到二元信息、多元信息的競爭傳播，結合復雜網(wǎng)絡、社會計算、心理學等多學科理論，研究者們利用生物群體、疾病模型、信息模型對競爭影響力傳播的傳播表象、傳播機理、傳播規(guī)律進行剖析，取得了一系列的研究成果.但是，當前研究還存在一定的挑戰(zhàn)：一方面，研究多聚焦于單方競爭影響力的最大化，多方競爭的整體影響力最大化面臨越來越多的場景需求；另一方面，研究多聚焦于雙方競爭對抗的影響力量化計算，但從競爭傳播的作用機制來看更是一個雙方博弈的過程.

3.2 展 望

未來圍繞影響力的競爭傳播還存在繼續(xù)深入的研究點，如多元建模的深度刻畫、競爭與互促的耦合、博弈論的應用等.

1) 多元建模的深度刻畫.

在目前的信息模型構建過程中，主要圍繞經(jīng)典的IC模型和LT模型進行優(yōu)化.由于模型帶有先天的假設，與實際場景存在距離，需要融入更多場景需求來解決實際問題：一是隨著多元競爭的應用越來越廣泛，二元競爭環(huán)境中影響力傳播問題的子模性和單調(diào)性可能不再適用；二是展開多關系[67]對影響力研究的探討，對節(jié)點間的鏈接關系進行分類梳理，細化其對競爭模型的影響機理.

2) 競爭和互促的耦合.

當前競爭影響力傳播研究主要圍繞促使一方影響力最大化或者抑制一方影響力最小化展開，即圍繞純粹的競爭關系展開.隨著研究場景的擴展與應用，互促關系越來越受到重視：一是對競爭環(huán)境的互促機理[68]進行深化研究，尤其是對互促關系對競爭傳播的影響機理進行量化評估；二是在有限的預算條件[69-70]下，面向競爭主體的互促影響力最大化問題的建模論證成為深入研究的重點.

3) 博弈論的應用.

在目前的競爭傳播過程中，主要聚焦于一方影響力最大化或者最小化傳播的研究，但在實際場景中，不一定是單方的競爭勝出.影響力傳播與抑制的本質(zhì)是傳播方與抑制方在系統(tǒng)層面的博弈[71-73]：一方面，在信息模型構建過程中，信息的傳播過程常常以概率或者累計影響力進行計算，隨著競爭傳播中博弈現(xiàn)象的研究，博弈行為及環(huán)境反饋被納入節(jié)點的交互過程，需要對競爭傳播模型進行優(yōu)化[74-75]；另一方面，從演化博弈[76-79]的角度提出可擴展性的近似算法[80-81]，對于競爭博弈的平衡以及成本控制具有現(xiàn)實意義.