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

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

1 引言

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

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

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

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

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

本文的主要工作如下:

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

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

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

(4) 通過整合節(jié)點(diǎn)的拓?fù)涮卣骷捌渑c網(wǎng)絡(luò)中觀察節(jié)點(diǎn)的距離,提出一種基于深度學(xué)習(xí)的方法。該方法能有效、準(zhǔn)確地識(shí)別影響源且能適用于多種傳播模型。

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

2 相關(guān)工作

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

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

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

有些方法將單謠言源定位問題轉(zhuǎn)化為一個(gè)分類問題,并使用基于神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)方法來識(shí)別謠言源。例如,文獻(xiàn)[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ò)的拓?fù)湫畔⒔⒛繕?biāo)函數(shù),忽略了觀測節(jié)點(diǎn)被感染的時(shí)間信息。觀測節(jié)點(diǎn)的受影響時(shí)間是謠言源定位的重要信息,因此忽略受影響時(shí)間的方法不能滿足特征提取的訓(xùn)練要求,也不能獲得高精度的結(jié)果。

3 預(yù)備知識(shí)

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

3.1 獨(dú)立級(jí)聯(lián)模型

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

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

3.2 多謠言源定位問題

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

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

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

3.3 方法框架

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

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

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

4.1 基于隨機(jī)游走的路徑分析算法

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

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

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

(1)

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

(2)

(3)

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

(4)

(5)

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

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

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

算法1 RW-Path-Analysis算法輸入:G':G=(V,E,P)的逆向圖;H:隨機(jī)游走路徑的最大長度;K:采樣次數(shù);O:觀測節(jié)點(diǎn)集合。輸出:l:所有隨機(jī)游走路徑集合,對(duì)于觀測節(jié)點(diǎn)om,lm={l(m)1,l(m)2,…,l(m)j,…,l(m)K},其中l(wèi)(m)j是從om開始的第j條隨機(jī)游走路徑;Cm:觀測節(jié)點(diǎn)om的候選源節(jié)點(diǎn)集合;d(m)v,j:om和v的隨機(jī)可達(dá)路徑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é)點(diǎn)u的一個(gè)鄰居節(jié)點(diǎn)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ò)

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

4.3 激活函數(shù)

(6)

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

(7)

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

(8)

(9)

(10)

(11)

(12)

(13)

(14)

4.4 損失函數(shù)

(15)

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

(16)

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

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

(17)

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

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

(18)

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

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

(19)

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

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

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

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

(20)

Lossr=2tr(ZTL(r)Z)

(21)

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

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

(22)

(23)

(24)

(25)

(26)

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

算法2 訓(xùn)練自編碼網(wǎng)絡(luò)輸入:節(jié)點(diǎn)v與觀測節(jié)點(diǎn)之間的影響力向量x(1)v,…,x(M)v;A:路徑相似度矩陣;O:觀測節(jié)點(diǎn)集合;α,β,γ,ε:參數(shù);e:迭代次數(shù)。輸出:節(jié)點(diǎn)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 基于隨機(jī)游走的路徑分析方法

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

(27)

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

(28)

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

算法3 基于深度學(xué)習(xí)的謠言源定位方法(DL-SIA)輸入:G=(V,E,P):社交網(wǎng)絡(luò);k:謠言源的數(shù)量;O:觀測節(jié)點(diǎn)集合;T:觀測節(jié)點(diǎn)的感染時(shí)間。輸出:S*={S*1,S*2,…,S*k}:謠言源節(jié)點(diǎn)集合。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é)點(diǎn)數(shù),K為隨機(jī)可達(dá)路徑數(shù),H為隨機(jī)可達(dá)路徑長度。計(jì)算路徑相似度的時(shí)間復(fù)雜度為O(H×K×N)。由于計(jì)算影響力向量需要遍歷所有的觀測者和節(jié)點(diǎn),其計(jì)算復(fù)雜度為O(M×N),其中M為觀測到的節(jié)點(diǎn)數(shù)。在AE網(wǎng)絡(luò)中,編碼器和解碼器部分的層數(shù)都是L。因此,DL-SIA的總復(fù)雜度為O(N·(H×K+M+(2L+1)·H))。在最壞的情況下,所有被感染的節(jié)點(diǎn)都被選為觀測者,即M=N。因?yàn)镵、L和H都可以被視為常數(shù),因此DL-SIA的時(shí)間復(fù)雜度為O(2N2)。

6 實(shí)驗(yàn)設(shè)計(jì)

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

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

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

(29)

其中,N為節(jié)點(diǎn)數(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ò)的拓?fù)浣Y(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 對(duì)比方法

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

6.3 評(píng)估指標(biāo)

本文采用平均錯(cuò)誤距離AED(Average Error Distance)和準(zhǔn)確率(Precision)2個(gè)評(píng)價(jià)指標(biāo)來衡量謠言源定位方法的有效性。

(1)平均錯(cuò)誤距離。

(30)

(2)準(zhǔn)確率。

(31)

準(zhǔn)確率越高說明方法的效果越好。

7 結(jié)果

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

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

7.1.1α、β和γ對(duì)實(shí)驗(yàn)結(jié)果的影響

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

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

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

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

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

7.1.2 衰減因子

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

Figure 5 AED under different values of τ圖5 衰減因子τ對(duì)實(shí)驗(yàn)結(jié)果的影響

7.1.3 觀測節(jié)點(diǎn)占比以及隨機(jī)可達(dá)路徑的長度

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

Figure 6 AED of different percentages of observers and the average length of randomly reachable paths圖6 不同比例觀測節(jié)點(diǎn)和不同的 隨機(jī)路徑長度對(duì)實(shí)驗(yàn)結(jié)果的影響

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

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

7.2 消融實(shí)驗(yàn)

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

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

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

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

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

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

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

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

7.3 謠言源定位的準(zhǔn)確率

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

Figure 7 Precision values of different methods圖7 不同方法的準(zhǔn)確率

7.4 謠言源定位的平均錯(cuò)誤距離

為了驗(yàn)證本文DL-SIA方法的準(zhǔn)確性,還測試了其平均錯(cuò)誤距離,并將其和其他方法的平均錯(cuò)誤距離進(jìn)行了比較。

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

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

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

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

隨著謠言源節(jié)點(diǎn)數(shù)量的增加,DL-SIA的平均錯(cuò)誤距離穩(wěn)定在3跳。從表4可以看出,盡管網(wǎng)絡(luò)中存在多個(gè)源,但DL-SIA方法的平均錯(cuò)誤距離與其他方法的相比,有22.9%～38.8%的改善。這一統(tǒng)計(jì)結(jié)果表明,DL-SIA可以處理網(wǎng)絡(luò)中多謠言源傳播的復(fù)雜情況。而隨著源節(jié)點(diǎn)數(shù)量的增加,DL-SIA的表現(xiàn)更加突出,在平均錯(cuò)誤距離上獲得了近50%的改進(jìn)。

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

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

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

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

7.5 運(yùn)行時(shí)間

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

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

圖14為不同方法的運(yùn)行時(shí)間測試結(jié)果,在大多數(shù)情況下,DL-SIA方法的運(yùn)行速度要比DMP和EDA的快。RC和JC的計(jì)算時(shí)間低于其他方法的?；谥行男缘姆椒≧C和JC的計(jì)算時(shí)間較短,這是因?yàn)樗鼈兊挠?jì)算只考慮每個(gè)節(jié)點(diǎn)的中心度。其他3種方法需要根據(jù)網(wǎng)絡(luò)的全局拓?fù)湫畔⒂?jì)算每個(gè)節(jié)點(diǎn)在每個(gè)時(shí)間步的狀態(tài)。但是,基于中心性的方法RC和JC的準(zhǔn)確率要比DL-SIA方法的低得多,因?yàn)樗鼈優(yōu)榱怂俣葼奚藴?zhǔn)確率。綜合考慮實(shí)驗(yàn)的效果和運(yùn)行時(shí)間,本文的DL-ISA方法相比其他方法有著更優(yōu)秀的表現(xiàn)。對(duì)于DMP和EPA方法,盡管DMP相比EPA有更高的準(zhǔn)確率,但它需要2倍多的時(shí)間來獲得與EPA相同的準(zhǔn)確率。特別是在一些大規(guī)模的網(wǎng)絡(luò)中,DMP甚至無法準(zhǔn)確定位謠言源。

Figure 13 Running time of DL-SIA under different percentages of observers and path length圖13 DL-SIA方法在不同比例觀測者 和隨機(jī)可達(dá)路徑長度下的運(yùn)行時(shí)間

Figure 14 Running time of different methods圖14 不同方法的運(yùn)行時(shí)間

8 結(jié)束語

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

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