戴樹興,夏正友

(南京航空航天大學 計算機科學與技術(shù)學院,江蘇 南京 211106)

0 引 言

現(xiàn)今人們的生活離不開網(wǎng)絡(luò),網(wǎng)絡(luò)給用戶提供信息交流的平臺。隨著手機、電腦等通信設(shè)備的快速普及,社交網(wǎng)絡(luò)平臺也逐漸開始興起,例如Twitter、Facebook、微博。用戶之間通過社交網(wǎng)絡(luò)平臺進行信息分享。同時,信息的快速傳播也會產(chǎn)生不同的影響,例如用戶可以通過網(wǎng)絡(luò)獲取天氣預報、股票市場情況變化等信息,但同樣也會受到虛假信息的影響,由于虛假信息具有新穎性,抓住人們的獵奇心理,從而導致虛假信息比真實信息具有更強的傳染性。此外,對各種各樣信息的真實性進行檢測是困難的,這導致了謠言在社交網(wǎng)絡(luò)中傳播的問題,惡意用戶發(fā)散各種不實信息,可能會影響社會的穩(wěn)定,產(chǎn)生嚴重的后果[1]。

為了確保社交平臺的公信力,以及減少錯誤信息在社交網(wǎng)絡(luò)中的影響,追蹤識別散播謠言的源頭是非常重要的一步,通過了解這些謠言源頭有助于平臺設(shè)計有效的策略遏制謠言的散播。而且感染源頭檢測技術(shù)在其他領(lǐng)域有著很多成功的應(yīng)用,例如找出污水網(wǎng)絡(luò)中的病毒、流行傳染病的最初感染者[2]。

目前謠言溯源的工作集中于對單一主題的謠言進行源頭檢測,且大部分為單源檢測,這些工作并不全面?？紤]到一個更為現(xiàn)實的場景,在同一社交網(wǎng)絡(luò)中,會有多個不同主題的謠言從多個源頭同時傳播,每個用戶可以同時接收到這些不同主題的謠言。因此,該文將單主題謠言溯源的工作拓展到多主題謠言溯源。在這種情況如何高效地對謠言源頭進行追溯是一個很有挑戰(zhàn)性的課題。經(jīng)過一段時間后,在只知道底層的社會網(wǎng)絡(luò)結(jié)構(gòu)以及時間t的感染子圖情況下,如何確定謠言的來源。要解決這個問題,需要解決幾個關(guān)鍵挑戰(zhàn)。首先,在多主題多源謠言傳播的場景下,信息是在網(wǎng)絡(luò)中如何擴散的;其次,如何確定每個感染節(jié)點為源頭的可能性;最后,對謠言源頭進行識別的方法是否有近似保證,是否會產(chǎn)生較大的偏差。

在單主題謠言傳播中,獨立級聯(lián)模型[3]被廣泛應(yīng)用于各項研究中。而多主題謠言傳播已經(jīng)有研究證明其影響是異質(zhì)的[4]。因此,需要重新證明激活節(jié)點目標函數(shù)的子模性質(zhì),子模能夠保證解的良好逼近。該文提出了一種謠言傳播的多主題獨立級聯(lián)模型,基于該模型定義了多主題謠言溯源問題,并證明了該問題是NP難的,以及目標函數(shù)具有單調(diào)、子模的性質(zhì)。從目標函數(shù)的性質(zhì)出發(fā),提出了一種基于影響力最大化的貪婪算法來進行謠言源頭識別,該算法能保證(1-1/e)的比例逼近最優(yōu)解。

1 相關(guān)工作

Shah和Zaman首次提出了謠言溯源問題[5],他們假設(shè)單一感染源在樹狀網(wǎng)絡(luò)下滿足SI模型傳播,并提出謠言中心性的概念估計謠言來源。Cai等人[6]研究了在一般傳播時間分布條件下,SI模型對單一源多次獨立網(wǎng)絡(luò)快照的檢測概率。

Xu和Chen提出一種新的源檢測方法[7],設(shè)置一些監(jiān)視器節(jié)點來獲得謠言傳播的速度,以此提出一種多項式算法計算節(jié)點的可達性并進行重要性排序。謠言源頭檢測概率取決于監(jiān)視器數(shù)量。

文獻[8]中作者在經(jīng)典傳染病模型的基礎(chǔ)上進行改進,加入了新的“辟謠者”狀態(tài),并基于貪婪算法識別源頭。文獻[9]提出一種SIOR傳染病模型,并研究了在該模型下的謠言溯源問題。文獻[10]提出一種SEIR模型,研究了基于網(wǎng)絡(luò)觀測快照下的單一來源檢測問題。

Choi等人[11]提出了基于查詢的方法,首先向節(jié)點進行一次簡單的查詢并根據(jù)回答生成網(wǎng)絡(luò)。然后使用交互式查詢,詢問節(jié)點從誰接收到謠言。該方法保證了在規(guī)則樹網(wǎng)絡(luò)中的檢測概率。文獻[12]中,作者在基于監(jiān)視的觀察下,通過監(jiān)視器節(jié)點發(fā)送“反謠言”,并用最大后驗估計器來檢測謠言來源。

在多源檢測工作中,Wang[13]首次將謠言中心度拓展到了多源檢測。Dong等人[14]提出了一種基于深度學習的謠言溯源模型,在缺乏底層網(wǎng)絡(luò)信息傳播模型的先驗知識下,依然能檢測到多個謠言來源。

Nguyen提出了基于排名和優(yōu)化的方法將感染節(jié)點按可疑性排序,找出前k個可疑節(jié)點[15]。李城等人[16]基于最長公共子序列改進了LCS算法。

葉增煒等[17]提出了一種基于有責量和免責量的謠言溯源方法。廖藝等人[18]基于譜優(yōu)化社區(qū)劃分算法將感染子圖劃分為兩個社區(qū)后尋找謠言來源。

2 謠言來源檢測和問題描述

在這一節(jié)內(nèi)容中,首先將介紹謠言的基本傳播模型,然后給出了改進后的多主題謠言傳播模型,接著描述了相關(guān)問題的描述以及證明。該文將獨立級聯(lián)模型拓展到多主題獨立級聯(lián)模型。

2.1 獨立級聯(lián)模型

在獨立級聯(lián)模型中,社交網(wǎng)絡(luò)被視作為一個有向加權(quán)圖G=(V,E),每個節(jié)點v代表不同的用戶,每條有向邊e=(u,v)∈E代表用戶u和用戶v之間的關(guān)系,每條邊會被分配一個權(quán)重p(u,v)∈[0,1],代表用戶u對用戶v的影響程度。

在謠言傳播過程中,每個節(jié)點只有兩種狀態(tài):活躍和非活躍。在時間步t時,當節(jié)點u被激活為活躍狀態(tài)時,該節(jié)點會依次向其每個鄰居v以概率p(u,v)進行謠言傳播,如果激活成功,鄰居t+1在第u時刻轉(zhuǎn)化為活躍狀態(tài)。在后續(xù)傳播過程中,節(jié)點u將不再嘗試激活其鄰居。當沒有新的節(jié)點被激活時,謠言傳播過程結(jié)束。

2.2 多主題獨立級聯(lián)模型

獨立級聯(lián)模型研究單個主題的信息傳播過程。但是考慮到多個不同主題的謠言可以同一時間傳播,同一用戶可以在短時間內(nèi)同時接收到不同主題的謠言。不同主題的謠言不僅內(nèi)容不同,傳染力也可能不同。娛樂八卦類的謠言比農(nóng)業(yè)、軍事等類型的謠言傳播更廣,影響人數(shù)更多。而且同一用戶傳播不同類型的謠言時,對鄰居產(chǎn)生的影響也可能不同。

因此,在多主題謠言傳播的情況下,需要重新對信息擴散過程進行建模。而獨立級聯(lián)模型并不能處理這種情況,因為它很難體現(xiàn)不同主題之間的復雜相關(guān)性。已經(jīng)有相關(guān)研究證明,當采用多主題信息級聯(lián)時,計算激活節(jié)點的目標函數(shù)不再是子模的[19-20]。

在多主題獨立級聯(lián)模型中,在線社交網(wǎng)絡(luò)用G=(V,E,P)表示,其中V為節(jié)點集,E為邊集,且|V|=n,|E|=m。每個節(jié)點v代表不同的用戶,每條有向邊e=(u,v)∈E代表用戶u和用戶v之間的關(guān)系,每條邊會被分配一個初始影響權(quán)重p0(u,v)∈[0,1]代表用戶u對用戶v的影響程度。用Ni(v)表示節(jié)點v的傳入鄰居節(jié)點集,No(v)表示傳出鄰居節(jié)點集。

2.3 問題描述

該文的目標是在已知底層網(wǎng)絡(luò)結(jié)構(gòu)以及第t個時間步感染子圖的情況下找出一組節(jié)點,而這組節(jié)點被認為是最可能的謠言來源。現(xiàn)實中謠言源頭想通過影響盡可能多的用戶以達到某種目的,因此在直覺中如果能找出影響最大的一組節(jié)點,那么這組節(jié)點中為謠言來源的可能性非常大。利用這一特點,基于影響力最大化的原理將活躍集合S中每個節(jié)點根據(jù)可疑性程度進行排序,其中前k個節(jié)點被視作最可疑的節(jié)點。

定義1(k-可疑節(jié)點):在線社交網(wǎng)絡(luò)用有向加權(quán)圖G=(V,E,P)表示以及給出帶有q個主題的感染節(jié)點集S={S1,S2,…,Sq},利用多主題獨立級聯(lián)模型來模擬信息擴散過程。目標是在已知感染子圖G'=(V',E',P')時找出一組不超過k個可疑節(jié)點集A?S,使得激活節(jié)點數(shù)均值φ(G',A)=E(|σ(G',A)∩S|)最大。

一些關(guān)于影響最大化問題是NP難的證明可以在文獻[3,20-21]中找到。接下來給出在多主題獨立級聯(lián)模型下的k-可疑節(jié)點問題是NP難的證明。

定理1:基于多主題獨立級聯(lián)模型的k-可疑節(jié)點問題是NP難的。

證明:為了證明k-可疑節(jié)點問題是NP難的,用背包問題歸約到k-可疑節(jié)點問題。而背包問題是公認被證明的NP完全問題。

令π1=(X,W)是背包問題的一個實例,令π2=(G',S,k)是k-可疑節(jié)點問題的一個實例。其中S是謠言的源頭節(jié)點,k是確定的前k個可疑節(jié)點。對于接下來構(gòu)造從π1到π2的一個歸約,如圖1所示。

圖1 k-可疑節(jié)點問題到背包問題的歸約

歸約:為了構(gòu)造歸約,首先給出一個感染子圖G'=(V',E',P')使其滿足以下條件:其中存在謠言源頭集S,對每個物品的價值ci構(gòu)造一條含有ci+1個節(jié)點的簡單路徑:S→ui,1→ui,2→…→ui,ci,并設(shè)路徑的每條有向邊權(quán)重為1。對任意的ui,1都有wi=1,令k=W和M=C。M是一個正整數(shù)。接下來證明π1有解X={x1,x2,…,xn}當且僅當π2也有對應(yīng)的解A={ui,1|i=1}使φ(G,A)>M,反之亦然。

綜上可知,背包問題的解是k-可疑節(jié)點問題的解,而k-可疑節(jié)點問題的解也是背包問題的解。因此k-可疑節(jié)點問題是NP難的。

接下來需要證明目標函數(shù)是單調(diào)且子模的。

定理2:多主題獨立級聯(lián)模型下的目標函數(shù)φ(·)是單調(diào)遞增的子模函數(shù)。

2.4 基于影響力最大化的貪婪算法

前面已經(jīng)證明多主題獨立級聯(lián)模型下的k-可疑節(jié)點問題是NP難的,因此想要求最優(yōu)解是需要花費指數(shù)增長的時間,成本太高。因此,該文提出了一種求解該問題的貪婪算法。由于子模函數(shù)的性質(zhì),該算法能以(1-1/e)的比例逼近最優(yōu)解,能夠在一定程度內(nèi)保證解的質(zhì)量和精度。

在已知某一時刻的感染子圖情況下,對任意節(jié)點u,如果能感染盡可能多S中的節(jié)點,那么該節(jié)點為謠言源頭的可能性越大。以此計算并排序?qū)⑺泄?jié)點的可疑程度,最后輸出前k個最可疑的節(jié)點。算法過程如下:

算法1:貪婪算法

輸入:感染子圖G'=(V',E',P'),以及感染節(jié)點集S,模擬次數(shù)R,謠言主題數(shù)q

輸出:k個最可疑節(jié)點

I←φ

fori=1 toq

forj=1 tok

foru∈SiIi

form=1 toR

早產(chǎn)的動物在使用機械通氣進行治療的初期其炎癥反應(yīng)的程度就會上升，即使利用表面活性物質(zhì)進行治療，也會導致肺部的損傷，動物實驗的結(jié)果提示早產(chǎn)兒發(fā)生BPD可能與機械通氣之間有著密切的關(guān)聯(lián)[7]。在對早產(chǎn)兒進行機械通氣的過程中，由于參數(shù)設(shè)置的不穩(wěn)定和時間過長等因素，有可能使小氣道和肺泡的膨脹過度，而且產(chǎn)生大量炎性因子。而呼氣末壓力的降低，又會使肺單位出現(xiàn)反復的萎縮與張開，此過程構(gòu)成了對肺泡毛細血管完整性地損害。

end

end

end

end

ReturnI

為了盡可能提高算法的準確性,使用蒙特卡羅方法對多主題謠言傳播過程進行R次模擬,對節(jié)點可疑程度取平均值并取前k個節(jié)點。在時間復雜度方面,假設(shè)模擬一次多主題謠言傳播過程的時間需要O(m),謠言主題數(shù)量為q,那么總花費時間為O(Rmqk|S|)。

3 實 驗

該文分別在三個不同的真實在線社交網(wǎng)絡(luò)上進行了謠言溯源的實驗。結(jié)果表明,與其他的算法相比,貪婪算法有著更高的準確性。

3.1 實驗設(shè)置

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

實驗將貪婪算法與最大度算法和隨機算法進行了比較。結(jié)果表明,在三個不同的真實數(shù)據(jù)集上以及在不同謠言主題數(shù)量的情況下,貪婪算法的表現(xiàn)都要優(yōu)于最大度算法以及隨機算法。

3.2 實驗結(jié)果

表2和表3分別顯示謠言主題數(shù)量q=2和q=3的情況下,通過檢測概率,誤差距離以及平均誤差距離用來評估算法的性能。檢測概率是指檢測謠言來源節(jié)點數(shù)量與真實源節(jié)點數(shù)量之比。誤差距離是指檢測謠言來源節(jié)點與真實源節(jié)點的最小距離。從表2和表3可以看出,在不同謠言主題數(shù)量的情況下,貪婪算法在檢測概率、誤差距離(1跳之內(nèi))以及平均誤差距離上的表現(xiàn)都要優(yōu)于其他兩種算法。

3.2.1 檢測概率

隨著k的增大,檢測概率提高。理論上,如果k增大到與感染子圖的節(jié)點數(shù)量一致的話,那么一定包含所有真實謠言來源,但這種做法并不現(xiàn)實。所以實驗中將k的最大值設(shè)置為10。

由表2可以看出,在謠言主題數(shù)量q=2的情況下,在gemsec數(shù)據(jù)集上,貪婪算法能達到55%的成功檢測概率,而最大度算法和隨機算法分別只有45%和40%。在Slashdot 和Epinions數(shù)據(jù)集上,貪婪算法的檢測概率能達到70%,最大度算法有35%和30%的檢測概率,而隨機算法則都只有20%的檢測概率。

表2 三種算法在不同數(shù)據(jù)集上的性能對比(謠言主題數(shù)量q=2)

表3 三種算法在不同數(shù)據(jù)集上的性能對比(謠言主題數(shù)量q=3)

當q=3時,由表3可以看出,在Epinions,gemsec和Slashdot數(shù)據(jù)集上,貪婪算法的檢測概率能分別達到43.3%,53.3%和50%。最大度算法的檢測概率分別達到23.3%,26.7%和20%。而隨機算法則分別達到20%,43.3%以及16.7%。隨著謠言主題數(shù)量增加,貪婪算法依然明顯優(yōu)于最大度算法和隨機算法。

3.2.2 誤差距離

圖2顯示了不同算法在不同真實數(shù)據(jù)集下的誤差距離頻率。其中(a1,b1,c1)為謠言主題數(shù)量q=2的情況,在Epinions數(shù)據(jù)集上,貪婪算法有70%的把握能夠正確找到謠言來源,且有80%的把握保證檢測的謠言節(jié)點離真實謠言來源節(jié)點的距離在1跳之內(nèi)。而隨機算法和最大度算法分別只有65%和45%的把握。在gemsec和Slashdot數(shù)據(jù)集上,貪婪算法則分別有85%和80%的把握正確找到真實謠言來源或者只差1跳的誤差距離,隨機算法則只有45%和40%,最大度算法有75%和30%。

在謠言主題數(shù)量q=3的情況下,即圖2(a2,b2,c2)中可以看出,貪婪算法的表現(xiàn)依然出色且穩(wěn)定,在三種數(shù)據(jù)集上分別有66.7%,86.7%,86.7%的概率能夠在1跳的距離之內(nèi)找到真實謠言來源。而隨機算法則分別達到53.3%,45%,43.3%。最大度算法則分別達到36.7%,86.7%,36.7%。隨著謠言主題數(shù)量增加,貪婪算法優(yōu)于其他兩種算法。

圖2 不同數(shù)據(jù)集和算法下的誤差距離

相比于其他兩種算法,貪婪算法檢測到的大部分謠言節(jié)點離真實謠言節(jié)點的距離在1跳以內(nèi),檢測距離達到3跳或者超過3跳的節(jié)點不超過10%,表現(xiàn)穩(wěn)定且高效。隨機算法與最大度算法所檢測的謠言節(jié)點與真實謠言節(jié)點的距離隨機分布在0～3跳之間,誤差較大。

圖3 不同算法在不同數(shù)據(jù)集下的平均誤差距離

圖3顯示了不同算法在不同數(shù)據(jù)集下的平均誤差距離,進行1 000次蒙特卡羅模擬后取平均值。當q=2時,在三種數(shù)據(jù)集下的平均誤差距離分別為0.6跳、0.5跳、0.55跳。而最大度算法分別為1.40跳、0.80跳、1.70跳。隨機算法則分別為1.20跳、1.30跳、1.60跳。當q=3時,貪婪算法平均誤差距離分別為0.90跳、0.47跳、0.70跳。最大度算法分別為1.43跳、0.93跳、1.47跳。隨機算法分別為1.47跳、0.93跳、1.60跳?？梢钥闯鲐澙匪惴黠@優(yōu)于其他算法。

4 結(jié)束語

考慮到每個節(jié)點可能在同一時間收到多種類型的謠言并傳播給鄰居的情況,在傳統(tǒng)獨立級模型的基礎(chǔ)上進行了擴展,提出一種多主題謠言傳播的獨立級聯(lián)模型。在該模型下,每個節(jié)點可以被不同主題的謠言多次感染,因此需要重新定義影響力最大化的溯源問題以及相應(yīng)的目標函數(shù)。

在該模型的基礎(chǔ)上,提出了考慮影響力的k-可疑節(jié)點謠言溯源問題,即找出前k個影響力最大的節(jié)點,這些節(jié)點被認為是最有可能的謠言來源。并證明了多主題獨立級聯(lián)模型下的k-可疑節(jié)點謠言溯源問題是NP難的,以及對應(yīng)的目標函數(shù)φ(·)是單調(diào)遞增的子模函數(shù)。

提出了一種近似比為(1-1/e)的貪婪算法。實驗結(jié)果表明,在不同大型網(wǎng)絡(luò)上,貪婪算法可以有效地識別出不同謠言主題的來源。