基于信息傳遞的謠言源檢測新算法

劉 徹,劉祖根

(云南財(cái)經(jīng)大學(xué)信息學(xué)院,云南 昆明 650032)

0 引 言

人們因?yàn)閷W(xué)習(xí)、生活與工作等需要而身處社會(huì)網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、技術(shù)網(wǎng)絡(luò)等不同類型的復(fù)雜網(wǎng)絡(luò)系統(tǒng)中[1]。社交媒體自其誕生以來就吸引了很多使用者，在不到20年的時(shí)間里，全球的社交媒體已經(jīng)擁有了幾十億的用戶。在當(dāng)今這個(gè)信息大爆炸的時(shí)代里，隨著網(wǎng)絡(luò)技術(shù)的快速發(fā)展，以及移動(dòng)設(shè)備的飛速更新，使得社交網(wǎng)絡(luò)無處不在，社交網(wǎng)絡(luò)儼然已經(jīng)成為人們生活中無法缺少的一部分，無論是工作、學(xué)習(xí)，還是生活、娛樂都離不開社交網(wǎng)絡(luò)。人們不僅可以與家人和朋友保持聯(lián)系，還可以隨時(shí)了解當(dāng)前正在發(fā)生的實(shí)事和最新消息。而且人們在社交網(wǎng)絡(luò)中的角色發(fā)生了變化，不再僅僅是接受者，同時(shí)也是信息內(nèi)容的創(chuàng)造者、傳播者。許多新聞媒體將自己的宣傳媒介放在社交網(wǎng)絡(luò)上，發(fā)布實(shí)時(shí)新聞，普通用戶也能夠通過社交網(wǎng)絡(luò)從個(gè)人的角度發(fā)表自己的觀點(diǎn)和看法，媒體和用戶為了盡快地發(fā)布信息，信息內(nèi)容的可信度就受到了威脅，當(dāng)各大媒體之間出現(xiàn)競爭意識的時(shí)候，發(fā)布正確的、可信的信息變得尤為困難。假新聞對民主話語可信度的影響以及普遍的錯(cuò)誤信息的廣泛傳播，學(xué)者和評論家對其表現(xiàn)出了極大的擔(dān)憂[2]。據(jù)最近的一份報(bào)告顯示，當(dāng)前有15.9億Facebook用戶，他們的平均分離程度只有3.57[3]。也就是說，如果幾個(gè)人在社交網(wǎng)絡(luò)上發(fā)布一個(gè)謠言，那么在短時(shí)間內(nèi)會(huì)有很多人被其影響。更是有調(diào)查顯示，平均而言，65歲以上的用戶分享假新聞的文章數(shù)量幾乎是最年輕群體的7倍[4]。

在社交網(wǎng)絡(luò)中，由于謠言傳播過程的復(fù)雜性、數(shù)據(jù)的實(shí)時(shí)性以及網(wǎng)絡(luò)的動(dòng)態(tài)變化，如何快速準(zhǔn)確地檢測出謠言的來源是一項(xiàng)非常具有挑戰(zhàn)性的任務(wù)。近年來,許多基于Web的系統(tǒng)被開發(fā)用來檢測和評估謠言,包括：1)TwitterTrails.com[5],一個(gè)允許用戶確定謠言傳播特性的系統(tǒng)；2)TweedCred[6]，一個(gè)瞬時(shí)判斷Twitter推文可信度的系統(tǒng)；3)Hoaxy[7]，在一個(gè)社交網(wǎng)絡(luò)中跟蹤錯(cuò)誤信息的平臺；4)Emergent.info[8]，一個(gè)實(shí)時(shí)的謠言追隨者，專注于互聯(lián)網(wǎng)上的熱點(diǎn)事件；5)Snopes.com[9]、Factcheck.org[10]，存儲一些奇異事件或城市傳說。這些謠言檢測系統(tǒng)的真實(shí)性檢測性能驗(yàn)證了網(wǎng)絡(luò)謠言的真實(shí)性，從完全自動(dòng)化到半自動(dòng)都有。但是，這些系統(tǒng)沒有跟蹤或觀察擴(kuò)散過程，也沒有檢測到所有可能的謠言源。所以在社交網(wǎng)絡(luò)上發(fā)現(xiàn)虛假信息、檢測謠言源是一個(gè)亟需解決的問題，但在技術(shù)上也是一個(gè)具有挑戰(zhàn)性的問題，因?yàn)槿藗儫o法使用眼睛直觀地判斷哪些是虛假信息，哪些是真實(shí)信息，甚至在思考之后也無法抉擇信息的真假，更無法想當(dāng)然地猜測謠言的來源。

Shah和Zaman[11]首先提出了謠言源在樹狀網(wǎng)絡(luò)中的識別工作，將謠言中心性度量用于信源估計(jì)，考慮了信息擴(kuò)散的SIR模型。節(jié)點(diǎn)的謠言中心被描述為從源節(jié)點(diǎn)開始的若干確定的傳播路徑。謠言中心度較高的節(jié)點(diǎn)是信息傳播的源頭。謠言中心測度的有效性在文獻(xiàn)[12]中得到了進(jìn)一步的分析。Dong等[13]利用同樣的方法和結(jié)果，利用局部謠言中心度量對源進(jìn)行識別。Yu等[14]將易受影響的節(jié)點(diǎn)考慮為有限節(jié)點(diǎn)，并將端點(diǎn)(接收謠言但不轉(zhuǎn)發(fā)的節(jié)點(diǎn))作為邊界節(jié)點(diǎn)，利用謠言中心性度量進(jìn)行源檢測。他們考慮了一個(gè)有限圖用于源檢測，并使用消息傳遞方法來減少頂點(diǎn)搜索以獲得最大似然估計(jì)。

本文的謠言傳播模型以及算法模型，是在Shah等人[11]研究算法的基礎(chǔ)之上加以改進(jìn)。通過真實(shí)網(wǎng)絡(luò)數(shù)據(jù)的SI(Susceptible-Infected)模型傳播仿真，并分析比較本文提出的算法與之前算法的效率結(jié)果，實(shí)驗(yàn)結(jié)果表明，新算法檢測謠言源的準(zhǔn)確率更高，相同的檢測任務(wù)，其實(shí)際執(zhí)行時(shí)間更短。

1 相關(guān)研究及算法模型

1.1 謠言傳播模型

流行病模型主要用于尋找病毒性疾病的起源，由于人群中的流行病類似于謠言在社交網(wǎng)絡(luò)中的傳播，所以流行病模型可以用于尋找謠言的來源。在模型中，節(jié)點(diǎn)通常具有3種狀態(tài)：易感狀態(tài)(Susceptible， S)、感染狀態(tài)(Infected， I)以及恢復(fù)狀態(tài)(Recovered，R)。每一個(gè)節(jié)點(diǎn)只能具有其中一種狀態(tài)，不能同時(shí)具有2種或2種以上的狀態(tài)。當(dāng)前最為常見的流行病模型有4種：

1)SI模型。最初，節(jié)點(diǎn)是易感狀態(tài)，并且可以被SI模型中傳播的謠言感染。易感染的節(jié)點(diǎn)是未受感染的節(jié)點(diǎn)，如果它們的鄰居節(jié)點(diǎn)受到了感染，它們被感染的可能性更高，而受感染的節(jié)點(diǎn)將永遠(yuǎn)受到感染。在社交網(wǎng)絡(luò)謠言傳播方面，受感染節(jié)點(diǎn)就是已經(jīng)收到謠言的節(jié)點(diǎn)，易感節(jié)點(diǎn)是沒有收到任何謠言的節(jié)點(diǎn)，但是由于相鄰的受感染節(jié)點(diǎn)，易感節(jié)點(diǎn)在收到謠言后可以被感染。

2)SIS模型。在SIS模型中，節(jié)點(diǎn)的狀態(tài)仍然只有易感狀態(tài)和受感染狀態(tài)，但在這個(gè)模型中，當(dāng)易感節(jié)點(diǎn)受到感染后，它們可以在一段時(shí)間后恢復(fù)到易感狀態(tài)。

3)SIR模型。在SIR模型中,節(jié)點(diǎn)具有3種狀態(tài)，易感狀態(tài)、感染狀態(tài)和恢復(fù)狀態(tài)。SIS和SIR模型之間唯一的變化是,在SIS模型被感染節(jié)點(diǎn)可以變回易感狀態(tài)，而在SIR模型中被感染節(jié)點(diǎn)可以通過忽略消息或者不將消息傳遞給鄰居的方式變?yōu)榛謴?fù)狀態(tài)?；謴?fù)的節(jié)點(diǎn)可以一直保持恢復(fù)狀態(tài)。在社交網(wǎng)絡(luò)中，恢復(fù)的節(jié)點(diǎn)相當(dāng)于是知道謠言的節(jié)點(diǎn)。

4)SIRS模型。在SIRS模型中，恢復(fù)后的節(jié)點(diǎn)可能再次成為具有一定概率的易感節(jié)點(diǎn)。

所有這些基本的流行病模型都得到了相應(yīng)的解釋，它們用于描述網(wǎng)絡(luò)節(jié)點(diǎn)的感染和恢復(fù)過程。作為該領(lǐng)域的另一個(gè)基礎(chǔ)，不同的模型在尋找傳播源時(shí)涉及不同的場景，如SI用于檢測感染源[15]；SIS用于識別謠言源[16]和有影響力的節(jié)點(diǎn)[17]；SIR用于信息源[18]和網(wǎng)絡(luò)論壇話題傳播[19]；SIRS模型用于分析網(wǎng)絡(luò)中的僵尸網(wǎng)絡(luò)交互[20]。

假設(shè)一個(gè)節(jié)點(diǎn)網(wǎng)絡(luò)模型為無向圖G(V,E)，其中V是模型中的節(jié)點(diǎn)數(shù)，E是模型中的邊數(shù)。在最初的情況下，只考慮一個(gè)節(jié)點(diǎn)V作為謠言源。本算法將采用SI模型作為謠言在網(wǎng)絡(luò)中的傳播仿真，一旦節(jié)點(diǎn)Vi是感染狀態(tài)，將不會(huì)變?yōu)橐赘袪顟B(tài)或者恢復(fù)狀態(tài)，并且，它可以使鄰居節(jié)點(diǎn)Vj成為感染狀態(tài)。

1.2 謠言源極大似然估計(jì)器

(1)

其中P(GN|v)是在SI模型下觀察GN的概率，假設(shè)v是源v*。因此，想對所有v∈GN求P(GN|v)的值，然后選擇其中值最大的一個(gè)。

1.3 謠言中心性

圖1 示例圖

R(v,GN)

(2)

(3)

再次以圖1為例，節(jié)點(diǎn)1的謠言中心性為：

2 算法模型

2.1 MPA算法模型

(4)

(5)

2.2 IMPA算法模型

2.3 評估模型

3 實(shí)驗(yàn)與分析

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

選用3個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)完全不同的真實(shí)社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)，具體的數(shù)據(jù)集信息見表1。

表1 數(shù)據(jù)集

數(shù)據(jù)集名稱節(jié)點(diǎn)數(shù)邊數(shù)平均度數(shù)直徑Facebook[21]40398823421.88P2p-Gnutella08[22]6301207773.39Wiki-Vote[23]711510368915.67

3.2 實(shí)驗(yàn)配置

所有的實(shí)驗(yàn)均是基于Python2.7版本完成的，運(yùn)行平臺是PyCharm，計(jì)算機(jī)的內(nèi)存是16 GB。

3.3 實(shí)驗(yàn)分析

3.3.1 準(zhǔn)確率

(a) Facebook

(b) P2p-Gnutella08

(c) Wiki-Vote圖2 3種數(shù)據(jù)集的準(zhǔn)確率

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

實(shí)驗(yàn)結(jié)果如圖3所示，實(shí)線代表著IMPA，虛線代表著MPA。從謠言源檢測的時(shí)間來看，在不同數(shù)量的感染節(jié)點(diǎn)情況下，IMPA所示時(shí)間都要少于MPA所用時(shí)間，這就說明了先找到葉子節(jié)點(diǎn)，并進(jìn)行信息的層層傳遞，比一個(gè)個(gè)單獨(dú)判斷是否為葉子節(jié)點(diǎn)要更快。在需要計(jì)算父節(jié)點(diǎn)的謠言中心性時(shí)，能夠直接進(jìn)行計(jì)算，省去相應(yīng)判斷葉子節(jié)點(diǎn)的時(shí)間，在實(shí)際的算法中就相當(dāng)于減少了猶豫的過程，從而縮短了IMPA的執(zhí)行時(shí)間，提高了算法效率。而且，隨著感染節(jié)點(diǎn)的增加，2種算法所需時(shí)間都隨之上升，雖然2種算法的時(shí)間復(fù)雜度都為O(N)，但是IMPA的時(shí)間增長速率比MPA增長幅度小。因此，在時(shí)間方面，MPA的表現(xiàn)還是要比IMPA略遜一籌。

(a) Facebook

(b) P2p-Gnutella08

(c) Wiki-Vote圖3 3種數(shù)據(jù)集的運(yùn)行時(shí)間

4 結(jié)束語

準(zhǔn)確高效地發(fā)現(xiàn)社交網(wǎng)絡(luò)中有謠言傳播源，具有非常重要的理論和現(xiàn)實(shí)意義。近年來，如何檢測謠言以及如何發(fā)現(xiàn)謠言的源頭受到了多領(lǐng)域?qū)W者的廣泛關(guān)注。相對于謠言檢測方法，謠言源檢測更具有難度和挑戰(zhàn)性。本文通過改進(jìn)傳統(tǒng)的謠言源檢測算法MPA，在3種真實(shí)網(wǎng)絡(luò)數(shù)據(jù)上通過SI模型得到的仿真實(shí)驗(yàn)結(jié)果表明，IMPA能夠在準(zhǔn)確率方面略有提升。謠言源并不是一直不變的，謠言傳播的路徑也會(huì)根據(jù)事件動(dòng)態(tài)地變化而改變。因此，下一步將研究在SIR模型或SIRS模型中的謠言源檢測，并嘗試從理論上開展一定的工作。另外，本文工作是針對靜態(tài)的簡單網(wǎng)絡(luò)進(jìn)行的研究，進(jìn)一步工作將擴(kuò)展到動(dòng)態(tài)網(wǎng)絡(luò)的研究。