一種真假信息傳播能力評估的動態規劃算法

俞山青，鄭 鈞，殳欣成，阮中遠

1(浙江工業大學 信息工程學院，杭州 310000) 2(浙江工業大學 計算機學院，杭州 310000)

1 引 言

近年來，隨著信息技術的不斷發展，Twitter、Facebook、微博等社交媒體正逐漸成為人們生活中必不可少的組成部分.由這些媒體平臺[1]構建的社交網絡加速了信息的傳播，成為人們新獲取聞、宣傳產品、共享資源的重要途徑.但與此同時，這也為虛假消息[2，3]、惡意營銷[4-6]等負面信息創造了傳播條件.這些有害信息的肆意傳播，將會危害公共輿論安全、誤導人們的行為，繼而對社會產生惡劣的影響.

信息傳播領域涉及廣泛，包含物理學、經濟學、計算機科學和社會學等多個學科[7-9].信息傳播的主要研究內容包含節點的影響范圍[10]和信息傳播的動態過程[11].其中，線性閾值模型(Linear Threshold Model，LT)[12]和獨立級聯模型(Independent Cascade Model，IC)[13]是兩種傳統社交網絡傳播模型.許多傳播領域的研究在這兩種模型的基礎上展開[14-16]，比如Kempe等人[17]將傳播影響力轉化為離散優化問題，證明了該問題屬于NP-hard問題，并給出了基于貪心優化算法的近似解.文獻[18]中針對該問題提出了一種改進的貪心算法，該算法能夠消除各類模型融合的隨機性，提高結果精度，并應用在動態網絡的影響擴散問題中.然而，這些研究都只考慮了單一屬性信息的傳播影響力，且并未考慮社交網絡中不同類型的節點對傳播過程可能產生的不同作用.

在對真假信息的傳播影響力研究中[19，20]，研究人員認識到網絡中不同的節點和連邊在傳播過程中起到的作用是不同的.另一方面，對真信息和假信息傳播過程一概而論的分析也存在著不合理性[21].例如，一些節點可能會自發地接受信息而不受其鄰居節點的影響；另一些免疫節點可能會拒絕傳播虛假的信息等.針對這些屬性的特殊節點和不同類型的信息，文獻[22]提出了一種真假信息傳播模型和評估信息過濾能力的指標(Information Filtering Ability，IFA)，分析了不同網絡拓撲和不同屬性的節點對真假信息傳播的影響.該模型考慮了兩種屬性的節點：智慧節點和普通節點，以及兩種不同類型的信息：真信息和假信息.文章采用蒙特卡羅法對傳播過程進行仿真，并計算信息過濾能力指標.蒙特卡羅法[23]是在充分多次仿真的情況下，計算出所有結果的平均值，從而得到近似解的方法.這種方法是傳播領域研究中應用最為廣泛的方法之一.然而，蒙特卡羅方法往往需要進行大量的仿真實驗來獲得符合預期精確度的實驗結果，仿真實驗的重復次數多以經驗為準.但在面對較大的網絡數據或不定參數較多的傳播模型時，這種分析方法需要消耗大量的時間，并且實驗結果的精確度難以保證，存在較大的局限性[24].

本文針對真假信息的傳播模型提出了一種真假信息傳播能力評估的動態規劃算法(DynamicProgrammingAlgorithmForTrueandFalseInformationDiffusionAbility，DPA)，該方法能快速地評估真假信息在整個網絡中的傳播影響力，以及不同網絡拓撲結構對信息的過濾能力的影響.該方法包括尋找最短路徑和計算轉發概率兩個步驟.實驗部分，本文提出的基于動態規劃的計算方法在多種不同的拓撲網絡中與文獻[22]中基于蒙特卡羅的評估方法進行了對比.實驗結果表明，本文提出的方法能夠快速得出與蒙特卡羅仿真方法近似的結果，兼顧了時間效率和準確度，為分析真假信息在不同網絡中的傳播影響力及信息過濾能力評估這一類問題提供了新的可行方法.

2 真假信息傳播模型

本文針對包含真假屬性的信息傳播模型[22]研究不同網絡結構的過濾能力.與傳統的傳播模型相比，該模型更接近現實社交網絡中的信息傳播的模式和過程，極具研究意義.該模型定義了兩種不同屬性的節點：智慧節點和普通節點.同時假設社交網絡中有兩種不同類型的信息：真實信息和虛假信息.當信息在社交網絡中傳播時，智慧節點能夠區分信息的真偽，并對假信息加以抑制，而普通節點卻不具備這樣的能力.

2.1 模型描述

假設G=(V，E，W)表示一個加權有向網絡，其中V是節點的集合，E?V×V是邊的集合.vi∈V表示一個節點，eij∈E表示從節點vi到節點vj的有向邊.其中，每條有向邊都有一個權重系數wij∈W，滿足0≤wij≤1，用于度量vj對于vi的信任程度.S和O分別代表智慧節點和普通節點的集合，滿足S∪O=V和足S∩O=?.在信息傳播過程中，節點的狀態有以下3種：

1)未知狀態0，節點未被訪問，沒有收到過來自鄰居節點的信息，該狀態為可變化狀態，可能在傳播過程中發生改變.

2)已知狀態1，節點被訪問，但沒有轉發，該狀態為終態，不會再發生變化.

3)接受狀態2，節點已經被訪問，且將信息轉發給所有鄰居節點，該狀態也為終態，不再發生變化.基于以上描述，信息傳播過程分為以下3個步驟：

·初始化兩種節點集合.選擇節點子集S作為智慧節點集合，其余節點設置為普通節點，包含在普通節點集合O中.

·隨機選擇信息源節點.隨機選擇網絡中的一個節點vi作為信息源節點，對它進行信息傳播，并根據該節點的屬性改變其狀態.

·信息傳播過程.當一個節點vk在t時刻處于未知狀態時，它將觀察其所有入邊的頭節點轉發的信息，然后隨機選取一個入鄰節點j，根據公式(1)改變其狀態：

(1)

普通節點無法區分信息的真假，因此它是否轉發信息的概率與vj到vk的有向權值wij即信任度成正比.在該模型下智慧節點以較高的概率傳遞真實信息，并拒絕轉發假信息，普通節點無法識別傳入信息的屬性，所以傳遞真假信息的概率相同，轉發真信息的概率低于智慧節點，轉發假信息的概率高于智慧節點.

2.2 信息過濾能力的指標

根據2.1節中描述的傳播模型，當信息傳播停止后，用NT和NF分別表示傳遞真信息的節點數和傳遞假信息的節點數.真信息傳輸能力(TrueMessageTransmissionAbility，TTA)和假信息傳輸能力(FalseMessageTransmissionAbility，FTA)分別定義為公式(2):

(2)

其中，N為網絡的總節點數.

社交網絡的信息過濾能力(InformationFilteringAbility，IFA)定義為公式(3):

F=FT-FF

(3)

過濾能力指標F表示社交網絡中節點最終接受真、假信息狀態的密度差異.一般來說，F值越大，表示網絡的信息過濾能力越強，可以將真信息傳遞給更多的節點，同時可以將假信息的傳遞控制在更小的范圍內.

3 一種真假信息傳播能力的動態規劃算法

本文提出了一種真假信息傳播能力評估的動態規劃算法(DynamicProgrammingAlgorithmForTrueandFalseInformationDiffusionAbility，DPA)，將信息在整個網絡傳播的過程看作是網絡中每個節點接收并決定是否轉發信息的獨立子任務的集合，每個節點根據入鄰邊和自身的狀態迭代計算傳播概率直至收斂，并以此來計算近似于IFA的信息過濾能力指標.方法包括3個主要步驟：

步驟1.計算網絡中每個信息源節點到目標節點的最短距離，并得到最短距離矩陣.

步驟2.根據步驟1得到的最短距離矩陣，對各節點的鄰入邊進行排序，并用本文提出的基于動態規劃的計算方法分別迭代計算各節點關于真信息和假信息的傳播概率.

步驟3.根據步驟2中計算得到迭代收斂后每個節點的信息傳播概率，計算整個網絡的信息過濾能力評估指標.

以上的每個步驟將在下文中詳細描述.表1列出了文中使用的符號.

表1 符號表Table 1 Notations Table

3.1 問題的定義

令P∈RN×M=[P1，…，PN]T為傳播概率矩陣，表示從源節點到傳播信息到所有目標節點的概率，其中每個元素Pi，j表示信息從源節點vi發出并轉發到節點vj的概率.對于真信息和假信息，分別定義兩個傳播概率矩陣PT和PF.

3.2 最短距離矩陣的計算

本文首先采用基于Q值的動態規劃算法[25]計算網絡中各邊到源節點的最短距離.與本文提出的方法相似，該方法也采用了動態規劃的思想，無需保留最短路徑中的前置節點的信息.通過方程(4)迭代計算邊eij到源節點o的最短距離Qo(i，j):

Qo(i，j)←ωij+mink∈A(i)Qo(k，i)

(4)

其中ωij表示從節點vi到vj的權重.A(i)表示所有以i為尾節點的邊的頭節點的集合.

3.3 節點信息傳播概率計算

本文將信息傳播的過程看作是每個節點完成自己傳播子任務的過程加和.對于網絡中的每個節點來說，不考慮信息的來源和傳播路徑，僅根據其鄰居節點將信息傳播給它的概率以及它自身的狀態，獨立迭代計算傳播概率.當網絡中所有節點的傳播概率收斂時，則整個網絡的傳播概率計算結束.

一般來說，某節點的傳播概率應該是它的所有鄰居入邊將信息轉發給它的概率和.然而，和文獻[22]一樣，本文采用單次訪問的傳播模型，即某節點在第一次被某信息訪問時，決定是否轉發，即使之后該節點再次被訪問，也不會再改變其轉發狀態.在該模型下，只有在之前沒有其它入邊將信息轉發給該節點的情況下，新的入邊才有可能轉發信息給該節點，單純的概率加和不能還原該模型下的傳播過程.

因此，在本文提出的真假信息傳播能力的動態規劃算法中，對于每個節點vi∈V，首先根據其入邊到源節點的最短距離對vi的所有入邊進行升序排序，得到有序入邊集合Ωi，然后依次用集合中各邊將信息傳播到節點vi的概率更新vi的傳播概率.更新時，入邊eji將信息傳播到節點vi的概率為集合中所有前序入邊不傳遞信息給節點vi的條件下，入邊eji將信息傳播給節點vi的條件概率.為了簡化模型和計算復雜度，這里將前序邊不傳播信息和入邊eji傳播信息這兩個復雜關系的事件看作是完全獨立的事件，通過概率乘積直接計算條件概率.同時，概率值小于一定閥值的小概率事件將不被計算.具體的計算過程在偽代碼算法1和算法2中進行描述.

圖1 計算轉發概率的例子Fig.1 An example for calculating forwarding probability

表的初始化值Table 2 Initialization value of

步驟2.將Q(s，(j，t))進行升序排列，其中j∈A(t).如果節點vt有多條到源節點vs相同最短距離的入邊，則將這兩條路徑都作為可能的傳播路徑.在升序排序后，可以得到一個有序的入邊集合Ωt，包含目標節點vt的所有入邊.

(5)

(6)

設收斂條件Δ為概率矩陣PX在n次迭代與n-1次迭代的差，這里的Δ是一個很小的實數.當概率矩陣PX中的每個元素都不再變化或變化很小時，可以認為該算法收斂，停止迭代.

算法1.轉發概率矩陣的計算

輸入：(G=(V,E,W),S,Q,σ,X)

輸出：(PX)

1.fors∈Vdo

3. fort∈Vdo

5. while 收斂條件Δ未滿足do

7. ifs≠tdo

②在以單個工程為單位實行招標的情況下，個別地方存在低價勝出的現象。由于只強調價格低，忽視了對管材質量的要求和控制，容易出現管材質量得不到保證的現象。

9. end

10. end

11. end

12. end

13.returnPX

算法2.計算OICFP

3. ifgsz·ωzt·η>σdo

7. end

8.end

3.4 計算近似

(7)

(8)

(9)

4 實驗和結果

4.1 數據描述

本文使用了3個典型的合成網絡來進行驗證，包括具有不同平均度值k的ER網絡、BA網絡以及WS網絡.

·ER網絡由隨機ER模型[26]生成.該模型假設網絡中有N個節點和M條邊.隨機選擇一對沒有連邊的節點并添加一條邊，然后，重復M次.因此，可以得到k=2·M/N的網絡，一般通過調整邊的數目M來改變網絡的平均度值.

·WS網絡由Watts-Strogatz模型[28]生成.首先，該模型構造了一個N個節點的環狀最近鄰耦合網絡，每個節點都與它相鄰的k/2個節點相連.利用隨機化重連方法，將固定節點以一定概率隨機地重新連接網絡中原有的連邊來生成網絡.

4.2 實驗設置及參數

針對不同拓撲網絡，實驗依次選擇每個節點作為傳播源來觀察節點的傳播影響.這里選擇節點數N=1000，并假設自然傳播率為常數η=0.9，設置節點之間的有向連邊權重為ωij=0.5.此外，本文在所有節點中隨機選擇比例為α的節點作為智慧節點，其中0≤α≤1，每次實驗α的增量為0.05.

4.3 實驗結果與分析

在這一節中，本文提出的真假信息傳播能力評估的動態規劃算法DPA和文獻[22]中的基于蒙特卡羅仿真的方法進行了比較.在復現蒙特卡羅仿真實驗中，我們對比了不同實驗次數的結果平均值，發現大于10000次后，結果的平均值變化不再明顯.相應地，對于相同參數配置的實驗進行10000次，并取其平均值作為蒙特卡羅仿真的實驗結果.

圖2 在不同的網絡下仿真結果與動態規劃結果的比較Fig.2 Results of comparison between simulation and dynamic programming on different synthetic networks

實驗結果如圖2所示，其中點數據代表仿真結果，線數據代表估計方法得到的結果.從趨勢來看，基于動態規劃的方法結果走勢與仿真方法完全一致.隨著智慧節點比例的增加，真信息傳播的范圍變得更廣，假信息則能夠被迅速抑制.ER網絡中，TTA、FTA的估計結果及兩者之間的差異分別如圖2(a)、圖2(d)所示.可見，增加平均度k可以顯著地促進信息的級聯過程.當m=1時，真、假信息兩種情況下的傳播范圍都處于非常低的水平.圖2(b)、圖2(e)分別展示了在BA網絡中不同m值的對TTA、FTA的影響以及兩者之間的差異，結構參數m決定了BA網絡的平均度值.當選擇鏈狀結構中的一個節點作為智慧節點時，由于該節點有兩條可傳播路徑，其中作為智慧節點的效果會減弱.類似地，高度連通的網絡結構，如k≥6的ER網絡和m≥3的BA網絡，會導致更高的信息傳播速度，并獲得更高的FT和FF值.WS網絡具有小世界屬性，即平均路徑較短，且聚類系數較高.如圖2(c)、圖2(f)所示，當β=0.01時，假信息的傳播被抑制.

從具體數值來看，DPA與仿真結果存在的差距不大，能夠很好的復現仿真實驗的結果.在真信息的傳播中，信息大多能夠通過網絡中的連邊關系傳播下去.DPA通過最短路徑的概率傳播模擬了真實的傳播路徑，這樣使得該方法的FTA略高于仿真結果.在假信息的傳播中，由于智慧節點的存在，DPA只考慮少數最短路徑的傳播，信息的傳播很容易被抑制，相比之下，真實的傳播路徑更多更遠.所以，在假信息的傳播計算中，本文提出的方法TTA結果會略低于仿真值.但在絕大多數情況下，兩種方法結果的近似一致.也就是說，本文提出的方法可以用來分析真、假信息在不同網絡下的傳播影響.基于動態規劃的近似估計方法為我們找到具有最佳信息過濾能力的網絡結構提供了方便.

4.4 運行時間效率分析

本文的實驗環境為Intel(R)Corei7-8700K3.7GHzCPU和32GBRAM.動態規劃算法中真、假信息傳播在不同拓撲網絡上的收斂代數如圖3所示.基于動態規劃的方法中實驗收斂的速度與網絡的平均路徑相關.結果顯示絕大多數實驗能夠在10代以內快速收斂.在k=3的ER網絡和m=1的BA網絡中，由于節點間的平均路徑長度較長，這部分真信息的傳播實驗在30代左右收斂.

圖3 真假信息傳播在不同拓撲網絡上的收斂代數Fig.3 Convergence algebra of true and false message propagation on different topological networks

圖4 仿真方法與估計方法的時間對比Fig.4 Time consumption of simulation method and estimation method

在實驗的運行時間分析中，如圖4所示，實驗的運行時間隨著網絡連邊數的增加而增加.本文提出的基于動態規劃的評估方法DPA的時間消耗遠低于基于蒙特卡羅仿真方法.在對本文提出的方法進行算法時間復雜度分析中，計算真信息概率矩陣PT與假信息概率矩陣PF的時間復雜度相同.每次迭代中，需要根據算法1中的公式更新所有節點的轉發概率.因此，傳播概率計算的復雜度為k·|v|.該方法的時間復雜度取決于網絡中的節點的平均度值和總節點數.

5 結 語

本文針對真假信息傳播模型提出了一種基于動態規劃的真假信息傳播能力評估的計算方法，該方法包括尋找最短路徑和計算傳播概率兩個步驟.經過大量的實驗表明，本文提出的方法能夠很好的用來分析不同網絡的信息傳播能力及影響，解決了傳統基于蒙特卡羅方法實驗重復次數不確定和時間效率低的問題.如今社會中虛假信息的問題愈發嚴重，該研究為控制輿論傳播和構建智慧社會以及分析最優的網絡結構提供了新的思路和方法.在未來的工作中，我們將在本文提出的方法基礎上研究如何優化現有的傳播網絡結構，使得最優的網絡在相同條件下，更能抑制虛假消息的傳播；通過刪除一定數量的連邊，使得一個網絡中虛假消息傳播的比例下降最多，從而達到控制輿情的擴散；以及研究智慧節點布置策略，使得真消息傳播最大化，同時虛假信息傳播最小化.