在線社交網絡中的多主題謠言溯源

戴樹興,夏正友

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

0 引 言

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

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

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

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

1 相關工作

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

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

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

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

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

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

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

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

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

2.1 獨立級聯模型

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

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

2.2 多主題獨立級聯模型

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

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

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

2.3 問題描述

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

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

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

定理1:基于多主題獨立級聯模型的k-可疑節點問題是NP難的。

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

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

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

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

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

接下來需要證明目標函數是單調且子模的。

定理2:多主題獨立級聯模型下的目標函數φ(·)是單調遞增的子模函數。

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

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

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

算法1:貪婪算法

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

輸出:k個最可疑節點

I←φ

fori=1 toq

forj=1 tok

foru∈SiIi

form=1 toR

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

end

end

end

end

ReturnI

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

3 實 驗

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

3.1 實驗設置

表1 數據集

實驗將貪婪算法與最大度算法和隨機算法進行了比較。結果表明,在三個不同的真實數據集上以及在不同謠言主題數量的情況下,貪婪算法的表現都要優于最大度算法以及隨機算法。

3.2 實驗結果

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

3.2.1 檢測概率

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

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

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

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

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

3.2.2 誤差距離

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

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

圖2 不同數據集和算法下的誤差距離

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

圖3 不同算法在不同數據集下的平均誤差距離

圖3顯示了不同算法在不同數據集下的平均誤差距離,進行1 000次蒙特卡羅模擬后取平均值。當q=2時,在三種數據集下的平均誤差距離分別為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跳。可以看出貪婪算法明顯優于其他算法。

4 結束語

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

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

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