吳 楊,吳國(guó)文,張 紅,沈士根,曹奇英

(1.東華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,上海 201620; 2.紹興文理學(xué)院計(jì)算機(jī)科學(xué)與工程系,浙江 紹興 312000)

0 引 言

隨著社交網(wǎng)絡(luò)的日益普及，微信、微博、Facebook等社交網(wǎng)絡(luò)媒體飛速發(fā)展，如今成為人們生活必不可少的社交平臺(tái)。這些社交網(wǎng)絡(luò)平臺(tái)為人們帶來(lái)便利的同時(shí)，也帶來(lái)了一些麻煩，網(wǎng)絡(luò)謠言就是其中之一。在當(dāng)今的社交網(wǎng)絡(luò)上充斥著五花八門(mén)的謠言，有些謠言會(huì)導(dǎo)致個(gè)人的利益受損、影響金融證券市場(chǎng)穩(wěn)定、社會(huì)混亂等問(wèn)題。所以，分析謠言的傳播過(guò)程并找出謠言傳播的源頭對(duì)于遏制謠言有十分重要的意義[1-6]。

近些年，謠言的傳播溯源問(wèn)題吸引了許多學(xué)者的關(guān)注。Comin等人[7]將接入性最大的節(jié)點(diǎn)推斷為源頭節(jié)點(diǎn)。Lokhov等人[8]通過(guò)找到傳播邊界概率最大的節(jié)點(diǎn)作為源頭估計(jì)器的估計(jì)值。在另一方面，有的學(xué)者通過(guò)將拓?fù)浣Y(jié)構(gòu)與極大似然估計(jì)的方法結(jié)合來(lái)定位源頭。這方面的開(kāi)創(chuàng)者Shah等人[9-11]在susceptible-infected(SI)模型中，根據(jù)觀測(cè)到的感染拓?fù)鋱D，提出了一個(gè)謠言中心的概念，并且證明在樹(shù)形網(wǎng)絡(luò)下謠言中心就是最大似然估計(jì)的值。之后在此基礎(chǔ)上，Luo等人[12]將謠言中心擴(kuò)展到了多個(gè)源頭的溯源問(wèn)題中。文獻(xiàn)[13-14]中基于極大似然估計(jì)提出局部謠言中心的概念，之后通過(guò)統(tǒng)計(jì)的方法求得信息源。Zhu等人[15]提出了基于最優(yōu)樣本路徑的方法解決susceptible-infected-recovered(SIR)模型下的溯源問(wèn)題，他們定義了一個(gè)感染偏心性，且具有最小感染偏心率的節(jié)點(diǎn)定義為拓?fù)鋱D中的Jordan感染中心，然后證明了在樹(shù)形網(wǎng)絡(luò)中Jordan感染中心就是最優(yōu)樣本路徑的源頭，即源頭的估計(jì)值。在文獻(xiàn)[16]中Jordan感染中心被運(yùn)用于多個(gè)信息源節(jié)點(diǎn)的源頭檢測(cè)問(wèn)題。Kang等人[17]將溯源問(wèn)題用于susceptible-infected-susceptible(SIS)模型中，Zhou等人[18]證明了Jordan感染中心的方法在susceptible-exposed-infected-recovered(SEIR)模型下溯源是可行的。此外，Pinto等人[19]在網(wǎng)絡(luò)中設(shè)置傳感器節(jié)點(diǎn)觀測(cè)感染過(guò)程的方法，提出了感染時(shí)間差異的極限定理，并運(yùn)用于溯源問(wèn)題中。

社交網(wǎng)絡(luò)中對(duì)傳播謠言的節(jié)點(diǎn)具有檢測(cè)能力，可對(duì)傳播過(guò)謠言的節(jié)點(diǎn)進(jìn)行隔離處理防止繼續(xù)影響其他節(jié)點(diǎn)。根據(jù)謠言傳播的性質(zhì)，本文提出一種擴(kuò)展傳染病模型SIOR來(lái)分析單一謠言源頭節(jié)點(diǎn)的傳播與溯源。本文基于最優(yōu)信息傳播過(guò)程來(lái)求解謠言源頭的估計(jì)值，并針對(duì)SIOR模型驗(yàn)證該估計(jì)值近似于網(wǎng)絡(luò)拓?fù)渲械腏ordan感染中心。此外，本文還根據(jù)文獻(xiàn)[15]中的RI算法，針對(duì)SIOR模型提出一種反向信息傳遞算法.并且在不同的網(wǎng)絡(luò)模型下進(jìn)行模擬實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，該算法的溯源準(zhǔn)確率要高于傳統(tǒng)的中心性算法，同時(shí)還對(duì)比SIR模型的溯源效率，結(jié)果顯示SIOR模型的溯源效率更優(yōu)。表1列出了本文所用符號(hào)及含義。

表1 本文所用符號(hào)

1 傳播模型

1.1 SIOR模型

謠言在社交網(wǎng)絡(luò)傳播的過(guò)程中，節(jié)點(diǎn)的狀態(tài)會(huì)發(fā)生一系列的變化，基于經(jīng)典SIR模型提出的擴(kuò)展型模型SIOR來(lái)研究單一信息源的溯源問(wèn)題。

SIOR模型包含S、I、O、R這4種狀態(tài)。圖1給出了節(jié)點(diǎn)狀態(tài)轉(zhuǎn)換模型。S狀態(tài)的節(jié)點(diǎn)在受到傳播者傳播的信息后，可能會(huì)以概率p1相信該消息，從而狀態(tài)轉(zhuǎn)變?yōu)镮，同時(shí)也存在一些人，不會(huì)輕易相信該消息，或是可以辨別該消息是否屬于謠言而以p2直接轉(zhuǎn)換為R的狀態(tài)，但必須鄰居節(jié)點(diǎn)要為I狀態(tài)時(shí)才會(huì)轉(zhuǎn)換。而當(dāng)一個(gè)節(jié)點(diǎn)屬于I狀態(tài)時(shí)，可能會(huì)以概率q1不再相信該信息轉(zhuǎn)換為R狀態(tài)，也可能被系統(tǒng)檢測(cè)到傳播謠言而進(jìn)行封號(hào)處理，處于O狀態(tài)不能繼續(xù)發(fā)消息影響其他節(jié)點(diǎn)，在之后某時(shí)刻被解封轉(zhuǎn)換為R狀態(tài)。其中封號(hào)概率與解封概率分別為o1和o2。

圖1 基于SIOR的狀態(tài)轉(zhuǎn)換模型

給定一個(gè)無(wú)向圖G={V,E},V、E分別為圖的節(jié)點(diǎn)集合和邊的集合。每個(gè)節(jié)點(diǎn)v∈V包含S、I、O、R這4種狀態(tài)。在信息的傳播過(guò)程中，假設(shè)一個(gè)時(shí)間戳系統(tǒng)。當(dāng)t=0時(shí)，圖中節(jié)點(diǎn)只有一個(gè)感染狀態(tài)節(jié)點(diǎn)即源頭節(jié)點(diǎn)s*，其他的節(jié)點(diǎn)都處于S狀態(tài)。每個(gè)節(jié)點(diǎn)只會(huì)在每個(gè)時(shí)間片開(kāi)始的時(shí)候改變它的狀態(tài)。例如：每個(gè)感染節(jié)點(diǎn)會(huì)在時(shí)間戳的開(kāi)始把信息傳遞給它的鄰居節(jié)點(diǎn)，而接收到的鄰居節(jié)點(diǎn)會(huì)以p1的概率轉(zhuǎn)化為I狀態(tài)，而對(duì)于不相信該信息的人該節(jié)點(diǎn)會(huì)以概率p2轉(zhuǎn)換為R狀態(tài)。另外還假定變?yōu)镽狀態(tài)的節(jié)點(diǎn)不會(huì)再信任該信息，即不會(huì)再被感染為I狀態(tài)。

由于節(jié)點(diǎn)狀態(tài)的變化取決于鄰居節(jié)點(diǎn)的狀態(tài)或上一個(gè)時(shí)間戳該節(jié)點(diǎn)的狀態(tài)，所以可以采用離散時(shí)間的馬爾可夫鏈來(lái)描述某一時(shí)間戳節(jié)點(diǎn)的狀態(tài)情況。令φv(t)表示節(jié)點(diǎn)v在t時(shí)刻的狀態(tài)，令Φ(t)表示馬爾可夫鏈，表達(dá)式為Φ(t)={φv(t)|v∈V}，作用是表示t時(shí)刻拓?fù)鋱D中所有節(jié)點(diǎn)的狀態(tài)。例如初始時(shí)刻t=0,表示為：

φs*(0)=I，Φ(0)={I,S,S,S,S,…,S}

圖2 節(jié)點(diǎn)狀態(tài)轉(zhuǎn)化過(guò)程

在圖2中，時(shí)間戳t=4時(shí)節(jié)點(diǎn)的狀態(tài)為：

Φ(T)={S,I,R,R,R,S,S,O,R,I}

1.2 觀測(cè)網(wǎng)絡(luò)模型

要獲取傳播過(guò)程中某一時(shí)刻的拓?fù)鋱D，定義Ω={ωv,v∈V}來(lái)表示觀測(cè)快照中節(jié)點(diǎn)的狀態(tài)，根據(jù)真實(shí)的情況，觀測(cè)快照是無(wú)法區(qū)分S狀態(tài)和R狀態(tài)的節(jié)點(diǎn)，則可以通過(guò)一個(gè)函數(shù)來(lái)表示節(jié)點(diǎn)的狀態(tài)：

(1)

例如在t=0時(shí)觀測(cè)快照的節(jié)點(diǎn)狀態(tài)集合為：Ω={1,0,0,…,0}，在圖2中左方的圖為觀測(cè)快照?qǐng)D，該快照的節(jié)點(diǎn)狀態(tài)集合表示為：

Ω={0,0,0,1,0,0,0,2,0,1}

1.3 信息傳播過(guò)程

定義1 從0時(shí)刻到T時(shí)刻，信息傳播的過(guò)程為：

Φ(0→T)={Φ(t):0≤t≤T}

(2)

其含義為每一個(gè)時(shí)間戳的節(jié)點(diǎn)狀態(tài)集合的集合，同時(shí)為了將信息傳播過(guò)程中的節(jié)點(diǎn)狀態(tài)與觀測(cè)到的快照的狀態(tài)信息對(duì)應(yīng)起來(lái)，定義一個(gè)映射函數(shù)：

(3)

如果在某一時(shí)刻觀測(cè)到的快照的狀態(tài)與某一個(gè)傳播過(guò)程的狀態(tài)完全相同，即Γ(Φ(t))=Ω成立，則稱(chēng)這是一個(gè)可能的傳播過(guò)程，這個(gè)傳播過(guò)程從0時(shí)刻到t時(shí)刻最終的狀態(tài)與快照狀態(tài)一致。舉個(gè)例子，在圖2的傳播過(guò)程中，左方的圖是某時(shí)刻觀測(cè)到的網(wǎng)絡(luò)拓?fù)洇福谏墓?jié)點(diǎn)表示處于I狀態(tài),灰色節(jié)點(diǎn)表示處于O狀態(tài)，白色節(jié)點(diǎn)表示處于S狀態(tài)或是R狀態(tài)的節(jié)點(diǎn)。右方的圖表示某一信息從0時(shí)刻到t時(shí)刻的傳播過(guò)程，當(dāng)t=4時(shí)網(wǎng)絡(luò)拓?fù)渑c觀測(cè)到的快照的拓?fù)涞臓顟B(tài)信息完全吻合，于是稱(chēng)該過(guò)程是一個(gè)可能的傳播過(guò)程。

2 謠言源頭估計(jì)器

2.1 極大似然估計(jì)器

(4)

其中，Ρr(Φ(0→T)|s*=v)表示當(dāng)起始節(jié)點(diǎn)v為給定的源頭時(shí)，形成傳播過(guò)程Φ(0→T)的概率，而Φ(0→T):Γ(Φ(t)=Ω)表示以節(jié)點(diǎn)v為起點(diǎn)所有可能的信息傳播過(guò)程，即這些過(guò)程在t時(shí)刻的節(jié)點(diǎn)狀態(tài)與觀察到的快照Ω的狀態(tài)相同。

但是，假設(shè)傳播過(guò)程執(zhí)行了t個(gè)時(shí)間戳，在觀測(cè)快照拓?fù)洇斧@取了I和O狀態(tài)的節(jié)點(diǎn)一共有N個(gè)，則可能的信息傳播過(guò)程至少有tN個(gè)，要解決這個(gè)指數(shù)級(jí)別計(jì)算問(wèn)題十分困難，所以下面給出最優(yōu)信息傳播過(guò)程的概念，來(lái)化簡(jiǎn)這個(gè)問(wèn)題。

2.2 基于最優(yōu)信息傳播過(guò)程的估計(jì)器

為了能夠簡(jiǎn)化信息源溯源問(wèn)題，參考文獻(xiàn)[15]，可以通過(guò)構(gòu)建最優(yōu)信息傳播過(guò)程，來(lái)降低極大似然溯源估計(jì)器的復(fù)雜度。

定義2 一個(gè)最可能在[0，T]時(shí)間內(nèi)形成觀測(cè)快照的拓?fù)洇傅男畔鞑ミ^(guò)程稱(chēng)為最優(yōu)信息傳播過(guò)程。表達(dá)式為：

(5)

其中,t*是最優(yōu)信息傳播過(guò)程的傳播時(shí)間。規(guī)定能形成最優(yōu)傳播過(guò)程的起始節(jié)點(diǎn)作為信息源的估計(jì)值，即基于最優(yōu)傳播過(guò)程的源頭估計(jì)器。簡(jiǎn)單地說(shuō)，最優(yōu)信息傳播過(guò)就是一個(gè)最有可能導(dǎo)致最終觀測(cè)快照的感染過(guò)程。

3 基于最優(yōu)信息傳播過(guò)程的溯源方法

3.1 Jordan感染中心

在對(duì)該檢測(cè)方法進(jìn)行分析前，參考文獻(xiàn)[15]給出拓?fù)鋱D中節(jié)點(diǎn)性質(zhì)的定義。

定義3 在觀測(cè)快照的拓?fù)洇钢?，使用d(v,u)表示任意2節(jié)點(diǎn)v和u的最短距離，任意節(jié)點(diǎn)v到距離它最遠(yuǎn)的I狀態(tài)或是O狀態(tài)節(jié)點(diǎn)的距離為該節(jié)點(diǎn)感染偏心率，表達(dá)式如下：

(6)

其中v∈V，VΙ表示快照Ω中I狀態(tài)和O狀態(tài)節(jié)點(diǎn)的集合。再根據(jù)喬丹中心的定義，給出喬丹感染中心的概念，即快照拓?fù)洇钢芯哂凶钚「腥酒穆实墓?jié)點(diǎn)，表達(dá)式為：

(7)

3.2 最優(yōu)信息傳播持續(xù)時(shí)間

本節(jié)將通過(guò)定理1表述在謠言傳播的網(wǎng)絡(luò)中，一個(gè)最優(yōu)信息傳播過(guò)程的持續(xù)時(shí)間近似于該過(guò)程起始節(jié)點(diǎn)的感染偏心率，以及信息傳播過(guò)程持續(xù)的時(shí)間越長(zhǎng)，信息傳播過(guò)程發(fā)生的概率就會(huì)越低。且本文將針對(duì)無(wú)限的正則樹(shù)網(wǎng)絡(luò)構(gòu)建溯源模型，因?yàn)樵谕ǔD結(jié)構(gòu)中獲取最優(yōu)信息傳播路徑還是困難的，并且在正則樹(shù)網(wǎng)絡(luò)中節(jié)點(diǎn)的度值相同且沒(méi)有回路。

(8)

(1-p1-p2)|Β′(u)|p1·q1·p2(1-p1-p2)|Β′(u)|}

(9)

下一步假設(shè)最大距離為k=n時(shí)成立，驗(yàn)證k=n+1。先將樹(shù)形網(wǎng)絡(luò)劃分為多個(gè)子樹(shù)結(jié)構(gòu)，對(duì)于每個(gè)子樹(shù)上應(yīng)用歸納假設(shè)的方法，給定一個(gè)持續(xù)時(shí)間為t+1的最優(yōu)信息傳播過(guò)程，總是能構(gòu)建出一個(gè)同源且持續(xù)時(shí)間為t的信息傳播過(guò)程，其發(fā)生概率更大。如式(10)所示。

(10)

3.3 感染偏心率

本節(jié)將證明在網(wǎng)絡(luò)拓?fù)渲?，最?yōu)信息傳播過(guò)程的起始節(jié)點(diǎn)的感染偏心率越小則該信息傳播過(guò)程的發(fā)生概率就越大。

(11)

(12)

根據(jù)該過(guò)程，總是能構(gòu)建出一個(gè)發(fā)生概率更高的信息傳播過(guò)程且它的起始節(jié)點(diǎn)uj的感染偏心率更小。其發(fā)生概率的表達(dá)式為：

(13)

根據(jù)上述不等式易知式(13)>式(12)，即不等式(10)獲證，定理2證畢。

3.4 謠言源頭估計(jì)值

本節(jié)將說(shuō)明Jordan感染中心是最優(yōu)信息傳播過(guò)程的源頭，且可以作為謠言源頭的估計(jì)值。

根據(jù)以上3個(gè)定理可知，最優(yōu)信息傳播過(guò)程的源頭可以作為謠言源頭的估計(jì)值，且該值近似于網(wǎng)絡(luò)拓?fù)鋱D中的Jordan感染中心。

4 實(shí)驗(yàn)仿真及分析

4.1 反向信息傳播算法

根據(jù)上文證明可知，評(píng)估源頭需要先找到拓?fù)鋱D中所有節(jié)點(diǎn)的感染偏心率，再進(jìn)一步找到Jordan感染中心，根據(jù)文獻(xiàn)[15]中RI算法，本文提出針對(duì)于SIOR模型的反向信息傳播算法。

算法1 反向信息傳播算法

輸入：節(jié)點(diǎn)集合VI和網(wǎng)絡(luò)拓?fù)洇?/p>

步驟1 初始化2個(gè)集合，一個(gè)為記錄發(fā)送信息的節(jié)點(diǎn)sent_list，一個(gè)為記錄接收信息的節(jié)點(diǎn)receive_list，并且為所有節(jié)點(diǎn)加入一個(gè)記錄節(jié)點(diǎn)ID的數(shù)組，一個(gè)計(jì)數(shù)器及一個(gè)總時(shí)間屬性。并讓系統(tǒng)的時(shí)間t=1，將所有VI中的節(jié)點(diǎn)加入到sent_list中。

步驟2 遍歷sent_list中的節(jié)點(diǎn)，判斷它們的鄰居節(jié)點(diǎn)是否為第一次收到ID信息，如果是則記錄該ID到節(jié)點(diǎn)的數(shù)組中，同時(shí)更新計(jì)數(shù)器以及時(shí)間和屬性，并把節(jié)點(diǎn)更新到receive_list中。如果計(jì)數(shù)器的值等于VI中節(jié)點(diǎn)數(shù)量，表明該節(jié)點(diǎn)可以作為可能的估計(jì)值并加入到結(jié)果集中，更新循環(huán)結(jié)束標(biāo)志。當(dāng)遍歷完一輪后，系統(tǒng)時(shí)間t=t+1。最后將receive_list中的節(jié)點(diǎn)更新到sent_list中。如果循環(huán)沒(méi)結(jié)束，重復(fù)步驟2，否則進(jìn)入步驟3。

步驟3返回結(jié)果集，如果存在多個(gè)節(jié)點(diǎn)，返回總時(shí)間最小的節(jié)點(diǎn)，該節(jié)點(diǎn)就是拓?fù)浣Y(jié)構(gòu)中的Jordan感染中心。

4.2 實(shí)驗(yàn)評(píng)估標(biāo)準(zhǔn)與數(shù)據(jù)集

為了驗(yàn)證求解Jordan感染中心的(Jordan Centrality， JC)反向信息傳遞算法的有效性，本文將與其他中心性算法進(jìn)行比較，包括度中心性[20](Degree Centrality， DC)，接近中心性[21](Closeness Centrality， CC)，中介中心性[21](Between Centrality， BC)。并且采取表2所述的網(wǎng)絡(luò)數(shù)據(jù)集，比較算法的檢測(cè)效率。同時(shí)為了更好地描述實(shí)驗(yàn)的結(jié)果，本文采用文獻(xiàn)[22]中溯源的衡量標(biāo)準(zhǔn)。

表2 網(wǎng)絡(luò)數(shù)據(jù)集

1)檢測(cè)準(zhǔn)確率(Detection Rate)。

檢測(cè)準(zhǔn)確率表示多次執(zhí)行算法后，正確找出源頭的次數(shù)與總次數(shù)的比值。

2)檢測(cè)誤差(Detection Error)。

檢測(cè)誤差表示算法得出的估計(jì)值與真實(shí)源頭之間最短距離的平均值。

4.3 實(shí)驗(yàn)結(jié)果及數(shù)據(jù)分析

本文首先在不同度值的正則樹(shù)形網(wǎng)絡(luò)中比較3種算法的檢測(cè)準(zhǔn)確性。分別構(gòu)造度值為2～6的正則樹(shù)，在網(wǎng)絡(luò)中隨機(jī)選取一個(gè)節(jié)點(diǎn)作為謠言源頭，對(duì)于每種度值進(jìn)行模擬傳播過(guò)程1000次，其中對(duì)于感染概率p1隨機(jī)從(0,1)中選取，對(duì)于恢復(fù)概率q1與封號(hào)概率o1從(0,p1)中選取，而對(duì)于概率p2與o2盡可能取值偏小，選取觀測(cè)快照的時(shí)間在區(qū)間[3,10]中，這主要是為了保證有足夠多的節(jié)點(diǎn)被觀測(cè)到，且讓正則樹(shù)盡可能保持無(wú)限大。結(jié)果如圖3所示?？梢钥闯觯瑢?duì)于每種度值的正則樹(shù)形網(wǎng)絡(luò)JC算法的溯源準(zhǔn)確度高于其他中心性算法，由于正則樹(shù)中節(jié)點(diǎn)的度值相同，所以DC算法準(zhǔn)確率偏低。且當(dāng)度值為6時(shí)，JC算法溯源準(zhǔn)確率達(dá)到了61%。

圖3 正則樹(shù)網(wǎng)絡(luò)中實(shí)驗(yàn)結(jié)果

接下來(lái)，本文在復(fù)雜網(wǎng)絡(luò)中進(jìn)行對(duì)比實(shí)驗(yàn)，選取小世界網(wǎng)絡(luò)[20]，構(gòu)建3000個(gè)節(jié)點(diǎn)和12000條邊。為了保證傳播能在一個(gè)足夠大的網(wǎng)絡(luò)中進(jìn)行，將選取盡可能小的概率，其中對(duì)于感染概率p1隨機(jī)從(0,0.05)中選取，對(duì)于恢復(fù)概率q1與封號(hào)概率o1從(0,p1)中取，而對(duì)于概率p2與o2盡可能取值偏小，獲取觀測(cè)快照的時(shí)間選定在觀測(cè)圖中感染節(jié)點(diǎn)超過(guò)100個(gè)時(shí)，進(jìn)行1000次模擬。實(shí)驗(yàn)結(jié)果如圖4所示，不難看出，JC算法的溯源距離主要分布在0～1跳內(nèi)，而傳統(tǒng)中心性主要分布在1～5跳內(nèi)，0跳時(shí)，JC的準(zhǔn)確率為46.2%。

圖4 小世界網(wǎng)絡(luò)中實(shí)驗(yàn)結(jié)果

本文下一步在真實(shí)網(wǎng)絡(luò)中進(jìn)行模擬實(shí)驗(yàn)，在Facebook網(wǎng)絡(luò)、Internet Autonomous Systems網(wǎng)絡(luò)以及LastFM Asia Social網(wǎng)絡(luò)中進(jìn)行傳播模擬，同樣為了保證傳播過(guò)程能在一個(gè)足夠大的網(wǎng)絡(luò)中進(jìn)行，概率與快照觀測(cè)時(shí)間選取與前一部分小世界網(wǎng)絡(luò)中實(shí)驗(yàn)配置相同，進(jìn)行1000次模擬，實(shí)驗(yàn)結(jié)果如圖5所示。很容易看出JC算法在不同網(wǎng)絡(luò)中檢測(cè)出的平均誤差距離均要小于CC和BC檢測(cè)算法。由于真實(shí)網(wǎng)絡(luò)中存在較多的邊，網(wǎng)絡(luò)中存在度值較大的節(jié)點(diǎn)，因此謠言擴(kuò)散更快，溯源準(zhǔn)確率偏低。對(duì)比于小世界網(wǎng)絡(luò)，其節(jié)點(diǎn)度值平均，JC算法檢測(cè)更加準(zhǔn)確。

圖5 真實(shí)世界網(wǎng)絡(luò)中實(shí)驗(yàn)結(jié)果

最后，本文在度為3的正則樹(shù)網(wǎng)絡(luò)中進(jìn)行SIR模型與SIOR模型的溯源對(duì)比實(shí)驗(yàn)，觀察是否導(dǎo)致檢測(cè)效率上的差異。令2個(gè)實(shí)驗(yàn)中感染概率p1相同，恢復(fù)概率q1與封禁概率o1一致，而對(duì)于概率p2與o2盡可能取值偏小，每組執(zhí)行2000次模擬，實(shí)驗(yàn)結(jié)果如圖6所示，可以看出，不論是JC或CC算法，SIOR模型的檢測(cè)誤差均低于SIR模型下的檢測(cè)誤差。所以加強(qiáng)對(duì)網(wǎng)絡(luò)中傳播謠言節(jié)點(diǎn)的檢測(cè)能力，可以提高溯源效率。

圖6 2種模型的對(duì)比實(shí)驗(yàn)結(jié)果

5 結(jié)束語(yǔ)

本文基于SIR模型提出SIOR模型對(duì)謠言溯源進(jìn)行研究，證明了在SIOR模型中，最優(yōu)信息傳播過(guò)程的起始節(jié)點(diǎn)可以作為源頭的估計(jì)值，并且近似于拓?fù)浣Y(jié)構(gòu)中的Jordan感染中心。本文還提出了針對(duì)SIOR模型的反向信息傳播算法，可以找出網(wǎng)絡(luò)拓?fù)渲械腏ordan感染中心，即源節(jié)點(diǎn)的估計(jì)值。最后實(shí)驗(yàn)結(jié)果顯示該溯源方法優(yōu)于其他中心性溯源方法，且對(duì)于封禁隔離狀態(tài)的加入，一定程度上有利于源頭的檢測(cè)。