基于深度學(xué)習(xí)節(jié)點表示的謠言源定位方法*

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

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

1 引言

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

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

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

多謠言源定位方法主要可以分為3類:基于社區(qū)的多謠言源定位方法、基于傳播路徑的多謠言源定位方法和基于排名的多謠言源定位方法。基于社區(qū)的多謠言源定位方法[7,8]首先利用網(wǎng)絡(luò)的拓撲信息對網(wǎng)絡(luò)進行劃分,然后在每個社區(qū)內(nèi)解決單源識別問題。然而,基于社區(qū)的多謠言源定位方法的效果在很大程度上取決于觀測節(jié)點的選擇?；趥鞑ヂ窂降姆椒◤姆聪騻鞑9]、貝葉斯理論[10]、感染序列[11]和置信集[12]等角度考慮來自每個謠言源節(jié)點的復(fù)雜感染路徑。然而,這些多謠言源檢測方法大多采用貪婪的策略來尋找謠言源,因此需要多次模擬來估計每個候選源節(jié)點集的傳播范圍。由于這2類方法時間復(fù)雜度較高,所以并不適用于大規(guī)模網(wǎng)絡(luò)?；谂琶亩嘀{言源定位方法[10,12]首先估計一些度量值,用這些度量值表示節(jié)點作為源的概率,然后根據(jù)度量值對節(jié)點進行排序,最后選擇度量值最高的節(jié)點作為源節(jié)點。然而,這些方法認為網(wǎng)絡(luò)中的所有節(jié)點和邊都是相同的,忽略了信息傳播中觀測到的節(jié)點的關(guān)鍵潛在拓撲特征。由于節(jié)點的關(guān)鍵拓撲特征丟失,這些方法謠言源定位的效果往往不夠理想。

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

本文的主要工作如下:

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

3 預(yù)備知識

本節(jié)介紹獨立級聯(lián)模型,并定義多謠言源定位問題。

3.1 獨立級聯(lián)模型

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

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

3.2 多謠言源定位問題

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

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

在現(xiàn)實世界中,觀測節(jié)點集合O的選擇必須滿足以下條件:對于任意2個節(jié)點v1和v2,至少存在O中的一個節(jié)點o使得該節(jié)點分別到v1和v2的距離不相同?；谏鲜鰲l件,本文選擇一個雙重可分解集[22]作為觀測節(jié)點集。

3.3 方法框架

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

4 基于深度學(xué)習(xí)的節(jié)點表示

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

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

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

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

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

(1)

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

(2)

(3)

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

(4)

(5)

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

Figure 2 Structure of auto-encoder network圖2 自編碼神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

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

算法1 RW-Path-Analysis算法輸入:G':G=(V,E,P)的逆向圖;H:隨機游走路徑的最大長度;K:采樣次數(shù);O:觀測節(jié)點集合。輸出:l:所有隨機游走路徑集合,對于觀測節(jié)點om,lm={l(m)1,l(m)2,…,l(m)j,…,l(m)K},其中l(wèi)(m)j是從om開始的第j條隨機游走路徑;Cm:觀測節(jié)點om的候選源節(jié)點集合;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. 根據(jù)概率pw,u選擇G'中節(jié)點u的一個鄰居節(jié)點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 自編碼神經(jīng)網(wǎng)絡(luò)

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

4.3 激活函數(shù)

(6)

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

(7)

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

(8)

(9)

(10)

(11)

(12)

(13)

(14)

4.4 損失函數(shù)

(15)

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

(16)

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

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

(17)

其中,ru,v為節(jié)點u與節(jié)點v之間的節(jié)點相似度。損失Lossr的加入保證了神經(jīng)網(wǎng)絡(luò)訓(xùn)練時保留了節(jié)點信息,也就是說相似的節(jié)點在潛在空間的嵌入更接近。

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

(18)

基于上述損失項,定義自編碼網(wǎng)絡(luò)的損失函數(shù)如式(19)所示:

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

(19)

該損失函數(shù)保證了自編碼網(wǎng)絡(luò)將節(jié)點向量映射到了一個包含傳播路徑、傳播時間和節(jié)點信息的潛在空間。

4.5 自編碼網(wǎng)絡(luò)的訓(xùn)練

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

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

(20)

Lossr=2tr(ZTL(r)Z)

(21)

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

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

(22)

(23)

(24)

(25)

(26)

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

算法2 訓(xùn)練自編碼網(wǎng)絡(luò)輸入:節(jié)點v與觀測節(jié)點之間的影響力向量x(1)v,…,x(M)v;A:路徑相似度矩陣;O:觀測節(jié)點集合;α,β,γ,ε:參數(shù);e:迭代次數(shù)。輸出:節(jié)點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 基于深度學(xué)習(xí)的謠言源定位

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

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

(27)

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

(28)

本文選擇概率P(O|v)最高的節(jié)點為謠言源?；谏疃葘W(xué)習(xí)的謠言源定位方法DL-SIA的偽代碼如算法3所示。

算法3 基于深度學(xué)習(xí)的謠言源定位方法(DL-SIA)輸入:G=(V,E,P):社交網(wǎng)絡(luò);k:謠言源的數(shù)量;O:觀測節(jié)點集合;T:觀測節(jié)點的感染時間。輸出:S*={S*1,S*2,…,S*k}:謠言源節(jié)點集合。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 復(fù)雜度分析

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

6 實驗設(shè)計

6.1 數(shù)據(jù)集

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

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

(29)

其中,N為節(jié)點數(shù)。

表2列出了DL-SIA方法在不同網(wǎng)絡(luò)上的神經(jīng)網(wǎng)絡(luò)參數(shù)設(shè)置。

Table 1 Topological features of the networks表1 不同網(wǎng)絡(luò)的拓撲結(jié)構(gòu)

Table 2 Default settings of neural networks in different datasets表2 不同網(wǎng)絡(luò)集上的神經(jīng)網(wǎng)絡(luò)設(shè)置

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 結(jié)果

7.1 參數(shù)對DL-SIA方法的影響

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

7.1.1α、β和γ對實驗結(jié)果的影響

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

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

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

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

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

7.1.2 衰減因子

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

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

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

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

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

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

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

7.2 消融實驗

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

情況1將Lossx+Lossreg作為損失函數(shù),即自編碼網(wǎng)絡(luò)使用節(jié)點的影響力向量作為節(jié)點的初始特征輸入神經(jīng)網(wǎng)絡(luò),不使用路徑相似性及節(jié)點相似性信息對訓(xùn)練過程加以限制。

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

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

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

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

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

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

7.3 謠言源定位的準確率

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

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

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

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

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

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

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

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

隨著謠言源節(jié)點數(shù)量的增加,DL-SIA的平均錯誤距離穩(wěn)定在3跳。從表4可以看出,盡管網(wǎng)絡(luò)中存在多個源,但DL-SIA方法的平均錯誤距離與其他方法的相比,有22.9%～38.8%的改善。這一統(tǒng)計結(jié)果表明,DL-SIA可以處理網(wǎng)絡(luò)中多謠言源傳播的復(fù)雜情況。而隨著源節(jié)點數(shù)量的增加,DL-SIA的表現(xiàn)更加突出,在平均錯誤距離上獲得了近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展示了不同觀測節(jié)點占比下DL-SIA單源檢測的計算時間。從圖13中可以看出,計算時間隨著觀測節(jié)點數(shù)量的增加呈線性增加。這一結(jié)果也證明了結(jié)合深度學(xué)習(xí)框架的謠言源定位方法可以獲得更高的效率,并保持相對較高的精度。

本文測試了DL-SIA方法在不同占比的觀測節(jié)點和不同路徑長度下在4個網(wǎng)絡(luò)上的運行時間。將觀測到的節(jié)點占比設(shè)定為40%,路徑長度設(shè)定為40。

圖14為不同方法的運行時間測試結(jié)果,在大多數(shù)情況下,DL-SIA方法的運行速度要比DMP和EDA的快。RC和JC的計算時間低于其他方法的?；谥行男缘姆椒≧C和JC的計算時間較短,這是因為它們的計算只考慮每個節(jié)點的中心度。其他3種方法需要根據(jù)網(wǎng)絡(luò)的全局拓撲信息計算每個節(jié)點在每個時間步的狀態(tài)。但是,基于中心性的方法RC和JC的準確率要比DL-SIA方法的低得多,因為它們?yōu)榱怂俣葼奚藴蚀_率。綜合考慮實驗的效果和運行時間,本文的DL-ISA方法相比其他方法有著更優(yōu)秀的表現(xiàn)。對于DMP和EPA方法,盡管DMP相比EPA有更高的準確率,但它需要2倍多的時間來獲得與EPA相同的準確率。特別是在一些大規(guī)模的網(wǎng)絡(luò)中,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 結(jié)束語

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

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