基于深度學習節點表示的謠言源定位方法*

劉 維,楊 潔,羅佳莉,王賽威,陳 崚

(揚州大學信息工程學院,江蘇 揚州 225000)

1 引言

近年來,社交媒體的普及使得謠言迅速傳播,這對社會穩定和政府公信力構成了一定的威脅。虛假信息混入公共事件,不僅可能引起公眾的恐慌,還可能給公眾帶來傷害[1]。此外,虛假新聞也可能會損害企業和個人的聲譽。謠言會誤導人們的思想,導致他們對某些問題產生誤解進而做出錯誤的決定。以全球抗擊COVID-19疫情為例,一些人故意散布飲用烈酒可以殺死病毒的謠言。有人相信了這一謠言,開始大量飲酒而未采取科學的預防措施。這樣的謠言不僅妨礙了疫情防控工作的開展,還對國家的經濟發展產生了不利的影響。

為了控制謠言的傳播范圍,定位謠言源至關重要。在實際應用中,我們雖然不知道謠言的具體來源,但是可以通過找到一些受到謠言影響的觀測節點并根據觀測節點的信息來定位謠言源。Shah等人[2]首次提出了謠言源定位問題。他們把這一問題定義為:給出一組受謠言影響的觀測節點O和其被影響的時間T,謠言源定位的目的是識別一個由k個謠言源組成的節點集S,使其影響范圍I(S)能夠最大限度地覆蓋O中的觀測節點。同時,要保證謠言源到O中觀測節點的距離與它們的影響時間T高度一致。

近年來,很多學者對這個問題進行了研究。有些學者從網絡拓撲結構角度出發,假設謠言源與節點的中心性有關并據此展開了研究。例如,文獻[2-4]利用不同的中心性測量方法定位源節點。然而,由于基于中心性的方法忽略了觀測的節點信息和邊上的傳播概率,這些方法對謠言源的定位效果并不理想。還有一些研究[5,6]將擴散圖構建為生成樹,將生成樹的根作為源節點進行謠言定位。然而,由于樹結構只是原始網絡的一個子圖,基于樹結構的方法并不能準確反映原始網絡中的影響力傳播。此外,所有這些研究都假設網絡中只有一個謠言源,然而現實世界中謠言源往往不止一個,因此許多學者開始將研究重心轉移到多謠言源定位問題上來。

多謠言源定位方法主要可以分為3類:基于社區的多謠言源定位方法、基于傳播路徑的多謠言源定位方法和基于排名的多謠言源定位方法。基于社區的多謠言源定位方法[7,8]首先利用網絡的拓撲信息對網絡進行劃分,然后在每個社區內解決單源識別問題。然而,基于社區的多謠言源定位方法的效果在很大程度上取決于觀測節點的選擇。基于傳播路徑的方法從反向傳播[9]、貝葉斯理論[10]、感染序列[11]和置信集[12]等角度考慮來自每個謠言源節點的復雜感染路徑。然而,這些多謠言源檢測方法大多采用貪婪的策略來尋找謠言源,因此需要多次模擬來估計每個候選源節點集的傳播范圍。由于這2類方法時間復雜度較高,所以并不適用于大規模網絡。基于排名的多謠言源定位方法[10,12]首先估計一些度量值,用這些度量值表示節點作為源的概率,然后根據度量值對節點進行排序,最后選擇度量值最高的節點作為源節點。然而,這些方法認為網絡中的所有節點和邊都是相同的,忽略了信息傳播中觀測到的節點的關鍵潛在拓撲特征。由于節點的關鍵拓撲特征丟失,這些方法謠言源定位的效果往往不夠理想。

為了充分考慮謠言以及擴散過程中各個特征之間的關聯性,減少因路徑分析造成的大量計算,本文提出一種基于深度學習的謠言源定位方法。該方法首先從節點的擴散路徑角度定義所有節點與觀測節點之間的路徑相似度,從節點的傳播時間角度定義節點的影響力向量,從節點之間關系的角度定義節點與其他節點的影響力相似度。其次,本文設計一個包含編碼解碼模塊的自編碼神經網絡對節點的影響力向量進行編碼。需要特別關注的是,在網絡的訓練過程中,本文使用節點的路徑相似度以及節點的影響力相似度對訓練過程加以限制,最終得到包含了擴散路徑、傳播時間和節點信息的新的節點嵌入表示。最后,根據得到的節點嵌入表示計算節點為源的概率,從而實現謠言源的定位。

本文的主要工作如下:

(1) 提出一種基于隨機游走計算節點與觀測節點之間相似度的算法。

(2) 考慮觀測節點的感染時間,提出一種節點表示來度量每個節點與估計源之間的距離。

(3) 結合節點感染時間和節點與觀測節點的相似度,設計節點編碼方法。

(4) 通過整合節點的拓撲特征及其與網絡中觀察節點的距離,提出一種基于深度學習的方法。該方法能有效、準確地識別影響源且能適用于多種傳播模型。

(5) 在4個真實網絡和2個合成網絡上的實驗結果表明,該方法在謠言源定位方面具有優勢,并且可以在更短的時間內獲得比其他方法更高的效率。

2 相關工作

最早的單謠言源定位方法大多關注網絡的拓撲結構,依賴節點的中心性信息定位謠言源。Shah等人[2]首先定義了謠言源定位問題,并提出了“謠言中心性”來定位謠言源。Zhu等人[13]利用節點的“偏心率”,即一個候選源到其可到達的最遠節點的最大距離,來估計網絡中的真實源。Jog等人[14]研究了隨機生長樹中的節點中心性,提出了質量中心的概念并給出了中心性的下限。Kouzy等人[15]提出了一種使用社區結構中橋節點來定位謠言源的方法。然而,這些基于中心性的方法大多使用樹結構來檢測謠言源,將一般的圖改造成生成樹,或者只是在樹和樹狀子圖上估計原始傳播源。由于樹結構只是原始網絡的一個子圖,基于樹狀結構的方法不能準確反映原始網絡中的謠言真實傳播。由于基于中心性的方法的表現很大程度上依賴于源節點在網絡中的位置,只有當謠言源節點相對靠近圖的中心時,這些方法的表現才會比較好。因此,這些方法不能很好地適用于現實情況。

為了縮小謠言源的搜索范圍,許多研究人員試圖利用觀測到的節點信息定位謠言源。基于感染網絡的理論基礎,一些研究人員通過在社交網絡中部署傳感器和觀測者的方式獲得更多關于謠言傳播過程的信息。基于觀測到的節點信息,Hu等人[16]基于反向傳播和整數規劃修改了謠言源定位的最大最小值方法,通過結合節點的傳播延遲和0-1整數規劃來定位謠言源。然而,所提方法僅考慮傳播延遲和擴散時間是不足以準確定位源節點的,因為傳播路徑信息也非常重要。基于傳播路徑分析,Zhu等人[17]將謠言源定位問題轉化為觀測節點的信息排序問題。他們根據受感染節點影響的節點的概率和被感染的成本來定位謠言源。作者沒有具體說明觀測節點的選擇,但是該方法中時間戳的推導完全基于觀測節點,因此如何選擇觀測節點與他們提出的方法高度相關。

在現實世界的社交網絡中,錯誤信息來源于多個謠言源,通過如Twitter、Sina和其他社交網絡等多種不同的渠道進行傳播。模擬不同來源謠言的傳播和從觀測節點記錄的信息中找到這些傳播源是至關重要的。現有的多謠言源定位方法主要分為3類:基于社區劃分的多謠言定位方法、基于傳播路徑的多謠言源定位方法和基于排名的多謠言定位方法。基于社區劃分的方法首先將網絡劃分為多個社區,然后在每個社區中找到傳播源。Nguyen等人[9]通過網絡聚類設計了一種基于獨立級聯模型的啟發式算法,通過反向擴散確定多個候選源節點。然而,該算法僅依靠節點的狀態來檢測謠言源,沒有充分考慮可能的感染信息。基于反向傳播和分而治之的方法,Zang等人[5]提出了基于SIR(Susceptible Infected Recovered)模型的多謠言源定位問題。他們提出了一種社區檢測方法,將恢復的節點劃分到多個感染社區,然后用最大似然法定位每個社區的感染源。然而,作者直接使用了已有的社區檢測算法,沒有根據感染信息劃分社區,因此不能很好地解決謠言源定位問題。Khim等人[18]分析了感染子圖,并使用置信集估計源節點的數量,但是這種方法只適用于常規樹狀網絡。Ding等人[7]提出了一種基于有效距離的網絡劃分方法,將多謠言源定位問題轉化為單謠言源定位問題。然而,他們并沒有研究使用不同的有效距離對謠言源定位問題的影響。Li等人[19]提出了一種基于路徑的多路網絡源定位方法。該方法基于源中心性理論,采用標簽迭代過程尋找局部標簽最大的節點作為源。考慮到感染子圖的結構和謠言傳播的隨機性,Qiu等人[20]提出了一種基于時間戳反向傳播的估計方法定位謠言源。基于排名的多謠言源定位方法首先定義和估計一些代表節點作為謠言源的概率,然后根據這些值對節點進行排名。Zhang等人[10]使用貝葉斯反追蹤模型提出激活原因的后驗概率,并選擇隨機游走命中率高的節點作為謠言源。然而,該方法需要大量的計算,所以不適用于大規模網絡。Dawkins等人[12]定義了多謠言源定位的置信集,根據置信集,他們提出了2種節點抽樣方法來構建候選謠言源集合。

有些方法將單謠言源定位問題轉化為一個分類問題,并使用基于神經網絡的學習方法來識別謠言源。例如,文獻[12,21]分別是基于圖神經網絡GNN(Graph Neural Network)和門循環單元GRU(Gate Recurrent Unit)的單謠言源神經網絡方法。但是,這些方法都只是根據網絡的拓撲信息建立目標函數,忽略了觀測節點被感染的時間信息。觀測節點的受影響時間是謠言源定位的重要信息,因此忽略受影響時間的方法不能滿足特征提取的訓練要求,也不能獲得高精度的結果。

3 預備知識

本節介紹獨立級聯模型,并定義多謠言源定位問題。

3.1 獨立級聯模型

本文對獨立級聯IC(Independent Cascade)傳播模型下的多個謠言源定位問題進行研究。獨立級聯模型是社交網絡中常用的信息傳播模型之一。在這個模型下,信息傳播過程中任意時刻每個節點都處于2種狀態之一:激活狀態或未激活狀態。初始狀態下,所有的源節點都是激活狀態,其它節點處于未激活狀態。傳播開始時,源節點嘗試去激活它的鄰居節點,如果鄰居節點被激活,那么被激活的節點會在下一個時刻繼續激活它的鄰居節點。節點是否能激活鄰居節點,與其它節點的激活結果無關。此外,該模型假設每個被激活的節點有且僅有一次機會激活其鄰居節點。無論成功與否,都不會再有機會激活其鄰居節點。當沒有新的節點可以被激活時,信息傳播過程就結束了。源節點的影響范圍就是最終受影響的節點集合。

Figure 1 Framework of the proposed method圖1 本文所提方法框架

3.2 多謠言源定位問題

社交網絡可以用圖G=(V,E,P)的形式描述,其中,V表示節點集合,|V|=N,E表示邊集,P=[pu,v]表示邊的權重矩陣。對于每一條邊(u,v)∈E,pu,v∈(0,1)是節點u到它的鄰居節點v的傳播概率。O={o1,…,om,…,oM}表示隨機從節點集合V中選取的觀測節點集合,M<|V|。T={t1,…,tm,…,tM}表示觀測節點被影響的時間集合。

定義1(謠言源的影響范圍) 設社交網絡為G=(V,E,P),S?V為謠言源在IC模型下從t=0時刻開始傳播影響的所有節點集合。各個謠言源之間的傳播是相互獨立的,在足夠長的時間T后傳播終止。謠言源的影響范圍I(S)表示被源節點集合S在時間T后激活的節點集合。

在現實世界中,觀測節點集合O的選擇必須滿足以下條件:對于任意2個節點v1和v2,至少存在O中的一個節點o使得該節點分別到v1和v2的距離不相同。基于上述條件,本文選擇一個雙重可分解集[22]作為觀測節點集。

3.3 方法框架

圖1描述了本文在IC模型下定位多個謠言源方法的框架。本文所提方法首先根據觀測節點被影響的時間和節點與觀測節點之間的距離定義節點的影響力向量。然后,設計一個自動編碼AE(Auto Encoder)神經網絡對節點的影響力向量進行編碼。在模型訓練的過程中,加入路徑信息和節點信息對模型進行約束。通過神經網絡的訓練得到包含了謠言擴散路徑、傳播時間和節點信息的節點嵌入表示。最后,通過節點的嵌入表示計算節點為謠言源的概率并選擇概率最高的節點為源節點,實現謠言源的定位。

4 基于深度學習的節點表示

本節提出一個自動編碼器(AE)網絡,它將節點嵌入到一個反映謠言的擴散路徑、傳播時間和節點的鄰居信息的潛在空間。首先,提出一種基于隨機游走的路徑分析算法,根據每一個節點與觀測節點的可能路徑,從節點與觀測節點的受影響狀態獲得節點表征。然后,將節點表征輸入AE網絡,得到每個節點的嵌入表示輸出。該嵌入表示反映了節點在潛在空間中的擴散路徑、傳播時間和節點信息。

4.1 基于隨機游走的路徑分析算法

假設在t1=0,q(R≥q≥1)時刻謠言源開始傳播謠言,其中R為謠言傳播時間上限。在傳播過程中,一些隨機選擇的觀測節點會記錄下它們被影響的時間T。

為了估計謠言源節點對被觀測節點的傳播范圍,本文定義隨機可達路徑,以確定影響觀測節點的候選源節點。在現實生活中,謠言的傳播沒有閉環,而且長度小于Q,定義H(H≤Q)為傳播路徑長度的最大值。

定義5(路徑相似性) 假設從觀測節點om開始有K條隨機可達路徑,則觀測節點om與節點v之間的路徑相似性可定義為式(1)所示:

(1)

上述路徑相似性反映了這2個節點被同一個謠言源影響的可能性。連接它們的隨機可達路徑越多,它們的路徑相似度越高。因此,路徑相似性αm,v反映了謠言在傳播過程中傳播路徑的屬性。

(2)

(3)

定義7(影響力相似度) 根據影響力向量的定義,2個節點u和v的相似性定義為式(4)所示:

(4)

(5)

節點u和節點v到同一觀測節點的隨機可達路徑越多,它們的相似度就越高。也就是說,節點之間的影響力相似度ru,v越高,說明它們在潛在空間的距離應該更近。因此,節點之間的影響力相似度反映了節點的信息。

Figure 2 Structure of auto-encoder network圖2 自編碼神經網絡結構

設|V|=N,算法1的時間復雜度為O(M×K×H)。由于M和K為常數且H≤N,所以算法1的時間復雜度為O(N)。

算法1 RW-Path-Analysis算法輸入:G':G=(V,E,P)的逆向圖;H:隨機游走路徑的最大長度;K:采樣次數;O:觀測節點集合。輸出:l:所有隨機游走路徑集合,對于觀測節點om,lm={l(m)1,l(m)2,…,l(m)j,…,l(m)K},其中l(m)j是從om開始的第j條隨機游走路徑;Cm:觀測節點om的候選源節點集合;d(m)v,j:om和v的隨機可達路徑l(m)j長度;αm,v:om和v的路徑相似度。1.BEGIN2. FOR m∈[1,M]DO3. FORj∈[1,K]DO4. u←om;l(m)j={om};d(m)v,j=+∞;5. FORh∈[1,H]DO6. 根據概率pw,u選擇G'中節點u的一個鄰居節點w;7. lmj=lmj∪{w}; Cm∪{w};8. d(m)v,j=h;αm,w=αm,w+1K;9. u←w;10. END11. END12. END13. RETURNl,C,d=d(m)v,j M×N, A=αm,v M×N14.END

4.2 自編碼神經網絡

本文提出一個自編碼(AE)網絡,該網絡將節點的影響力向量作為輸入,以節點與觀測節點之間的路徑相似度和節點之間的影響力相似度作為約束,訓練得到包含節點信息、傳播路徑信息和傳播時間的節點嵌入表示。

4.3 激活函數

(6)

其中,w(m)1和b(m)1表示權重和偏差,σ(·)表示激活函數。本文使用tanh作為激活函數,如式(7)所示:

(7)

那么第l′層輸出的節點v與觀測節點om有關的中間嵌入向量如式(8)所示:

(8)

(9)

(10)

(11)

(12)

(13)

(14)

4.4 損失函數

(15)

其次,本文使用損失Lossα保證節點嵌入zv保留了節點v與其它節點之間的傳播路徑信息,Lossα的計算如式(16)所示:

(16)

其中,αu,v為節點u與節點v之間的路徑相似度。Lossx的加入使得路徑相似度接近的節點嵌入在潛在空間的距離更近,這就保證了在訓練過程中節點嵌入zv很好地保留了謠言源定位需要的傳播路徑信息。

此外,本文使用損失Lossr保證節點嵌入zv保留了節點v與其他節點之間的信息,如式(17)所示:

(17)

其中,ru,v為節點u與節點v之間的節點相似度。損失Lossr的加入保證了神經網絡訓練時保留了節點信息,也就是說相似的節點在潛在空間的嵌入更接近。

定義正則化項Lossreg如式(18)所示:

(18)

基于上述損失項,定義自編碼網絡的損失函數如式(19)所示:

Loss=Lossx+αLossα+βLossr+γLossreg

(19)

該損失函數保證了自編碼網絡將節點向量映射到了一個包含傳播路徑、傳播時間和節點信息的潛在空間。

4.5 自編碼網絡的訓練

為了訓練自編碼網絡,本文采用隨機梯度下降SGD(Stochastic Gradient Descent)法最小化式(19)定義的損失。

Lossα=2tr(ZTL(α)Z)

(20)

Lossr=2tr(ZTL(r)Z)

(21)

其中,tr(·)是矩陣的跡,Z是節點的嵌入向量。

為了訓練自編碼網絡,本文使用隨機梯度下降法通過更新每一個參數θ最小化損失函數,如式(22)所示:

(22)

(23)

(24)

(25)

(26)

通過隨機梯度下降法,式(22)以反向傳播的方式更新參數,使損失函數最小。這個嵌入計算和參數更新的過程不斷重復,直到收斂。訓練AE網絡的算法如算法2所示。

算法2 訓練自編碼網絡輸入:節點v與觀測節點之間的影響力向量x(1)v,…,x(M)v;A:路徑相似度矩陣;O:觀測節點集合;α,β,γ,ε:參數;e:迭代次數。輸出:節點v的影響力向量zv。1.BEGIN2. initialize w,b,^w,^b3. WHILE the difference of the loss values between two consecutive iterations is less than εDO4. Compute the embedding zv and restored vector ^x(m)v according to Eq. (6) through Eq. (14);5. ComputeLoss according to Eq. (19);6. Updatew,b,^w,^b according to Eq. (22) through Eq. (26) using SGD;7. END8. RETURNzv9.END

5 基于深度學習的謠言源定位

5.1 基于隨機游走的路徑分析方法

本文通過自編碼網絡得到了節點的嵌入zv,那么每個節點v為觀測節點om的謠言源的概率如式(27)所示:

(27)

而節點v是觀測節點集合O中的謠言源的概率可以通過式(28)計算:

(28)

本文選擇概率P(O|v)最高的節點為謠言源。基于深度學習的謠言源定位方法DL-SIA的偽代碼如算法3所示。

算法3 基于深度學習的謠言源定位方法(DL-SIA)輸入:G=(V,E,P):社交網絡;k:謠言源的數量;O:觀測節點集合;T:觀測節點的感染時間。輸出:S*={S*1,S*2,…,S*k}:謠言源節點集合。1.BEGIN2. RW-Path-Analysis;/*get Cm and A by Algorithm 1*/3. Compute the influence vector x(m)v by Eq. (2) and Eq.(3);4. Compute the influence similarity matrix R=[ru,v] by Eq. (4);5. Train the AE network and output the embedding z by calling Algorithm 2;6. Estimate the likelihood P(O|v) of all the nodes ac-cording to Eq. (28);7. Choose the k nodes with the maximal likelihoods as the sources S*={S*1,S*2,…,S*k};8. RETURN S*9.END

5.2 復雜度分析

設N為邊集V中的節點數,K為隨機可達路徑數,H為隨機可達路徑長度。計算路徑相似度的時間復雜度為O(H×K×N)。由于計算影響力向量需要遍歷所有的觀測者和節點,其計算復雜度為O(M×N),其中M為觀測到的節點數。在AE網絡中,編碼器和解碼器部分的層數都是L。因此,DL-SIA的總復雜度為O(N·(H×K+M+(2L+1)·H))。在最壞的情況下,所有被感染的節點都被選為觀測者,即M=N。因為K、L和H都可以被視為常數,因此DL-SIA的時間復雜度為O(2N2)。

6 實驗設計

6.1 數據集

在2個虛擬網絡BA和WS,4個真實網絡Email-Eu-core[23],ego-Facebook[24]USpowergrid[25]和wiki-vote[26]上評估了本文方法。

表1列出了6個網絡的拓撲結構屬性。其中,網絡直徑指的是網絡中最長最短路徑的長度。平均聚類系數用于衡量節點與其鄰居節點之間聯系的緊密程度。網絡的平均路徑長度NL定義為任意2個節點vi和vj之間距離dij的平均值,如式(29)所示:

(29)

其中,N為節點數。

表2列出了DL-SIA方法在不同網絡上的神經網絡參數設置。

Table 1 Topological features of the networks表1 不同網絡的拓撲結構

Table 2 Default settings of neural networks in different datasets表2 不同網絡集上的神經網絡設置

6.2 對比方法

為了驗證提出的DL-SIA方法的有效性,本文將其與多種方法進行對比。對于單謠言源檢測問題,本文將DL-SIA與謠言中心性RC(Rumour Centrality)[2]、約旦中心性JC(Jordan Centrality)[13]、EPA(Exoneration and Prominence based Age)方法[27]和DMP(Dynamic Message Passing)方法[28]進行比較。對于多謠言源檢測問題,本文將DL-SIA與NETSLEUTH[29]和K-Center[30]方法進行對比。

6.3 評估指標

本文采用平均錯誤距離AED(Average Error Distance)和準確率(Precision)2個評價指標來衡量謠言源定位方法的有效性。

(1)平均錯誤距離。

(30)

(2)準確率。

(31)

準確率越高說明方法的效果越好。

7 結果

7.1 參數對DL-SIA方法的影響

本文在不同的參數設置下分別做了實驗。α、β和γ為控制損失函數中各個項之間重要性的3個參數。τ為控制觀測節點om的感染時間與其它節點之間距離差異的參數,per為觀測節點的數量在所有節點數量中的占比。

7.1.1α、β和γ對實驗結果的影響

本文測試控制損失函數的3個參數α、β和γ對實驗結果的影響。圖3展示了不同參數對損失函數值的影響。從圖3可以看出,對于不同的網絡,節點v和被觀測節點om的表示與Loss中的Lossα并不是強關聯的。圖3的等高線色譜圖證明了這一結論。從圖3中可以看出,α和β的取值對神經網絡的損失影響不大。此外,從三維圖中可以看出,α的值應在0.5～0.6,以獲得快速收斂。

Figure 3 Effect of α and β on loss function圖3 損失函數中α、β的影響

與損失函數對參數α的不敏感相比,損失函數對β的值更為敏感,該值代表了節點和觀測節點之間相互關系的影響。這一結果也與現實生活中的影響力傳播過程高度一致,即受影響時間與到源節點的距離之差越小,值越高。不同網絡α和β的最佳值是不同的,但大多數測試結果表明,α和β最佳值集中在0.5 ～ 0.7。

本文還測試了正則項參數γ對損失函數的影響。圖4展示了在ego-Facebook網絡上損失的變化趨勢。從圖4中可以看出,不同的γ值損失函數值變化不大,其中圖4a為100次迭代損失的總體變化趨勢,圖4b為第50次～第100次迭代損失的總體變化趨勢。在對每個網絡進行測試期間,將迭代次數設置為接近于0的值。在本文的實驗中,根據迭代次數將γ設置在0.5以內。

Figure 4 The loss function under different values of γ圖4 損失函數中γ的影響

7.1.2 衰減因子

衰減因子調整了觀測節點被影響時間和節點距離差異的重要性。本文測試了DL-SIA在不同的衰減因子下的平均錯誤距離。圖5展示了利用DL-SIA方法在真實網絡上進行謠言源檢測的平均錯誤距離。圖5中的結果顯示,當參數在[0.42,0.53]取值時,DL-SIA方法的平均錯誤距離越低,說明在此范圍內謠言源定位的效果越好。

Figure 5 AED under different values of τ圖5 衰減因子τ對實驗結果的影響

7.1.3 觀測節點占比以及隨機可達路徑的長度

實驗中為了避免多個節點與任何觀測節點有相同距離的情況,本文選擇了一個雙可解集作為觀測節點集合。本文測試了Dl-SIA方法在不同的觀測節點占比以及不同的路徑長度下的表現。圖6展示了在不同的觀測節點占比和不同路徑長度下方法的平均錯誤距離。圖中橫軸代表觀測節點占比,縱軸代表路徑長度,每個網格的顏色代表其在設定的坐標參數下實驗得到的平均錯誤距離,顏色越深代表平均錯誤距離越長。

Figure 6 AED of different percentages of observers and the average length of randomly reachable paths圖6 不同比例觀測節點和不同的 隨機路徑長度對實驗結果的影響

從圖6可以看出,當路徑長度增加時,本文方法的效果提升越明顯。由于計算量隨路徑長度線性增加,運行時間也以可接受的速度增加。這一結果也表明,融合深度學習框架可以獲得更高的效率,并保持相對好的謠言源定位效果。由于真實網絡的連接性比虛擬網絡更強,平均路徑長度越長,平均聚類系數越高,上述現象在真實網絡中更為明顯。當檢測到的平均路徑長度達到20時,本文方法的準確性明顯提高,平均誤差距離下降到2跳左右。然而,當路徑長度超過20時,這種改善相對較小。可以為每個網絡設置一個合適的路徑長度,盡可能減少計算時間,以保證本文方法能達到理想的效果。

從圖6可以看出,在觀測節點占比較小時,觀測節點占比的增加對DL-SIA方法效果的影響較小。然而,當觀測節點的占比達到大約30%～40%時,DL-SIA的平均錯誤距離會明顯下降。這一結果表明,觀測節點的占比對DL-SIA的效果有著較大的影響。因此,考慮到實際環境和計算成本并保證DL-SIA的效果,本文得出以下結論:觀測節點的占比應該在40%～60%,隨機路徑長度應該在30～50。上述參數可以根據網絡規模適當調整。

7.2 消融實驗

為了進一步證明本文方法DL-SIA的有效性,設計了消融實驗。由于Lossreg是自編碼網絡中的一個正則項,本文考慮以下4種情況并進行實驗:

情況1將Lossx+Lossreg作為損失函數,即自編碼網絡使用節點的影響力向量作為節點的初始特征輸入神經網絡,不使用路徑相似性及節點相似性信息對訓練過程加以限制。

情況2將Lossx+Lossreg+Lossα作為損失函數,即自編碼網絡使用節點的影響力向量作為節點的初始特征輸入神經網絡,并使用路徑相似性限制訓練過程。最終通過自編碼網絡得到的節點嵌入表示同時包含傳播時間信息及傳播的路徑信息。

情況3將Lossx+Lossreg+Lossr作為損失函數,即自編碼網絡使用節點的影響力向量作為節點的初始特征輸入神經網絡,并使用節點相似性限制訓練過程,最終得到包含節點信息和傳播時間的節點嵌入表示。

情況4使用DL-SIA方法損失函數,即Lossx+αLossα+βLossr+γLossreg。自編碼網絡將節點的影響力向量作為輸入,并利用路徑相似性及節點相似性將節點映射到包含傳播時間、傳播路徑及節點信息的潛在空間,得到新的節點嵌入表示。

表3為上述4種情況得到的準確率和平均錯誤距離。可以看到,情況1只使用Lossx作為損失函數時得到的結果最差。對于情況2,準確率提高了5.30%,平均錯誤距離降低了7.78%。對于情況3,平均精度提高了5.30%,平均錯誤距離降低了23.51%。這表明,在訓練過程中加入路徑相似性以及節點相似性信息有助于提高謠言源檢測的精度。此外,據觀察,加入Lossr對于提高DL-SIA方法的性能比加入Lossα更為突出。

Table 3 Precision and average error distance in four different situations表3 4種情況下方法的準確率和平均錯誤距離

對于情況4,由于損失函數同時包含Lossα和Lossr,所以DL-SIA方法的精度得到了很大的提高。與情況1中使用的基本損失函數相比,當使用DL-SIA方法的損失函數時,平均精度提高了19.13%,平均錯誤距離降低了57.09%。上述消融實驗結果充分證明了DL-SIA方法設計是合理有效的。

7.3 謠言源定位的準確率

圖7展示了所有方法在每個網絡上的準確率。從圖7可以看出,本文DL-SIA方法優于其他基于中心性和基于感染路徑的方法。DL-SIA在BA、WS、Email-Eu-core和ego-Facebook網絡中的準確率明顯提高了25.0%～41.8%。從這4個網絡的準確率趨勢變化可以看出,當觀測節點的占比超過40%時,謠言源定位效果的提升就會放緩。總的來說,DL-SIA方法的準確率遠遠高于其他方法的,這表明DL-SIA方法的謠言源定位能力很強。此外,隨著觀測節點占比的增加,DL-SIA方法準確率也隨之提高,這也表明了DL-SIA方法設計中節點信息嵌入的科學性和準確性。

Figure 7 Precision values of different methods圖7 不同方法的準確率

7.4 謠言源定位的平均錯誤距離

為了驗證本文DL-SIA方法的準確性,還測試了其平均錯誤距離,并將其和其他方法的平均錯誤距離進行了比較。

圖8展示了各方法在2個模擬網絡(BA,WS)和2個真實網絡(Email-Eu-core,ego-Facebook)上的平均錯誤距離。與RC和JC等中心性方法相比,DL-SIA方法的平均錯誤距離較小。以1 000節點規模的網絡為例,如BA、WS和Email-Eu-core,在觀測節點占比較低的情況下,DL-SIA取得的平均錯誤距離相比其他方法的要低得多。這一結果表明,DL-SIA方法真實謠言源和估計謠言源之間的距離比其它方法的少約2.18跳。在大規模網絡ego-Facebook的測試中,與其他方法相比,DL-SIA定位到源節點的平均錯誤距離比真實謠言源減少了約4.82跳。這一結果表明,在更大規模的網絡中,DL-SIA方法相對其他對比方法表現更出色。在定位的初始階段,DL-SIA的平均錯誤距離與DMP方法的接近,但DMP方法的優勢并不明顯。從整體情況來看,與DL-SIA方法相比,DMP方法在早期階段獲得的微小優勢不能掩蓋其整體效果的不足。

Figure 8 Average error distances of different methods圖8 不同方法的平均錯誤距離

圖9～圖12展示了這4個網絡上不同數量謠言源的平均錯誤距離分布。本文將DL-SIA的平均錯誤距離與Net Sleuth和K-Center方法的平均錯誤距離進行了比較。如圖9～圖12所示,當隨機選擇2個謠言源時,Net Sleuth、K-Center和DL-SIA取得了相似的性能。但是,通過觀察直方圖的峰值可以發現,DL-SIA的平均錯誤距離集中在大約0～2跳,而K-Center在1～3跳,Net Sleuth在2～5跳。

表4展示了本文提出的多謠言源定位方法的平均錯誤距離。表4中的比例指的是由各方法得出的源節點與實際源節點的距離不超過3跳的概率。從表4可以看出,當謠言源數設置為2和3時,K-Center的平均錯誤距離與DL-SIA的接近。與K-Center方法相比,DL-SIA方法的平均錯誤距離可以減少約7.9%～19.5%。實驗中,Net Sleuth的結果最差。

隨著謠言源節點數量的增加,DL-SIA的平均錯誤距離穩定在3跳。從表4可以看出,盡管網絡中存在多個源,但DL-SIA方法的平均錯誤距離與其他方法的相比,有22.9%～38.8%的改善。這一統計結果表明,DL-SIA可以處理網絡中多謠言源傳播的復雜情況。而隨著源節點數量的增加,DL-SIA的表現更加突出,在平均錯誤距離上獲得了近50%的改進。

Figure 9 Average error distances of different methods when k=2圖9 不同方法在k=2時的平均錯誤距離

Figure 10 Average error distances of different methods when k=3圖10 不同方法在k=3時的平均錯誤距離

Figure 11 Average error distances of different methods when k=4圖11 不同方法在k=4時的平均錯誤距離

Figure 12 Average error distances of different methods when k=5圖12 不同方法在k=5時的平均錯誤距離

7.5 運行時間

圖13展示了不同觀測節點占比下DL-SIA單源檢測的計算時間。從圖13中可以看出,計算時間隨著觀測節點數量的增加呈線性增加。這一結果也證明了結合深度學習框架的謠言源定位方法可以獲得更高的效率,并保持相對較高的精度。

本文測試了DL-SIA方法在不同占比的觀測節點和不同路徑長度下在4個網絡上的運行時間。將觀測到的節點占比設定為40%,路徑長度設定為40。

圖14為不同方法的運行時間測試結果,在大多數情況下,DL-SIA方法的運行速度要比DMP和EDA的快。RC和JC的計算時間低于其他方法的。基于中心性的方法RC和JC的計算時間較短,這是因為它們的計算只考慮每個節點的中心度。其他3種方法需要根據網絡的全局拓撲信息計算每個節點在每個時間步的狀態。但是,基于中心性的方法RC和JC的準確率要比DL-SIA方法的低得多,因為它們為了速度犧牲了準確率。綜合考慮實驗的效果和運行時間,本文的DL-ISA方法相比其他方法有著更優秀的表現。對于DMP和EPA方法,盡管DMP相比EPA有更高的準確率,但它需要2倍多的時間來獲得與EPA相同的準確率。特別是在一些大規模的網絡中,DMP甚至無法準確定位謠言源。

Figure 13 Running time of DL-SIA under different percentages of observers and path length圖13 DL-SIA方法在不同比例觀測者 和隨機可達路徑長度下的運行時間

Figure 14 Running time of different methods圖14 不同方法的運行時間

8 結束語

本文提出了一種名為DL-SIA的基于深度學習的方法,該方法可以整合謠言的擴散時間、傳播路徑以及節點的拓撲特征信息來定位謠言源。首先,采用隨機游走策略來計算每個節點與觀測節點之間的影響力向量。其次,設計了一個自編碼器(AE)神經網絡,將節點映射到潛在空間。然后,通過節點嵌入計算出節點是源節點的概率并定位謠言源。在6個網絡上的實驗結果表明,本文的DL-SIA方法可以更有效地定位謠言源。

在社交網絡中,個體之間的關系和邊上的傳播概率可能經常變化。許多社交網絡由在線和離線用戶、關注和不關注的用戶組成,這影響了社交網絡的拓撲結構,造成了傳播過程中的巨大變化。因此,謠言源定位策略應作出相應改進。目前,很多研究人員都在關注動態社交網絡中的影響力分析,如鏈接預測、影響力傳播最大化等。然而,動態網絡中的不穩定因素和高計算復雜性使得動態網絡中的謠言源定位問題更具挑戰性。未來的研究將利用深度學習方法設計更有效的方法來定位這種動態網絡中的多謠言源。