基于有責量和免責量的謠言溯源算法

葉增煒，王友國，柴 允

(1.南京郵電大學 理學院，江蘇 南京 210023；2.南京郵電大學 通信與信息工程學院，江蘇 南京 210003)

0 引 言

隨著通信和互聯網技術的不斷發展，人與人之間的聯系愈加頻繁和緊密，社交網絡也成為人類生活中重要組成的一部分。在社交網絡大環境影響下，信息的傳播速度、擴散規模和影響力都顯著增加，一方面給予人們極大的便利，另一方面，謠言等不良信息在社交網絡上的肆意傳播，也對社會造成嚴重的危害，從而影響社會穩定。因此結合相應的社交網絡信息傳播模型，對不同場景下的謠言溯源問題進行挖掘和定位，進而確定謠言源位置和謠言傳播的關鍵信息，及時有效地遏制謠言發展顯得尤其重要。

目前，關于謠言溯源問題，通常是通過觀察整個感染子圖，在獲得某些信息的前提下，如網絡拓撲及節點狀態信息等，構建源節點估計量，最大化謠言源檢測概率。Shah和Zaman首次通過構建謠言源的極大似然估計量(謠言中心性)研究網絡上的單源溯源問題，并以此為基礎，假定按照廣度優先搜索的傳播機制，將謠言中心性推廣到一般樹和一般圖上。同時Shah和Zaman證明了在樹形網絡中謠言中心性和距離中心性完全等效，在幾何樹中，隨著傳播時間增長，正確檢測概率趨于1。Zhu等人基于采樣路徑，定義感染離心率為一個節點到所有感染節點最短路徑的最大值，提出Jordan中心估計量，即具備最小的感染離心率節點，用以解決SIR傳播模型下的謠言溯源問題。Luo等人在有限觀察的前提下，提出一種反向貪婪算法迅速尋找到網絡中的Jordan中心，即單Jordan中心估計算法(SJC)。Ali等人認為在沒有任何先驗知識的情況下，可以假設每個節點成為源的概率相等，因此實際的謠言源節點可能不是Jordan中心，并通過考慮鄰居節點的狀態計算出節點年齡從而估計可能的謠言源節點。也有研究者通過在網絡中設置傳感器節點，收集節點感染狀態和感染時間信息，從而探尋可能的謠言源節點。例如，Pinto等人通過傳感器節點所收集到的節點實際時延信息，對比信息到達的理論時延，計算時間矩陣的相似度進行信源估計。Spinelli等人在信息傳播過程中設置動態傳感器，可以在信息傳播結束或仍在傳播的時候定位到信源節點，并通過實驗分析出使用動態傳感器將大幅減少傳感器節點數量，即使具有高方差傳輸延遲，也可以使用少量傳感節點有效地進行溯源工作。

在真實網絡中，謠言源往往不唯一，為此，Luo等人提出多Jordan中心估計算法(MJC)，用于解決SI傳播模型中節點顯式狀態和隱式狀態的多源溯源問題，使用Voronoi劃分算法將所有顯式狀態節點劃分成多個社區，并使用SJC算法估計各自的謠言源節點。Fioriti等人考慮網絡鄰接矩陣最大特征值在移除每個節點后的下降量，定義了動態年齡的概念，并視動態年齡值排名靠前的節點為源節點。Ali等人基于K-Means劃分方法和連續源識別方法將單源估計算法推廣至多源情況。Prakash等人針對多源問題提出基于最小描述長度的NetSleuth算法，該算法是自適應的謠言溯源算法，無須事先已知謠言源數。

在已有研究的基礎上，該文考慮基于有責量和免責量的謠言源溯源算法，通過可疑集選取的思想，采用譜優化的模塊度劃分算法，將雙源感染網絡劃分為兩個社區，在各個社區內進行單源溯源工作，從而解決雙源溯源問題。最后，在多個網絡拓撲結構中進行了仿真實驗，對比不同溯源算法的性能。

1 基于有責量和免責量的謠言溯源算法

1.1 謠言傳播模型

信息擴散網絡可以模擬為一個無向圖

G

={

V

,

E

}，其中

V

代表可數點集，

E

代表可數邊集，在異構SI傳播模型中，網絡中的節點狀態包括：易感態

S

和感染態

I

(見圖1)，一旦一個節點由于從其被感染的鄰居節點處接收到感染或者僅僅是作為感染源而被感染，則它將永遠處于感染態。感染節點以概率

p

感染其易感鄰居，概率

p

取決于相鄰節點之間的關系強度，即邊的權重

w

(

e

)，

e

∈

E

。

圖1 異構SI傳播模型狀態轉移圖

1.2 節點年齡

在信息擴散網絡中，使用節點年齡來衡量節點加入感染網絡的先后程度，其中最早被感染的節點擁有最大的年齡。如圖2所示，當網絡發生擴散時，1號節點作為最早感染的節點，在擴散過程中，感染了2號和3號節點，此外4號節點被2號節點感染，那么在這個感染網絡中，1號節點擁有最大的年齡。

圖2 節點年齡示意圖

1.3 免責量

圖3 免責量

1.4 有責量

(1)

其中，

l

是距離節點

u

的距離，

P

(

u

)是距離

u

節點

l

跳的所有節點的有責量之和。同時，容易得到在估計源節點時，必須計算直至距離節點比網絡半徑少一個層級的有責量，即

k

最佳的取值為

r

-1，

r

是網絡的半徑。

1.5 源估計量

(2)

(3)

其中，

I

和

O

分別是

v

節點對應感染圖和底層圖的度。

圖4 水平有責量

由上文易得，當BFS遍歷到達網絡半徑時停止，即生成屬于

r

水平的用以計算免責量節點和屬于

r

-1水平的用以計算有責量節點。因此，節點

u

的年齡可由0至

r

-1水平的水平有責量之和計算得出，用公式表示為：

(4)

(5)

(6)

(7)

該文所陳述的謠言溯源方法可由以下算法實現。

算法1：基于免責量和有責量的謠言溯源算法(EPA_B)

底層圖

G

度矩陣

D

D

對應于

D

的子陣

D

=

D

[rownames(

D

),colnames(

D

)]

d

←

D

的對角線元素

d

←

D

的對角線元素level←0，

U

←

u

}

算法2：節點年齡估計算法。

if level>radius-1{

return(0)

}

for

u

∈

U

{lage←lage+

P

(

u

)

}

OUTPUT：節點年齡

A

2 基于譜優化社區劃分的雙源溯源算法

考慮到真實網絡謠言傳播過程中謠言源不唯一，針對雙源情況，考慮基于譜優化社區劃分算法將雙源問題轉化為單源問題，主要內容將在以下部分進行說明。

2.1 基于譜優化社區劃分的雙源溯源算法

在真實網絡中，普遍存在社區結構特性，即同組內的節點相似性較大，異組間的節點相似性較小。其中，Newman提出用以度量網絡社區劃分優劣的模塊度概念，并結合譜分析法優化社區劃分算法。譜分析法是利用拉普拉斯矩陣的特征向量將連接緊密的節點劃分到一個社區。對比傳統社區劃分算法，譜分析法不易陷入局部最優解。

(8)

同時，定義

s

是一個含有

n

個元素的索引向量，有：

(9)

那么模塊度

Q

改寫成矩陣形式如下:

(10)

B

=

A

-

P

(11)

(12)

(13)

綜上，該文得到通過計算模塊化矩陣的主特征向量以獲得最優

s

，從而根據

s

值的正負情況劃分兩個社區的基于譜分析的模塊度社區劃分算法。

2.2 算法展示

算法3：基于社區劃分的雙源溯源算法(EPA_DC)。

DO:初始化空集newcenters

if主特征向量

u

≥0{

part[1]←node

}

else{

part[2]←node

}

}

for

pa

in part{for

u

∈

pa

{

}

}

return newcenters

3 仿真與分析

3.1 數據集

該文在7種不同網絡拓撲結構下分別驗證單源和雙源算法的性能，包括2種合成網絡：ER隨機網絡(ER)、4-正則樹網絡(Regular)和5種真實網絡：Facebook社交網絡(Facebook)、美國電網(USPG)、爵士音樂人合作網絡(Jazz)、美國空手道俱樂部網絡(Karate)、《悲慘世界》主要人物關系網絡(Lesmis)。它們的相關數據在表1中給出。

表1 不同網絡拓撲結構的統計性質

3.2 仿真實驗設置

通過分析不同估計量在上文所提及的7種不同網絡拓撲結構下的誤差距離信息和正確檢測概率來評估文中算法的檢測性能和優劣。誤差距離為估計謠言源與真實源節點之間的最小路徑距離，正確檢測概率是實驗中正確識別謠言源的比例。在單源仿真實驗中，分別在ER、Regular、Facebook、USPG網絡上隨機選擇一個節點作為謠言源，并以異構SI傳播模型進行傳播，每個網絡的感染節點比例設置在2%～5%之間。在雙源仿真實驗中，分別在Jazz、Karate、Lesmis網絡上隨機選取兩個節點作為謠言源，同時以異構SI傳播模型進行傳播，考慮到每個網絡的規模情況，它們的感染節點比例設置在60%～70%之間。為減少隨機誤差的影響，所有仿真實驗均獨立進行了100次并取均值。文中實驗過程在R 4.0.3環境中進行。

3.3 單源仿真結果

本部分主要分析單源溯源仿真實驗結果，通過該文提出的基于有責量和免責量的謠言溯源算法(EPA_B)與基于動態年齡(DA)、最小描述長度(MDL)兩種常用的謠言源估計算法進行比較分析，同時加入采取度較大節點作為可疑集的EPA_D算法進行對比，來評價各算法性能的優劣。仿真結果如圖5、圖6所示。

圖5顯示了不同算法在4種網絡拓撲結構下的誤差距離頻率，結果表明，在合成網絡中，基于有責量和免責量的謠言溯源算法表現都相當不錯。如圖5(a)所示，在ER網絡上，EPA_B有97%的頻率完全正確地找到源節點或誤差距離僅僅1跳，大幅度領先于其他算法。圖5(b)顯示，在Regular網絡上，除了MDL算法之外，其余3個算法表現相差不大，EPA_B與EPA_D算法略優于DA算法，同時EPA_B算法的誤差距離均在3跳之內，而EPA_D算法存在超過3跳的誤差距離。在Facebook網絡上，各算法的表現也可由圖5(c)中看出，EPA_D和DA算法的表現比較亮眼，但EPA_B算法也有81%的頻率在1跳之內找到源節點。由圖5(d)可知，在USPG網絡上，由于USPG網絡的高度稀疏性，各個算法都很難精確地找到源節點。

圖5 不同網絡和算法下的誤差距離

圖6顯示了不同算法在4種網絡拓撲結構下的平均誤差距離，可以直觀地觀察到EPA_B算法相較于其他算法的表現。在ER網絡中，EPA_B算法的平均誤差距離僅為0.26，表現最好。在Regular和Facebook網絡上，EPA_B算法的平均誤差距離在1跳附近，與EPA_D和DA算法相差不大。總體而言，在給定的幾個網絡中，EPA_B算法表現較為優異且穩定。

圖6 算法在不同網絡中的平均誤差距離

3.4 雙源仿真結果

本部分主要分析雙源溯源仿真實驗結果，經過譜優化社區劃分算法的感染子圖分別使用基于有責量和免責量的謠言溯源算法(EPA_CD)、基于接近中心性的溯源算法(CC)和基于距離中心性的溯源算法(DC)進行仿真實驗，同時加入基于K-Means感染網絡劃分的雙源估計算法(EPA_K-Means)進行對比分析。

由圖7(a)可知，在不同網絡拓撲結構中，EPA_CD算法的平均誤差距離均為最小且都在1跳之內，EPA_K-Means算法的平均誤差距離在1跳左右，而CC和DC算法表現稍差一些。由于Karate網絡的規模最小，因此每個算法在Karate網絡中表現都是最好的。由圖7(b)可知，就正確檢測概率而言，EPA_CD和EPA_K-Means算法結果相差不大，且大幅優于CC和DC算法，在Jazz和Karate網絡中，EPA_CD算法的正確檢測概率略好于EPA_K-Means算法，在Lesmis網絡中則相反，EPA_K-Means算法的結果為0.27，而EPA_CD算法的結果為0.225。

圖7 平均誤差距離和正確檢測概率結果

4 結束語

該文利用謠言源是最早加入感染網絡的節點這一思想，通過考慮感染節點的鄰居節點狀態，得到基于有責量和免責量的謠言溯源算法，并為了減少算法計算成本，采用高介數中心性節點作為源節點可疑集的思想，提出EPA_B算法。同時，針對雙源問題，基于譜優化的社區劃分算法，將雙源感染子圖劃分為兩個社區，從而將復雜的雙源問題簡化為單源問題。最后，分別在不同網絡拓撲結構內進行單源和雙源溯源的仿真實驗，結果表明，單源問題中，在多數網絡拓撲結構下，EPA_B算法的平均誤差距離在1跳左右，在ER網絡中甚至能達到0.26，在高度稀疏性網絡中表現也最為穩定。針對雙源問題，提出的EPA_CD算法在3個小規模真實網絡中的平均誤差距離均為最小，在Karate網絡中，EPA_CD算法的正確檢測概率高達0.595，相較于其他啟發式謠言源估計算法，表現更為優異。