社交網絡中考慮節點度的演化博弈

劉亞州,王 靜,潘曉中,付 偉

(1.武警工程大學 電子技術系,西安 710086; 2.西安高科技研究所 計算機科學與技術系,西安 710086)(*通信作者電子郵箱qqzjlyz@163.com)

0 引言

謠言可以定義為一種缺乏事實根據,或未經證實,公眾一時難以辨別真偽的閑話、傳聞或輿論，它會引起社會對突發事件的恐慌心理并導致潛在的損失。人散播謠言以達到誹謗他人、制造聲勢、轉移注意力、造成恐慌等目的。近年來,互聯網的廣泛使用,無形中加速了謠言傳播[1]。例如,由于2011年日本發生了核泄漏事件,在中國出現了有關碘鹽可以幫助人免受核輻射的謠言,導致碘鹽價格高出正常價格的十倍,擾亂了正常的社會經濟秩序[2]。因此,有必要對謠言傳播過程進行研究,分析影響謠言傳播的因素,并提出控制謠言傳播的措施。

在過去的幾十年里,復雜網絡[3]中的謠言擴散模型被廣泛研究。1998年,Watts和Strogatz[4]研究了網絡的聚類性質,提出了WS小世界網絡模型,為分析社交網絡的小世界特性提供了理論依據；1999年9月,Barabési和Albert[6]通過研究發現萬維網的出度和入度分布與正態分布有很大不同,而是服從冪律分布,提出了BA無標度模型。隨著研究的逐步深入,研究者發現社交網絡中的謠言傳播過程與生物病毒網絡中的病毒擴散機制十分相似,因此人們提出SI(Susceptible-Infected)、SIR(Susceptible-Infective-Removal)等病毒網絡的傳染病模型來研究謠言傳播過程[7]。

近年來,研究者從多個角度對謠言傳播進行了研究,如從眾效應[8]對謠言傳播的影響、好奇心理[9]對謠言選擇的作用、猶豫機制[10]下的謠言傳播模型等。以上關于謠言傳播的研究并沒有考慮節點度對傳播率的影響,認為任何一個感染節點無論度大小都具有相同的傳播能力,然而在實際網絡中度越大的節點,往往也是網絡中越重要的節點,一般是較早加入網絡的,對謠言的辨識能力也越強,當這類節點接觸到謠言時,由于其具有更強的謠言辨識能力,因此它接受謠言并傳播謠言的概率也就會相應降低。也就是說度大的節點由于具有較強的謠言辨識能力,使得最終被謠言傳染的概率低于甚至遠低于網絡中謠言的平均傳播率。針對以上分析,本文引入η來表示度為k的節點對謠言的辨識能力,節點度越大其對謠言的辨識能力相應越大,對謠言的識別性就越強,受謠言蠱惑而成為傳播者的概率就越小。

通過以往的研究還發現社交網絡中的節點都是現實生活中的個體或者團體,由于個體的教育背景、生活環境、經歷等存在差異,使得與其聯系的個體數目也存在差異,面對謠言時,不同個體的策略對網絡中其他個體所采取策略的影響不同。此外,謠言中所包含的信息往往與個體自身利益相關,如網絡知名度、關注度等虛擬利益,甚至有些謠言與個體經濟利益密切相關,網絡中節點對謠言態度的選擇體現了自身利益的訴求,其實質是在利益機制驅動下,采取相應策略實現自身利益最大化,有趣的是這種情況和博弈論[11]中的“囚徒困境”[12]模型類似,在謠言傳播過程中引入博弈論能夠很好地描述這一情況,并取得了豐富的研究成果。然而以往的研究并沒有考慮節點的鄰居節點的度對節點博弈收益的影響,節點的鄰居節點的度的大小體現了鄰居節點在網絡中的重要程度,鄰居節點重要程度不同對節點最終博弈收益影響不同。

本文在已有研究的基礎上,考慮到謠言傳播過程中度不同的節點具有的辨識能力不同,對其他節點的影響因度不同而存在差異,分析了節點辨識能力對謠言傳播的影響,結合節點度定義了一種新的博弈收益,基于博弈論提出一種動態網絡演化模型,利用平均場理論,研究該模型在WS小世界網絡與BA無標度網絡上的傳播動力學行為。隨后利用兩種經典的網絡通過數值仿真的方式研究了謠言在本文所提網絡模型上的傳播特性,提出兩種抑制謠言傳播的策略并比較抑制效果。最后在Facebook真實網絡數據中驗證了仿真結果的正確性。

1 博弈網絡演化模型

借助于節點個數為N的WS小世界網絡與BA無標度網絡來模擬現實中的人際關系網絡,網絡中的節點代表現實中的個體,網絡中節點之間的邊代表個體間的聯系。利用SIR病毒傳播規則,N個節點可能處于三種不同的狀態:健康態S,表示節點從未聽到過謠言但聽到后有可能傳播謠言;感染態I,表示節點聽到謠言并選擇傳播謠言;免疫態R,表示節點聽到謠言但不傳播謠言。謠言傳播過程為:在時間t內,一個感染節點以概率λ將謠言傳播到鄰居易感染節點;由于易感染節點對謠言具有辨識能力,當其接觸謠言時,以概率η轉變為免疫節點;當感染節點接觸到免疫節點時,前者以概率γ轉變為免疫節點。

考慮到實際中不同個體面對同一謠言時,對謠言的辨識能力不同,進而影響個體對謠言所采取的態度。個體的辨識能力與個體的知識水平、人際關系以及謠言的模糊程度等有關,本文利用節點度k來表示個體的知識水平及人際關系,用σ來表示謠言的模糊程度,用η來表示節點對謠言的辨識能力,則度為k的節點辨識能力可用式(1)表示:

η=(1-exp(-kt))exp(-σ)

(1)

實際中個體的知識水平越高、人際關系越豐富個體對謠言的辨識能力通常也越強。在本文中表現為節點度k越大其辨識能力η越強;實際中謠言模糊程度越大,個體對謠言的辨識能力越弱,在本文中表現為謠言模糊程度σ越大其辨識能力η越小。

通常情況下,兩個相連的節點對彼此的影響程度不同,用Wij表示節點i對節點j的影響程度:

Wij=ki/kj

度為k的節點i其鄰居節點中第j個鄰居節點的度用k(j)表示,則k個鄰居節點對節點i的總影響程度為:

k個鄰居節點中感染節點的集合為Ni,用n(i)表示Ni中元素的個數,k個鄰居節點中免疫節點集合為Nr,用n(r)表示Nr中元素的個數,則感染節點對節點i的總影響程度T1可用式(2)表示:

(2)

免疫節點對節點i的總影響程度T2可用式(3)表示:

(3)

當健康節點接觸到謠言時,由于謠言的模糊性以及節點自身的辨識能力限制,節點對謠言態度不確定性的概率為1-η,節點往往依據鄰居節點對謠言的態度作出選擇以降低風險。當鄰居節點中免疫節點對節點的總影響程度大于感染節點對節點的總影響程度,即T1

(4)

謠言中包括的信息往往與節點自身的利益相關,節點對謠言的態度的選擇會改變其收益,如關注度變化、信譽度改變、經濟利益等。由于謠言信息的不確定性,傳播謠言與不傳播謠言都可能增加節點的收益,可見,節點對謠言態度的選擇是一個不完全信息的博弈過程。在經典的博弈理論中,博弈雙方是完全理性的,對博弈收益是完全了解的,因此雙方最終選擇納什均衡策略。但在實際復雜環境中個體往往沒有選擇納什均衡[13]策略,個體通過掌握的部分信息采取使自己利益最大化的策略,即實際中的個體并非完全理性。個體與每一個與其相聯系的個體之間都存在一個雙人博弈[14],個體的最終博弈收益為眾多雙人博弈收益的總和。同時,本模型考慮鄰居節點的度對節點最終博弈收益的影響,分別用A、B表示進行博弈的兩個節點,1表示節點選擇處于免疫狀態,2表示節點處于感染狀態,Bxy表示節點A、B分別處于狀態x、y時節點A的博弈收益,其中x,y∈(1,2),則收益矩陣如圖1所示。

圖1 節點博弈收益矩陣

用P1表示度為k的節點選擇處于免疫狀態時的博弈總收益,用P2表示度為k的節點選擇處于感染狀態時的博弈總收益,分別用式(5)、式(6)表示:

(5)

(6)

節點根據博弈總收益決定對謠言的態度：當P1≥P2時,不相信謠言對個體更有利,節點選擇不相信謠言;當P1

(7)

當感染節點接觸到免疫節點時,由于對謠言信息進一步確認,感染節點可能以一定概率改變策略轉變為免疫節點,這種轉變除了與節點辨識能力有關,還與博弈收益相關,轉變概率γ可以用式(8)表示:

γ=η×exp(-P2/P1)

(8)

綜合以上分析,當健康節點接觸感染節點時,考慮從眾效應,結合節點度不同對博弈收益的影響,健康節點轉變為感染節點的概率λ可以用式(9)表示:

λ=(1-η)×μ×γ

(9)

整個演化過程如圖2所示。

圖2 謠言傳播動態網絡的演化過程

由上述演化模型可知,在博弈收益中考慮節點度的因素時,改變了節點的博弈總收益,降低了健康節點轉變為感染節點的概率,很大程度上改變了謠言在社交網絡中的傳播機制。

謠言一旦大范圍流傳,國家安全和社會穩定就會受到影響,因此,有必要采取有效的措施來抑制謠言傳播[15]。當謠言出現時,有可能不會立即遭到抑制,謠言遭到抑制的時機與謠言的性質、內容以及波及范圍有關,本文用謠言抑制系數α來表示謠言遭到抑制的時機,用α0∈[0,1]為謠言抑制臨界值:

其中:ni(t)為t時刻感染節點總個數;N為網絡中節點總個數;k(j)為節點j的度。當α>α0時,謠言會被采取抑制策略。由于在實際人際關系網絡中個體數目眾多,因此,往往選擇一定比例個體進行謠言抑制,經過抑制后的個體選擇不相信謠言。本文采取兩種策略來抑制謠言擴散:

策略1 將網絡中節點按危害程度θ(θ∈[0,1])由大到小進行排列,按θ由大到小選擇α×N(0<α≤1)個節點進行謠言抑制,經過抑制后的個體選擇不相信謠言,θ可表示為:

策略2 隨機選擇α×N(0<α≤1)個節點,降低節點選擇傳播謠言的博弈收益。

在實際中,由于出現謠言傳播的社交網絡規模龐大,因此有針對性選擇一部分人進行謠言抑制符合實際;而謠言傳播與個體利益息息相關,因此利用博弈收益來抑制謠言傳播能改變個體對預期收益的期望,使個體認為不相信謠言會帶來更高的收益,從而達到抑制謠言傳播的目的。

2 演化博弈模型理論分析

下面借助于平均場理論[16-18]分別研究本文所提動態復雜網絡演化模型在均勻網絡和無標度網絡上的傳播特性,以此來分析在博弈模型中考慮節點度的情況下謠言傳播的變化情況。

2.1 本文模型在小世界網絡上的傳播行為

為了分析所提博弈模型在小世界網絡上的傳播特性,本文定義小世界網絡中每一個節點的度k都等于〈k〉,S(t)、I(t)、R(t)分別為t時刻健康節點、感染節點、免疫節點的節點密度,并且滿足:

S(t)+I(t)+R(t)=1

結合模型演化過程,可得謠言傳播的均勻場方程為:

當t=0時,即謠言剛進入到網絡中時,感染節點和免疫節點個數基本為0即:

S(0)≈1

謠言傳播最終達到穩定狀態時,所有的感染節點全部轉變為免疫節點,即I(∞)為0。

2.2 本文模型在無標度網絡上的傳播行為

實際大多數網絡(如WWW、Internet和DNA)中節點度的大小具有較大的差異性,即節點度分布具有冪律特性。BA無標度網絡[6]中節點度分布具有冪律特性,在這一部分,本文采用均勻場理論,利用BA無標度網絡對該演化博弈模型傳播動力學進行研究。t時刻度為k的節點中健康節點、感染節點、免疫節點的相對密度分別為:S(k,t)、I(k,t)、R(k,t),且有:

S(k,t)+I(k,t)+R(k,t)=1

結合模型演化過程,可以得到謠言傳播的均勻場方程:

(10)

(11)

(12)

(13)

圖3 謠言在三種網絡中的傳播特性

S(k,t)=exp(-kQ(t))

(14)

1-〈〈S(j,t)〉〉-

謠言傳播最終達到穩定狀態時,所有的感染節點全部轉變為免疫節點,即I(k,∞)為0,此時有:

無標度網絡中謠言傳播最終范圍可以表示為:

(15)

將式(14)代入式(15)可得謠言傳播最終范圍,謠言模糊σ和博弈收益通過影響S(k,∞),最終影響謠言傳播最終范圍。

3 仿真結果與分析

為了研究謠言在本文所提動態網絡上的傳播動力學行為,本文采用WS小世界和BA無標度兩種網絡數據集以及Facebook真實網絡數據,運用數值仿真方法研究其傳播特性。仿真過程中選取的參數如下:兩類網絡中節點總數N=2 000,謠言在網絡中傳播的初始時刻,隨機選擇0.5%的節點作為初始感染節點;在WS小世界網絡中隨機化加邊概率p=0.2,平均節點度〈k〉=5;在BA無標度網絡中,網絡的初始節點m0=6,每次引入新節點時新生成的邊數m=5。Facebook數據集[20]的基本特征為:節點總數N=4 039,邊數為88 234,節點度〈k〉=43.69,平均聚類系數為0.605 5,網絡直徑為8。其中:P(S)、P(I)、P(R)分別為網絡中健康節點、感染節點、免疫節點與總節點個數的比值。所有仿真結果至少為60次獨立運行的平均。

在對網絡中謠言傳播特性進行仿真的過程中,節點的博弈收益B11=15,B12=10,B21=5,B22=6,謠言的模糊程度σ=4。對比圖3(a)、(b)可發現,在考慮了節點度對博弈收益的影響后,相對于WS小世界網絡,謠言在BA無標度網絡中傳播速度更快,傳播范圍更廣,達到穩定狀態所需時間更短,在本文所提動態網絡模型中,謠言更容易在BA無標度網絡中傳播。這主要是由于WS小世界網絡中節點度具有均勻性,使節點選擇傳播謠言與不傳播謠言的博弈收益相差不大,給謠言進一步擴散增加了難度;BA無標度網絡中節點度分布具有冪律特性,大部分節點度較小,對謠言的辨識能力較低,更容易受謠言蠱惑而選擇傳播謠言,最終使謠言在BA無標度網絡中傳播速度更快,傳播范圍更廣。從圖3(c)可以看出,Facebook網絡中謠言傳播特性能夠很好吻合圖3(a)、(b)中謠言傳播特性,從而驗證了模型的正確性。

圖4 σ取值變化時P(I)隨t的變化情況

圖5 節點博弈收益不同時P(R)隨t的變化情況

圖6 在WS網絡上進行謠言抑制

圖4給出了節點的博弈收益相同的情況下,謠言模糊程度取值變化時,三種網絡中P(I)隨t的變化情況。結果表明,隨著謠言模糊程度增大,謠言在網絡中傳播范圍變大,通過圖4(c)驗證了這一結果,這主要由于謠言模糊程度變大時,節點對謠言的辨識能力降低,使節點更容易選擇相信并傳播謠言。由圖4(a)可以看出,在WS小世界網絡中謠言模糊程度增大時,謠言傳播速率會增大,達到穩定狀態所需時間變小。對比圖4(a)、(b)可發現,謠言模糊程度對BA無標度網絡中謠言傳播速率及達到穩定狀態所需時間影響較小。

圖5為謠言模糊程度相同時,不同的博弈收益下兩種網絡中P(R)隨t的變化情況。從圖5可看出,增大節點免疫收益時,兩種網絡中更多節點選擇不相信謠言。對比圖5(a)、(b),可發現免疫收益增加值相同時,與無標度網絡相比,小世界網絡中免疫節點的增長幅度更大,這主要因為在小世界網絡中,節點度具有均勻性,每個節點對謠言的辨識能力相差不大,增加節點免疫收益時,節點選擇傳播謠言與不傳播謠言的博弈收益更容易出現不平衡,節點在利益機制驅動下,傾向于選擇不相信謠言。圖5(c)驗證了免疫收益增加時網絡中更多的節點選擇不相信謠言。

由于謠言在網絡上大肆傳播具有很大的危害性,因此當謠言發生時,采取一定措施對謠言傳播進行抑制很有必要,但由于網絡中節點眾多,不能做到對每一個節點都進行謠言抑制,因此本文選擇α×N個節點進行謠言抑制,其中α=0.3為謠言抑制系數,N為網絡中節點總數,本文利用達到穩定狀態時健康節點占總節點個數的比例即P(S)的大小來衡量最終的抑制效果。

圖6為在WS網絡中采取本文所提兩種謠言抑制策略的仿真結果圖。圖6(a)為采取策略2進行謠言抑制的仿真圖,即隨機選擇α×N個節點降低其傳播謠言的博弈收益；圖6(b)為采取策略1進行謠言抑制的仿真圖,將網絡中節點按照危害程度θ由大到小進行排列,選擇前α×N個節點告知其謠言真相,進行謠言抑制。對比兩種抑制策略,在WS小世界網絡中選擇策略1進行謠言抑制具有更好的效果。

圖7為在BA無標度網絡中采取本文所提兩種謠言抑制策略的仿真結果圖。圖7(a)為采取策略2進行謠言抑制的仿真圖,即隨機選擇α×N個節點降低其傳播謠言的博弈收益。圖7(b)為采取策略1進行謠言抑制的仿真圖,將網絡中節點按照危害程度θ由大到小進行排列,選擇前α×N個節點告知其謠言真相,進行謠言抑制。對比圖7(a)、(b),可發現在BA無標度網絡中選擇策略1進行謠言抑制具有更好的效果。

圖8為在Facebook真實網絡中采取本文所提兩種謠言抑制策略的仿真結果圖。對比圖8(a)、(b)可以發現，在Facebook真實網絡中選擇策略1進行謠言抑制具有更好的效果。

圖7 在BA網絡上進行謠言抑制

圖8 在Facebook網絡上進行謠言抑制

通過在三種網絡中實施謠言抑制策略的仿真實驗,結果表明,策略1對謠言抑制的效果優于策略2,由于策略1是選擇鄰居節點中易感染節點數目較大的節點進行的精準抑制,因此能從源頭上減少感染節點數目,具有較好的謠言抑制效果。

4 結語

復雜網絡中謠言傳播類似于某種思想入侵,受多種因素影響,本文考慮度不同的節點對謠言辨識能力不同,結合節點度定義了一種新的博弈收益,基于博弈論構造了一種動態復雜網絡演化模型,提出了兩種謠言抑制策略,并對抑制效果作了比較。針對所提模型在兩種典型的網絡中進行仿真實驗,并利用Facebook真實網絡數據對仿真的正確性進行檢驗。仿真結果表明，考慮節點度的演化博弈模型能夠有效反映涉及節點利益的謠言在社交網絡中的傳播特性。研究過程中,為了分析問題的方便,本文考慮了博弈收益值恒定的情況,博弈收益隨時間變化時謠言傳播會出現什么樣的變化是今后研究的一個重點。

參考文獻(References)

[1] NEKOVEE M, MORENO Y, BIANCONI G, et al. Theory of rumour spreading in complex social networks[J]. Physica A: Statistical Mechanics & its Applications, 2008, 374(1): 457-470.

[2] LI D, MA J, TIAN Z, et al. An evolutionary game for the diffusion of rumor in complex networks[J]. Physica A: Statistical Mechanics & its Applications, 2015, 433(C): 51-58.

[3] QIU X, ZHAO L, WANG J, et al. Effects of time-dependent diffusion behaviors on the rumor spreading in social networks[J]. Physics Letters A, 2016, 380(24): 2054-2063.

[4] WATTS D J, STROGATZ S H. Collective dynamics of ’small-world’ networks [J]. Nature, 1998, 393(6684): 440-442.

[5] 李新鋒. 復雜網絡可控性基礎理論研究[D]. 杭州: 浙江大學, 2017: 32-45.(LI X F. Research on the fundamental theory of controllability of complex networks[D]. Hangzhou: Zhejiang University, 2017: 32-45.)

[7] ZHU L, WANG Y. Rumor spreading model with noise interference in complex social networks[J]. Physica A: Statistical Mechanics & its Applications, 2017, 469(C): 750-760.

[8] 朱冠樺, 蔣國平, 夏玲玲. 社交網絡上從眾現象對謠言傳播影響的研究[J]. 計算機科學, 2016, 43(2): 135-139.(ZHU G H, JIANG G P, XIA L L. Rumor spreading model considering conformity phenomena in complex social networks [J]. Computer Science, 2016, 43(2): 135-139.)

[9] 王亞奇, 王靜. 考慮好奇心理機制的動態復雜網絡謠言傳播研究[J]. 山東大學學報(理學版), 2017, 52(6): 99-104.(WANG Y Q, WANG J. Rumor spreading on dynamic complex networks with curious psychological mechanism [J]. Journal of Shandong University (Natural Science), 2017, 52(6): 99-104.)

[10] XIA L L, JIANG G P, SONG B, et al. Rumor spreading model considering hesitating mechanism in complex social networks[J]. Physica A: Statistical Mechanics & its Applications, 2015, 437(C): 295-303.

[11] JIANG C, CHEN Y, LIU K J R. Evolutionary dynamics of information diffusion over social networks[J]. IEEE Transactions on Signal Processing, 2013, 62(17): 4573-4586.

[12] 李燕. 空間囚徒困境博弈中合作解的演化——基于個體遷徙機制和計算經濟學的視角[D]. 杭州: 浙江大學, 2016: 40-65.(LI Y. The evolution of cooperation in spatial prisoner’s dilemma game [J]. Hangzhou: Zhejiang University, 2016: 40-65.)

[13] CEPARANO M C, QUARTIERI F. Nash equilibrium uniqueness in nice games with isotone best replies[J]. Journal of Mathematical Economics, 2017, 70: 154-165.

[14] LIN D, WANG Q. A game theory based energy efficient clustering routing protocol for WSNs[J]. Wireless Networks, 2017, 23(4): 1-11.

[15] HE Z, CAI Z, YU J, et al. Cost-efficient strategies for restraining rumor spreading in mobile social networks[J]. IEEE Transactions on Vehicular Technology, 2017, 66(3): 2789-2800.

[16] 肖云鵬, 李松陽, 劉宴兵. 一種基于社交影響力和平均場理論的信息傳播動力學模型[J]. 物理學報, 2017, 66(3): 227-239.(XIAO Y P, LI S Y, LIU Y B. An information diffusion dynamic model based on social influence and mean-field theory [J]. Acta Physica Sinica, 2017, 66(3): 227-239.)

[17] 吳騰飛, 周昌樂, 王小華, 等. 基于平均場理論的微博傳播網絡模型[J]. 物理學報, 2014, 63(24): 44-51.(WU T F, ZHOU C L, WANG X H, et al. Microblog propagation network model based on mean-field theory [J]. Acta Physica Sinica, 2014, 63(24): 44-51.)

[18] DADLANI A, KUMAR M S, MADDI M G, et al. Mean-field dynamics of inter-switching memes competing over multiplex social networks[J]. IEEE Communications Letters, 2017, 21(5): 967-970.

[19] WANG Y Q, WANG J. SIR rumor spreading model considering the effect of difference in nodes’ identification capabilities[J]. International Journal of Modern Physics C, 2017, 28(5): 92-100.

[20] LESKOVEC J, KREVL A. SNAP datasets [EB/OL]. [2017- 11- 11]. http: //snap.stanford.edu/data.

This work is partially supported by the National Natural Science Foundation of China (61402531), the Natural Science Basic Research Project of Shaanxi Province (2014JQ8358, 2015JQ6231, 2014JQ8307).