基于有責(zé)量和免責(zé)量的謠言溯源算法

葉增煒，王友國，柴 允

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

0 引 言

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

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

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

在已有研究的基礎(chǔ)上，該文考慮基于有責(zé)量和免責(zé)量的謠言源溯源算法，通過可疑集選取的思想，采用譜優(yōu)化的模塊度劃分算法，將雙源感染網(wǎng)絡(luò)劃分為兩個社區(qū)，在各個社區(qū)內(nèi)進(jìn)行單源溯源工作，從而解決雙源溯源問題。最后，在多個網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中進(jìn)行了仿真實驗，對比不同溯源算法的性能。

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

1.1 謠言傳播模型

信息擴散網(wǎng)絡(luò)可以模擬為一個無向圖

G

={

V

,

E

}，其中

V

代表可數(shù)點集，

E

代表可數(shù)邊集，在異構(gòu)SI傳播模型中，網(wǎng)絡(luò)中的節(jié)點狀態(tài)包括：易感態(tài)

S

和感染態(tài)

I

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

p

感染其易感鄰居，概率

p

取決于相鄰節(jié)點之間的關(guān)系強度，即邊的權(quán)重

w

(

e

)，

e

∈

E

。

圖1 異構(gòu)SI傳播模型狀態(tài)轉(zhuǎn)移圖

1.2 節(jié)點年齡

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

圖2 節(jié)點年齡示意圖

1.3 免責(zé)量

圖3 免責(zé)量

1.4 有責(zé)量

(1)

其中，

l

是距離節(jié)點

u

的距離，

P

(

u

)是距離

u

節(jié)點

l

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

k

最佳的取值為

r

-1，

r

是網(wǎng)絡(luò)的半徑。

1.5 源估計量

(2)

(3)

其中，

I

和

O

分別是

v

節(jié)點對應(yīng)感染圖和底層圖的度。

圖4 水平有責(zé)量

由上文易得，當(dāng)BFS遍歷到達(dá)網(wǎng)絡(luò)半徑時停止，即生成屬于

r

水平的用以計算免責(zé)量節(jié)點和屬于

r

-1水平的用以計算有責(zé)量節(jié)點。因此，節(jié)點

u

的年齡可由0至

r

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

(4)

(5)

(6)

(7)

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

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

底層圖

G

度矩陣

D

D

對應(yīng)于

D

的子陣

D

=

D

[rownames(

D

),colnames(

D

)]

d

←

D

的對角線元素

d

←

D

的對角線元素level←0，

U

←

u

}

算法2：節(jié)點年齡估計算法。

if level>radius-1{

return(0)

}

for

u

∈

U

{lage←lage+

P

(

u

)

}

OUTPUT：節(jié)點年齡

A

2 基于譜優(yōu)化社區(qū)劃分的雙源溯源算法

考慮到真實網(wǎng)絡(luò)謠言傳播過程中謠言源不唯一，針對雙源情況，考慮基于譜優(yōu)化社區(qū)劃分算法將雙源問題轉(zhuǎn)化為單源問題，主要內(nèi)容將在以下部分進(jìn)行說明。

2.1 基于譜優(yōu)化社區(qū)劃分的雙源溯源算法

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

(8)

同時，定義

s

是一個含有

n

個元素的索引向量，有：

(9)

那么模塊度

Q

改寫成矩陣形式如下:

(10)

B

=

A

-

P

(11)

(12)

(13)

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

s

，從而根據(jù)

s

值的正負(fù)情況劃分兩個社區(qū)的基于譜分析的模塊度社區(qū)劃分算法。

2.2 算法展示

算法3：基于社區(qū)劃分的雙源溯源算法(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 數(shù)據(jù)集

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

表1 不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的統(tǒng)計性質(zhì)

3.2 仿真實驗設(shè)置

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

3.3 單源仿真結(jié)果

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

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

圖5 不同網(wǎng)絡(luò)和算法下的誤差距離

圖6顯示了不同算法在4種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下的平均誤差距離，可以直觀地觀察到EPA_B算法相較于其他算法的表現(xiàn)。在ER網(wǎng)絡(luò)中，EPA_B算法的平均誤差距離僅為0.26，表現(xiàn)最好。在Regular和Facebook網(wǎng)絡(luò)上，EPA_B算法的平均誤差距離在1跳附近，與EPA_D和DA算法相差不大?？傮w而言，在給定的幾個網(wǎng)絡(luò)中，EPA_B算法表現(xiàn)較為優(yōu)異且穩(wěn)定。

圖6 算法在不同網(wǎng)絡(luò)中的平均誤差距離

3.4 雙源仿真結(jié)果

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

由圖7(a)可知，在不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中，EPA_CD算法的平均誤差距離均為最小且都在1跳之內(nèi)，EPA_K-Means算法的平均誤差距離在1跳左右，而CC和DC算法表現(xiàn)稍差一些。由于Karate網(wǎng)絡(luò)的規(guī)模最小，因此每個算法在Karate網(wǎng)絡(luò)中表現(xiàn)都是最好的。由圖7(b)可知，就正確檢測概率而言，EPA_CD和EPA_K-Means算法結(jié)果相差不大，且大幅優(yōu)于CC和DC算法，在Jazz和Karate網(wǎng)絡(luò)中，EPA_CD算法的正確檢測概率略好于EPA_K-Means算法，在Lesmis網(wǎng)絡(luò)中則相反，EPA_K-Means算法的結(jié)果為0.27，而EPA_CD算法的結(jié)果為0.225。

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

4 結(jié)束語

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

謠言大揭秘

學(xué)生天地(2016年32期)2016-04-16 05:16:19

雙源信號深組合導(dǎo)航在新一代運載火箭制導(dǎo)系統(tǒng)中應(yīng)用初探

導(dǎo)航定位學(xué)報(2015年2期)2015-06-05 09:27:38