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

臧正功，丁 箐

(中國科學技術大學 軟件學院，安徽 合肥230051)

0 引言

謠言是指未經驗證或者篡改真實的信息[1]，隨著通信網絡的快速發展、即時通信和新興互聯網技術的應用，謠言傳播在速度和廣度遠超歷史任何時代。惡意謠言可能造成遠超以往的大范圍恐慌和嚴重經濟損失[2]，對信息擴散過程與謠言抑制的研究成為社交網絡的研究重點。

由于謠言擴散過程類似于疾病傳播機制，經典的易感染去除模型SIR被借鑒和改進，文獻[3]基于改進的八態ICSAR模型(無知者，信息載體，信息傳播者，擁護者，撤離者)，建立了一個針對謠言傳播的動態時空綜合風險評估模型。文獻[4]建立了具有動態友誼的隨機異構網絡SHIR模型，將社交網絡中最常見的友情變化現象納入其中。

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

博弈論作為分析用戶決策與競爭現象的典型數學工具被廣泛應用于謠言抑制。文獻[8]提出一種演化博弈模型來分析謠言過程，該模型考慮了用戶的多維屬性，并量化了外部和內部驅動因素對群體狀態轉變的影響。文獻[9]通過將社交網絡中的謠言傳播建模為一種協作博弈，發現具有無標度屬性網絡可以更容易地促進謠言傳播。傳統的博弈論條件依賴度無限大，混合人口的假設，通過微分方程研究整體演化的動態過程[8-10]。但現實社交網絡中面對有限、非理性個體時，如何對社交網圖結構中輿情控制提出有效建模成為重點。針對網絡結構和擴散動力學的研究有助于更好地理解網絡的演化機制，因此本文引入圖進化博弈理論[11]來研究網絡結構策略的演化。

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

本文在圖論的基礎上采用演化博弈概念，引入遺憾最小化算法來研究網絡中謠言抑制與用戶策略的演化。本文的貢獻可歸納為：(1)結合圖演化博弈論，考慮個體特征與社交網絡規則圖結構，提出了新型演化博弈模型；(2)利用次優對手弱點，提出遺憾最小化算法實現個體更新策略。

1 模型構建

本節介紹了用于謠言控制的進化博弈模型的構建。首先設計博弈模型的收益矩陣，然后計算策略更新的復制動力方程，最后獲得演化穩定狀態的條件。

1.1 演化模型描述

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

網絡建模為圖 G=(V，E，A，P，U)，其中 V 為節點集；E是邊關系集；A表示節點的行為集，節點的交互行為與其采用策略有關；P是隨機事件概率函數；U是節點的效用函數。本文所用的參數定義如表1所示。

表1 參數定義

通常用戶對謠言或者反謠言的興趣取決于其對信息內容的認知，本文參照文獻[3]將其設定為固定參數；而謠言與反謠言強度意味著能促使輿情擴散的力度，本文依據文獻[6]謠言傳播強度SR取決于謠言主題的嚴重性與歧義性，反謠言強度SAR取決于反謠言機構的權威性與證據真實性。同時政府等權威機構發布反謠言新的概率為RC：當謠言傳播人數NRS超過風險人數閾值Q=βN時，政府將開始傳播反謠言，其中0＜β＜1，為風險系數，謠言控制中心對所有傳播謠言的節點實施成本為PUN的懲罰。

為簡單起見，將支付矩陣的參數組合為3個變量：UR，UAR，UI，如下所示：

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

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

其中，aij表示策略i對抗策略 j的收益。收益博弈動力學從充分混合群(完整圖)移動到度為k的規則圖上，可以近似通過回報矩陣的轉換來描述：

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

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

1.2 遺憾最小化算法策略更新規則

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

其含義為用戶在第t輪依據策略執行動作a，與相對按照最佳響應策略σ*采取動作效用值之差。若該值為正，則說明用戶應較多地執行動作a*，否則會產生遺憾。因此用戶i的T輪累積遺憾值為：

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

動態估計法則對新產生的博弈結果賦予更高的權重，使遺憾價值更能夠體現對手策略的動態變化。詳細過程見算法1。

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

輸出：σT+1(a)

(1)for每一輪博弈

(2)按照 σi與對手進行博弈

(3)記錄博弈收益U，并計算出即時遺憾價值 r；

(4)對每一個動作進行虛擬遺憾價值的更新R，并計算不同策略占比，更新其策略；

(5)end for

1.3 進化穩定策略證明

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

2 博弈模型仿真結果與分析

2.1 數據描述

本文使用了兩種真實的社交網絡數據集，如表2所示。第一個是Blog數據集，該數據集包含該社交博客目錄網站的友誼關系以及成員身份。第二個是電子郵件數據集(DNC emails)。網絡中的節點對應于數據集中的人員。數據集均符合典型冪律度分布。

表2 網絡參數

本節嘗試通過對不同的仿真來分析所提出的模型。首先，針對三種策略和ESS條件計算復制器動力學，并在圖中進行了說明，以進行參數樣本評估。其次，基于數據集的兩個真實世界圖進行謠言傳播實驗,以驗證復制動力學的進化穩定狀態。

2.2 復制動態方程

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

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

2.3 基于不同圖的模型仿真

(1)BA圖模型進行數值模擬

研究表明現實社交網絡通常都具有無標度特性，因此使用BA圖模型進行數值模擬。

圖1展示狀態RS、ARS和I策略節點在Barabasi-Albert無標度網絡上隨迭代時間變化的擴散過程，并通過模擬進化更新規則得出仿真結果。實驗對生成的1 000個節點采取不同策略進行隨機初始化，其收益矩陣參數初始化等同上節復制動力學的樣本參數。從圖1可見，BA網絡的演化博弈模型仿真結果與數值推理一致，并且ARS策略為演化穩定狀態。

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

(2)真實社交圖仿真

本節按照比例初始化三種狀態的用戶節點，支付矩陣的初始化參照于樣本參數。

圖 2中(a)與(b)分別顯示 Blog和 DNC兩種真實社交圖上的仿真結果。其中圖(a)最終ARS態節點比例較圖(b)高，且網絡中易感節點占比遠低于圖(b)，但二者穩態時ARS比例均低于圖(1)中BA圖。

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

(3)不同模型過程對比

圖2 謠言、反謠言、無知者在Blog與DNC真實網絡圖的模擬結果

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

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

實驗結果顯示，第二組模型中謠言者RS會在短暫上升后逐漸下降，最終趨向穩態，而其ARS策略趨向穩態時占比與第一組模型相似，但所需時間較長。這是因為第二組模型中SHIR分別代表易感、已知、感染、恢復四種狀態，網絡中感染節點I會在傳播初期感染大量易感節點S后，才會產生已知節點K來進行反謠言的對抗，從而導致初期RS占比的短暫提升。第三組模型較第一、二組網絡中ARS占比較低，其原因在于在相同懲罰成本的情況下，用戶盲目選擇鄰居策略較多導致整體謠言抑制效果較弱。

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

圖4 不同謠言策略與風險系數β所對應的NARSDM和最終數量

3 結束語

本文提出一種圖演化博弈模型用于分析社交圖譜上用戶決策與謠言擴散過程。首先針對完整圖規則與現實網拓撲差異，在圖論的基礎上采用演化博弈，設置策略更新規則中采取遺憾匹配與動態折扣，同時通過定義反謠言傳播者支配措施NARSDM衡量網絡中風險閾值比例與狀態節點數量關系。實驗部分首先在無標度圖BA上進行數值模擬，節點采取不同策略初始化，結果表明ARS策略為ESS狀態。然后在兩真實世界圖進行仿真，仿真結果表明真實世界圖中進化穩態狀態與復制動態方程具有一致性。