劉 徹,劉祖根

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

0 引 言

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

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

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

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

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

1.1 謠言傳播模型

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

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

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

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

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

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

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

1.2 謠言源極大似然估計器

(1)

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

1.3 謠言中心性

圖1 示例圖

R(v,GN)

(2)

(3)

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

2 算法模型

2.1 MPA算法模型

(4)

(5)

2.2 IMPA算法模型

2.3 評估模型

3 實驗與分析

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

選用3個網(wǎng)絡(luò)拓撲結(jié)構(gòu)完全不同的真實社會網(wǎng)絡(luò)數(shù)據(jù)集進行仿真實驗，具體的數(shù)據(jù)集信息見表1。

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

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

3.2 實驗配置

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

3.3 實驗分析

3.3.1 準(zhǔn)確率

(a) Facebook

(b) P2p-Gnutella08

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

3.3.2 運行時間

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

(a) Facebook

(b) P2p-Gnutella08

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

4 結(jié)束語

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