基于遺憾最小化算法的謠言抑制與演化博弈模型*

臧正功，丁 箐

(中國(guó)科學(xué)技術(shù)大學(xué) 軟件學(xué)院，安徽 合肥230051)

0 引言

謠言是指未經(jīng)驗(yàn)證或者篡改真實(shí)的信息[1]，隨著通信網(wǎng)絡(luò)的快速發(fā)展、即時(shí)通信和新興互聯(lián)網(wǎng)技術(shù)的應(yīng)用，謠言傳播在速度和廣度遠(yuǎn)超歷史任何時(shí)代。惡意謠言可能造成遠(yuǎn)超以往的大范圍恐慌和嚴(yán)重經(jīng)濟(jì)損失[2]，對(duì)信息擴(kuò)散過程與謠言抑制的研究成為社交網(wǎng)絡(luò)的研究重點(diǎn)。

由于謠言擴(kuò)散過程類似于疾病傳播機(jī)制，經(jīng)典的易感染去除模型SIR被借鑒和改進(jìn)，文獻(xiàn)[3]基于改進(jìn)的八態(tài)ICSAR模型(無知者，信息載體，信息傳播者，擁護(hù)者，撤離者)，建立了一個(gè)針對(duì)謠言傳播的動(dòng)態(tài)時(shí)空綜合風(fēng)險(xiǎn)評(píng)估模型。文獻(xiàn)[4]建立了具有動(dòng)態(tài)友誼的隨機(jī)異構(gòu)網(wǎng)絡(luò)SHIR模型，將社交網(wǎng)絡(luò)中最常見的友情變化現(xiàn)象納入其中。

與病毒感染不同，真實(shí)謠言傳播依賴于社交網(wǎng)絡(luò)中人的交互，而基于傳染病模型的研究忽略了人在散布謠言中的自主作用。與疾病傳播相反，個(gè)人在謠言傳播過程中實(shí)際是自我決策問題。如何有效利用個(gè)體策略，抑制謠言傳播成為研究的主要目的。疫苗接種理論[5]被引入到實(shí)際運(yùn)用中。文獻(xiàn)[6]嘗試使用個(gè)人或者權(quán)威機(jī)構(gòu)發(fā)送反謠言信息來抑制謠言。此外謠言抑制還取決于接受者與傳播者的特征、親密關(guān)系、謠言強(qiáng)度等因素[7]。

博弈論作為分析用戶決策與競(jìng)爭(zhēng)現(xiàn)象的典型數(shù)學(xué)工具被廣泛應(yīng)用于謠言抑制。文獻(xiàn)[8]提出一種演化博弈模型來分析謠言過程，該模型考慮了用戶的多維屬性，并量化了外部和內(nèi)部驅(qū)動(dòng)因素對(duì)群體狀態(tài)轉(zhuǎn)變的影響。文獻(xiàn)[9]通過將社交網(wǎng)絡(luò)中的謠言傳播建模為一種協(xié)作博弈，發(fā)現(xiàn)具有無標(biāo)度屬性網(wǎng)絡(luò)可以更容易地促進(jìn)謠言傳播。傳統(tǒng)的博弈論條件依賴度無限大，混合人口的假設(shè)，通過微分方程研究整體演化的動(dòng)態(tài)過程[8-10]。但現(xiàn)實(shí)社交網(wǎng)絡(luò)中面對(duì)有限、非理性個(gè)體時(shí)，如何對(duì)社交網(wǎng)圖結(jié)構(gòu)中輿情控制提出有效建模成為重點(diǎn)。針對(duì)網(wǎng)絡(luò)結(jié)構(gòu)和擴(kuò)散動(dòng)力學(xué)的研究有助于更好地理解網(wǎng)絡(luò)的演化機(jī)制，因此本文引入圖進(jìn)化博弈理論[11]來研究網(wǎng)絡(luò)結(jié)構(gòu)策略的演化。

社交網(wǎng)絡(luò)中當(dāng)非理性對(duì)手不再使用納什均衡策略博弈時(shí)，此時(shí)納什均衡策略并不保證是最佳反應(yīng)。為滿足實(shí)時(shí)博弈中對(duì)策略的完善，利用對(duì)手弱點(diǎn)往往能取得更高回報(bào)，故提出從自我遺憾最小化角度建模[12]。其思想是從遺憾最小化的角度來利用次優(yōu)對(duì)手弱點(diǎn)，并基于一種離線的均衡計(jì)算，從個(gè)體自身選擇的經(jīng)驗(yàn)中學(xué)習(xí)更新策略。文獻(xiàn)[13]探討了政府的懲罰和個(gè)人的敏感性如何影響謠言的演變。由此可見，網(wǎng)絡(luò)結(jié)構(gòu)、謠言強(qiáng)度、用戶策略以及謠言控制中心存在與否都影響著其傳播。

本文在圖論的基礎(chǔ)上采用演化博弈概念，引入遺憾最小化算法來研究網(wǎng)絡(luò)中謠言抑制與用戶策略的演化。本文的貢獻(xiàn)可歸納為：(1)結(jié)合圖演化博弈論，考慮個(gè)體特征與社交網(wǎng)絡(luò)規(guī)則圖結(jié)構(gòu)，提出了新型演化博弈模型；(2)利用次優(yōu)對(duì)手弱點(diǎn)，提出遺憾最小化算法實(shí)現(xiàn)個(gè)體更新策略。

1 模型構(gòu)建

本節(jié)介紹了用于謠言控制的進(jìn)化博弈模型的構(gòu)建。首先設(shè)計(jì)博弈模型的收益矩陣，然后計(jì)算策略更新的復(fù)制動(dòng)力方程，最后獲得演化穩(wěn)定狀態(tài)的條件。

1.1 演化模型描述

本文討論謠言和權(quán)威信息同時(shí)在復(fù)雜的社交網(wǎng)絡(luò)中傳播。假設(shè)當(dāng)個(gè)人傳播一條信息時(shí)，他或她的所有朋友都可以閱讀。用戶有三種可能的動(dòng)作：謠言傳播、反謠言傳播以及忽略謠言或反謠言。反謠言是說服人們謠言不真實(shí)的信息。因此，此處考慮三種策略：謠言傳播(RS)、反謠言傳播(ARS)和無知(I)。

網(wǎng)絡(luò)建模為圖 G=(V，E，A，P，U)，其中 V 為節(jié)點(diǎn)集；E是邊關(guān)系集；A表示節(jié)點(diǎn)的行為集，節(jié)點(diǎn)的交互行為與其采用策略有關(guān)；P是隨機(jī)事件概率函數(shù)；U是節(jié)點(diǎn)的效用函數(shù)。本文所用的參數(shù)定義如表1所示。

表1 參數(shù)定義

通常用戶對(duì)謠言或者反謠言的興趣取決于其對(duì)信息內(nèi)容的認(rèn)知，本文參照文獻(xiàn)[3]將其設(shè)定為固定參數(shù)；而謠言與反謠言強(qiáng)度意味著能促使輿情擴(kuò)散的力度，本文依據(jù)文獻(xiàn)[6]謠言傳播強(qiáng)度SR取決于謠言主題的嚴(yán)重性與歧義性，反謠言強(qiáng)度SAR取決于反謠言機(jī)構(gòu)的權(quán)威性與證據(jù)真實(shí)性。同時(shí)政府等權(quán)威機(jī)構(gòu)發(fā)布反謠言新的概率為RC：當(dāng)謠言傳播人數(shù)NRS超過風(fēng)險(xiǎn)人數(shù)閾值Q=βN時(shí)，政府將開始傳播反謠言，其中0＜β＜1，為風(fēng)險(xiǎn)系數(shù)，謠言控制中心對(duì)所有傳播謠言的節(jié)點(diǎn)實(shí)施成本為PUN的懲罰。

為簡(jiǎn)單起見，將支付矩陣的參數(shù)組合為3個(gè)變量：UR，UAR，UI，如下所示：

設(shè)定回報(bào)收益已歸一化(0，1)間，收益的物理含義是可能取得的回報(bào)。例如當(dāng)具有策略RS的用戶A與具有策略I的用戶B相遇時(shí)，B會(huì)以的比率成為RS，n為策略個(gè)數(shù)。相同策略的用戶交互收益為 0。

式(4)表示博弈模型的收益矩陣。在完整圖博弈中，所有個(gè)體都相鄰，根據(jù)與所有相鄰個(gè)體的交互來局部確定個(gè)體的適應(yīng)性。文獻(xiàn)[11]考慮進(jìn)化動(dòng)力學(xué)更新規(guī)則(IM)，其代表用戶策略頻率隨時(shí)間變化的方式。本文考慮網(wǎng)絡(luò)中靜態(tài)結(jié)構(gòu)，不涉及網(wǎng)絡(luò)單個(gè)節(jié)點(diǎn)的消亡。針對(duì)IM規(guī)則，定義動(dòng)態(tài)微分方程來描述圖表上每個(gè)人的期望頻率隨時(shí)間的變化，見式(5)。考慮n個(gè)進(jìn)化策略，總收益矩陣A=[aij]。同時(shí)更新機(jī)制定義了 n×n矩陣 B=[bij]，如下在度為 k的無限大圖中：

其中，aij表示策略i對(duì)抗策略 j的收益。收益博弈動(dòng)力學(xué)從充分混合群(完整圖)移動(dòng)到度為k的規(guī)則圖上，可以近似通過回報(bào)矩陣的轉(zhuǎn)換來描述：

這里 A=[aij]，B=[bij]，等式(6)解釋了兩 個(gè)矩 陣之間的變換。實(shí)驗(yàn)論證與事實(shí)表明[11]，對(duì)于非規(guī)則圖，博弈從充分混合的總體移至規(guī)則圖形只導(dǎo)致收益矩陣的轉(zhuǎn)換。因此，新的收益矩陣是原始收益矩陣加上另一個(gè)矩陣的總和。

轉(zhuǎn)換后的收益矩陣[aij+bij]可通過式(9)獲得：

1.2 遺憾最小化算法策略更新規(guī)則

博弈過程中的遺憾是指通過對(duì)過去博弈中動(dòng)作的遺憾程度來預(yù)測(cè)未來動(dòng)作選擇，定義σi為用戶i所使用的策略，博弈中除i以外的參與者策略為σ-i，則對(duì) σi的最佳響應(yīng)策略有：

其含義為用戶在第t輪依據(jù)策略執(zhí)行動(dòng)作a，與相對(duì)按照最佳響應(yīng)策略σ*采取動(dòng)作效用值之差。若該值為正，則說明用戶應(yīng)較多地執(zhí)行動(dòng)作a*，否則會(huì)產(chǎn)生遺憾。因此用戶i的T輪累積遺憾值為：

在迭代過程中玩家對(duì)動(dòng)作集進(jìn)行分配時(shí)，即時(shí)遺憾值將用來進(jìn)行下一輪的迭代策略更新，通過不同動(dòng)作的積極遺憾值匹配，使得遺憾向均衡收斂。故T+1輪迭代中，用戶i根據(jù)概率選擇動(dòng)作a∈A，有：

動(dòng)態(tài)估計(jì)法則對(duì)新產(chǎn)生的博弈結(jié)果賦予更高的權(quán)重，使遺憾價(jià)值更能夠體現(xiàn)對(duì)手策略的動(dòng)態(tài)變化。詳細(xì)過程見算法1。

算法1折扣遺憾最小化的在線算法

輸出：σT+1(a)

(1)for每一輪博弈

(2)按照 σi與對(duì)手進(jìn)行博弈

(3)記錄博弈收益U，并計(jì)算出即時(shí)遺憾價(jià)值 r；

(4)對(duì)每一個(gè)動(dòng)作進(jìn)行虛擬遺憾價(jià)值的更新R，并計(jì)算不同策略占比，更新其策略；

(5)end for

1.3 進(jìn)化穩(wěn)定策略證明

如果策略ARS執(zhí)行概率占比高于其他策略[14]，即 PARS＞PRS且 PARS＞PI，則 ARS 為進(jìn)化穩(wěn)定策略(ESS)。具體分析如下：假設(shè) A→B，根據(jù)文獻(xiàn)[14]依次可得：

2 博弈模型仿真結(jié)果與分析

2.1 數(shù)據(jù)描述

本文使用了兩種真實(shí)的社交網(wǎng)絡(luò)數(shù)據(jù)集，如表2所示。第一個(gè)是Blog數(shù)據(jù)集，該數(shù)據(jù)集包含該社交博客目錄網(wǎng)站的友誼關(guān)系以及成員身份。第二個(gè)是電子郵件數(shù)據(jù)集(DNC emails)。網(wǎng)絡(luò)中的節(jié)點(diǎn)對(duì)應(yīng)于數(shù)據(jù)集中的人員。數(shù)據(jù)集均符合典型冪律度分布。

表2 網(wǎng)絡(luò)參數(shù)

本節(jié)嘗試通過對(duì)不同的仿真來分析所提出的模型。首先，針對(duì)三種策略和ESS條件計(jì)算復(fù)制器動(dòng)力學(xué)，并在圖中進(jìn)行了說明，以進(jìn)行參數(shù)樣本評(píng)估。其次，基于數(shù)據(jù)集的兩個(gè)真實(shí)世界圖進(jìn)行謠言傳播實(shí)驗(yàn),以驗(yàn)證復(fù)制動(dòng)力學(xué)的進(jìn)化穩(wěn)定狀態(tài)。

2.2 復(fù)制動(dòng)態(tài)方程

本文研究中，推導(dǎo)出了式(15)、(16)、(17)，對(duì)于變量的樣本配置，此處列出樣本初始收益矩陣參數(shù)：IR=0.2，SR=0.2，IAR=0.3，SAR=0.3，PUN=0.1，PNP=0.25，β=0.1，折扣因子 λ=0.9。

設(shè)置初始策略比例為：RS=0.25，ARS=0.05，I=0.70。根據(jù)等式中給出的演化穩(wěn)定策略的初始值有：滿足ARS為 ESS的前提。

2.3 基于不同圖的模型仿真

(1)BA圖模型進(jìn)行數(shù)值模擬

研究表明現(xiàn)實(shí)社交網(wǎng)絡(luò)通常都具有無標(biāo)度特性，因此使用BA圖模型進(jìn)行數(shù)值模擬。

圖1展示狀態(tài)RS、ARS和I策略節(jié)點(diǎn)在Barabasi-Albert無標(biāo)度網(wǎng)絡(luò)上隨迭代時(shí)間變化的擴(kuò)散過程，并通過模擬進(jìn)化更新規(guī)則得出仿真結(jié)果。實(shí)驗(yàn)對(duì)生成的1 000個(gè)節(jié)點(diǎn)采取不同策略進(jìn)行隨機(jī)初始化，其收益矩陣參數(shù)初始化等同上節(jié)復(fù)制動(dòng)力學(xué)的樣本參數(shù)。從圖1可見，BA網(wǎng)絡(luò)的演化博弈模型仿真結(jié)果與數(shù)值推理一致，并且ARS策略為演化穩(wěn)定狀態(tài)。

圖1 謠言、反謠言、無知者在BA圖模擬比例

(2)真實(shí)社交圖仿真

本節(jié)按照比例初始化三種狀態(tài)的用戶節(jié)點(diǎn)，支付矩陣的初始化參照于樣本參數(shù)。

圖 2中(a)與(b)分別顯示 Blog和 DNC兩種真實(shí)社交圖上的仿真結(jié)果。其中圖(a)最終ARS態(tài)節(jié)點(diǎn)比例較圖(b)高，且網(wǎng)絡(luò)中易感節(jié)點(diǎn)占比遠(yuǎn)低于圖(b)，但二者穩(wěn)態(tài)時(shí)ARS比例均低于圖(1)中BA圖。

與BA圖模擬結(jié)果的差異來自于真實(shí)圖形結(jié)構(gòu)差異化。例如參考到DNC圖的平均聚類系數(shù)為54.8%，比BA圖聚類系數(shù)2.5%較大，這是因?yàn)镈NC中包含較多自我中心網(wǎng)絡(luò)(ego network)，并且處于不同自我中心網(wǎng)絡(luò)的用戶彼此間訪問受限[15]，因此策略難以傳播到整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)。但仍可以在真實(shí)社交網(wǎng)絡(luò)圖的仿真結(jié)果與復(fù)制動(dòng)態(tài)方程間找到一致性。而聚類系數(shù)較小的Blog圖與DNC相比最終治愈者比例更高，更快收斂至進(jìn)化穩(wěn)定狀態(tài)。從圖(a)與圖(b)的快照中可以看出，ARS策略是進(jìn)化穩(wěn)定狀態(tài)，即在真實(shí)圖形上的仿真結(jié)果與復(fù)制器方程之間存在相當(dāng)好的一致性。這個(gè)結(jié)果意味著可以使用該演化博弈的復(fù)制方程來對(duì)社交網(wǎng)絡(luò)進(jìn)行進(jìn)化博弈分析。

(3)不同模型過程對(duì)比

圖2 謠言、反謠言、無知者在Blog與DNC真實(shí)網(wǎng)絡(luò)圖的模擬結(jié)果

圖3 三種不同模型下謠言、反謠言者在Blog和DNC模擬過程

圖3 表示不同社交網(wǎng)絡(luò)中，本文模型與文獻(xiàn)[4]、[8]兩類演化博弈模型間關(guān)于謠言者、反謠言者的模擬過程。其中第一組為本文所提模型；第二組為SHIR[4]，該模型充分考慮反謠言和用戶心理因素，運(yùn)用進(jìn)化博弈論和多元信息回歸方法來構(gòu)建信息傳播進(jìn)化模型；第三組為 RDG模型[8]，該模型假設(shè)個(gè)人根據(jù)不同的親密強(qiáng)度選擇鄰居之一進(jìn)行策略模仿，探究懲罰成本與鄰居策略對(duì)輿情擴(kuò)散的影響。

實(shí)驗(yàn)結(jié)果顯示，第二組模型中謠言者RS會(huì)在短暫上升后逐漸下降，最終趨向穩(wěn)態(tài)，而其ARS策略趨向穩(wěn)態(tài)時(shí)占比與第一組模型相似，但所需時(shí)間較長(zhǎng)。這是因?yàn)榈诙M模型中SHIR分別代表易感、已知、感染、恢復(fù)四種狀態(tài)，網(wǎng)絡(luò)中感染節(jié)點(diǎn)I會(huì)在傳播初期感染大量易感節(jié)點(diǎn)S后，才會(huì)產(chǎn)生已知節(jié)點(diǎn)K來進(jìn)行反謠言的對(duì)抗，從而導(dǎo)致初期RS占比的短暫提升。第三組模型較第一、二組網(wǎng)絡(luò)中ARS占比較低，其原因在于在相同懲罰成本的情況下，用戶盲目選擇鄰居策略較多導(dǎo)致整體謠言抑制效果較弱。

圖4繪制了兩個(gè)社交網(wǎng)絡(luò)中不同風(fēng)險(xiǎn)閾值比率和治愈者與傳播者平均最終數(shù)量，為更好地理解結(jié)果，定義反謠言傳播者支配措施NARSDM=值得注意的是，當(dāng)網(wǎng)絡(luò)中風(fēng)險(xiǎn)閾值較小時(shí)，即存在少量謠言傳播者也將受到懲罰，此時(shí)謠言傳播覆蓋面較小，NARSDM較大，隨著風(fēng)險(xiǎn)閾值的擴(kuò)大，網(wǎng)絡(luò)中謠言覆蓋面變大，NARSDM變小，即風(fēng)險(xiǎn)閾值β與NARSDM成負(fù)相關(guān)。風(fēng)險(xiǎn)閾值增大意味著更多的謠言傳播者將面臨被懲罰的負(fù)擔(dān)，從而使得策略更新時(shí)，選擇反謠言的遺憾值更大,從而更多用戶選擇傳播ARS。從圖4可以看出，當(dāng)風(fēng)險(xiǎn)閾值從0.2降至0.1時(shí)，網(wǎng)絡(luò)中最終存在的治愈者比例并沒有大幅度提高。

圖4 不同謠言策略與風(fēng)險(xiǎn)系數(shù)β所對(duì)應(yīng)的NARSDM和最終數(shù)量

3 結(jié)束語(yǔ)

本文提出一種圖演化博弈模型用于分析社交圖譜上用戶決策與謠言擴(kuò)散過程。首先針對(duì)完整圖規(guī)則與現(xiàn)實(shí)網(wǎng)拓?fù)洳町?，在圖論的基礎(chǔ)上采用演化博弈，設(shè)置策略更新規(guī)則中采取遺憾匹配與動(dòng)態(tài)折扣，同時(shí)通過定義反謠言傳播者支配措施NARSDM衡量網(wǎng)絡(luò)中風(fēng)險(xiǎn)閾值比例與狀態(tài)節(jié)點(diǎn)數(shù)量關(guān)系。實(shí)驗(yàn)部分首先在無標(biāo)度圖BA上進(jìn)行數(shù)值模擬，節(jié)點(diǎn)采取不同策略初始化，結(jié)果表明ARS策略為ESS狀態(tài)。然后在兩真實(shí)世界圖進(jìn)行仿真，仿真結(jié)果表明真實(shí)世界圖中進(jìn)化穩(wěn)態(tài)狀態(tài)與復(fù)制動(dòng)態(tài)方程具有一致性。