吳 楊,吳國文,張 紅,沈士根,曹奇英

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

0 引 言

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

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

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

表1 本文所用符號

1 傳播模型

1.1 SIOR模型

謠言在社交網絡傳播的過程中，節(jié)點的狀態(tài)會發(fā)生一系列的變化，基于經典SIR模型提出的擴展型模型SIOR來研究單一信息源的溯源問題。

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

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

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

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

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

圖2 節(jié)點狀態(tài)轉化過程

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

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

1.2 觀測網絡模型

要獲取傳播過程中某一時刻的拓撲圖，定義Ω={ωv,v∈V}來表示觀測快照中節(jié)點的狀態(tài)，根據(jù)真實的情況，觀測快照是無法區(qū)分S狀態(tài)和R狀態(tài)的節(jié)點，則可以通過一個函數(shù)來表示節(jié)點的狀態(tài)：

(1)

例如在t=0時觀測快照的節(jié)點狀態(tài)集合為：Ω={1,0,0,…,0}，在圖2中左方的圖為觀測快照圖，該快照的節(jié)點狀態(tài)集合表示為：

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

1.3 信息傳播過程

定義1 從0時刻到T時刻，信息傳播的過程為：

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

(2)

其含義為每一個時間戳的節(jié)點狀態(tài)集合的集合，同時為了將信息傳播過程中的節(jié)點狀態(tài)與觀測到的快照的狀態(tài)信息對應起來，定義一個映射函數(shù)：

(3)

如果在某一時刻觀測到的快照的狀態(tài)與某一個傳播過程的狀態(tài)完全相同，即Γ(Φ(t))=Ω成立，則稱這是一個可能的傳播過程，這個傳播過程從0時刻到t時刻最終的狀態(tài)與快照狀態(tài)一致。舉個例子，在圖2的傳播過程中，左方的圖是某時刻觀測到的網絡拓撲Ω，黑色的節(jié)點表示處于I狀態(tài),灰色節(jié)點表示處于O狀態(tài)，白色節(jié)點表示處于S狀態(tài)或是R狀態(tài)的節(jié)點。右方的圖表示某一信息從0時刻到t時刻的傳播過程，當t=4時網絡拓撲與觀測到的快照的拓撲的狀態(tài)信息完全吻合，于是稱該過程是一個可能的傳播過程。

2 謠言源頭估計器

2.1 極大似然估計器

(4)

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

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

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

為了能夠簡化信息源溯源問題，參考文獻[15]，可以通過構建最優(yōu)信息傳播過程，來降低極大似然溯源估計器的復雜度。

定義2 一個最可能在[0，T]時間內形成觀測快照的拓撲Ω的信息傳播過程稱為最優(yōu)信息傳播過程。表達式為：

(5)

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

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

3.1 Jordan感染中心

在對該檢測方法進行分析前，參考文獻[15]給出拓撲圖中節(jié)點性質的定義。

定義3 在觀測快照的拓撲Ω中，使用d(v,u)表示任意2節(jié)點v和u的最短距離，任意節(jié)點v到距離它最遠的I狀態(tài)或是O狀態(tài)節(jié)點的距離為該節(jié)點感染偏心率，表達式如下：

(6)

其中v∈V，VΙ表示快照Ω中I狀態(tài)和O狀態(tài)節(jié)點的集合。再根據(jù)喬丹中心的定義，給出喬丹感染中心的概念，即快照拓撲Ω中具有最小感染偏心率的節(jié)點，表達式為：

(7)

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

本節(jié)將通過定理1表述在謠言傳播的網絡中，一個最優(yōu)信息傳播過程的持續(xù)時間近似于該過程起始節(jié)點的感染偏心率，以及信息傳播過程持續(xù)的時間越長，信息傳播過程發(fā)生的概率就會越低。且本文將針對無限的正則樹網絡構建溯源模型，因為在通常圖結構中獲取最優(yōu)信息傳播路徑還是困難的，并且在正則樹網絡中節(jié)點的度值相同且沒有回路。

(8)

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

(9)

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

(10)

3.3 感染偏心率

本節(jié)將證明在網絡拓撲中，最優(yōu)信息傳播過程的起始節(jié)點的感染偏心率越小則該信息傳播過程的發(fā)生概率就越大。

(11)

(12)

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

(13)

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

3.4 謠言源頭估計值

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

根據(jù)以上3個定理可知，最優(yōu)信息傳播過程的源頭可以作為謠言源頭的估計值，且該值近似于網絡拓撲圖中的Jordan感染中心。

4 實驗仿真及分析

4.1 反向信息傳播算法

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

算法1 反向信息傳播算法

輸入：節(jié)點集合VI和網絡拓撲Ω

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

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

步驟3返回結果集，如果存在多個節(jié)點，返回總時間最小的節(jié)點，該節(jié)點就是拓撲結構中的Jordan感染中心。

4.2 實驗評估標準與數(shù)據(jù)集

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

表2 網絡數(shù)據(jù)集

1)檢測準確率(Detection Rate)。

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

2)檢測誤差(Detection Error)。

檢測誤差表示算法得出的估計值與真實源頭之間最短距離的平均值。

4.3 實驗結果及數(shù)據(jù)分析

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

圖3 正則樹網絡中實驗結果

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

圖4 小世界網絡中實驗結果

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

圖5 真實世界網絡中實驗結果

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

圖6 2種模型的對比實驗結果

5 結束語

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