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

李 陽

(國家信息中心 北京 100045)

1 競爭影響力概述

1.1 研究背景

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

1.2 競爭影響力問題

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

2 競爭影響力傳播研究進(jìn)展

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

2.1 生物群體

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

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

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

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

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

2.2 疾病模型

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

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

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

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

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

2.3 信息模型

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

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

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

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

3 總結(jié)與展望

3.1 總 結(jié)

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

3.2 展 望

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

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

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

2) 競爭和互促的耦合.

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

3) 博弈論的應(yīng)用.

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