郭宏剛 楊 芳

1(河北師范大學(xué)計算機與網(wǎng)絡(luò)空間安全學(xué)院 河北 石家莊 050024) 2(河北師范大學(xué)河北省網(wǎng)絡(luò)與信息安全重點實驗室 河北 石家莊 050024) 3(河北師范大學(xué)河北省供應(yīng)鏈大數(shù)據(jù)分析與數(shù)據(jù)安全工程研究中心 河北 石家莊 050024) 4(河北公安警察職業(yè)學(xué)院警務(wù)科研處 河北 石家莊 050091)

0 引 言

隨著移動互聯(lián)網(wǎng)的普及，在線社交網(wǎng)絡(luò)實現(xiàn)了飛速發(fā)展，從早期的Facebook和職場社交“l(fā)inkedin”到近期風靡全球的短視頻分享網(wǎng)絡(luò)“抖音”等，在線社交網(wǎng)絡(luò)已經(jīng)延伸至人們娛樂、工作和生活之中[1]，成為人類社會信息交流的一個重要方式。在線社交網(wǎng)絡(luò)給人們交流帶來了極大的便利，但也加速了不良輿論、不良廣告及謠言的傳播與擴散，對公共安全及社會經(jīng)濟造成不可忽略的破壞[2]。

謠言的網(wǎng)絡(luò)傳播機制與生物病毒的傳染病模型存在許多相似之處，研究人員隨之采用傳染病模型研究謠言的傳播和擴散過程[3]。文獻[4]利用謠言在人類社區(qū)中的傳播方式與病毒傳播類似的特點，將微博社區(qū)用戶抽象為網(wǎng)絡(luò)中的節(jié)點，從宏觀角度研究謠言在網(wǎng)絡(luò)中的傳播機理構(gòu)造微博消息傳播網(wǎng)。雖然傳染病模型與謠言傳播十分相似，但一部分人員在謠言傳播中會對謠言進行糾正，對謠言傳播產(chǎn)生弱化的效果，傳染病模型則不包含該機制。文獻[5]對傳染病模型進行了修改，補充了用戶正面觀點和反面觀點分別對謠言的促進和弱化機制，并將模型的模擬結(jié)果與Twitter的真實數(shù)據(jù)進行了比較，實現(xiàn)了較好的準確性。傳染病模型的易感人群通過接觸感染者成為新感染者，而社交網(wǎng)絡(luò)用戶通過理性判斷決定是否傳播謠言或是只閱讀謠言，因此謠言傳播中的用戶具有很高的自主性和獨立性。

為了提高謠言傳播模型的準確性，文獻[6]提出基于謠言接受概率函數(shù)的謠言傳播模型CASR(Credulous Affected Spreader Rationals)，CASR模型的謠言接收概率函數(shù)考慮了正負影響的媒介效應(yīng)，很好地模擬了謠言的傳播過程。文獻[7]基于復(fù)雜網(wǎng)絡(luò)提出了謠言傳播模型，并且給出了最大化謠言傳播的方法。雖然文獻[6-7]對謠言傳播的模擬效果好于基于傳染病的模型，但這兩個模型僅考慮了單一的社交網(wǎng)絡(luò)，無法用于跨社交網(wǎng)絡(luò)的謠言傳播分析。

跨社交網(wǎng)絡(luò)轉(zhuǎn)發(fā)和分享消息已經(jīng)成為當前十分普遍的社交內(nèi)容傳播形式，而現(xiàn)有的主要謠言傳播模型尚未有效支持跨社交網(wǎng)絡(luò)的謠言傳播[8]。本文提出一種基于影響力分級的跨社交網(wǎng)絡(luò)謠言傳播模型，通過模型可計算和預(yù)測網(wǎng)絡(luò)的謠言傳播趨勢，并且基于該模型設(shè)計了貪婪的謠言抑制方法。對于大規(guī)模的社交網(wǎng)絡(luò)，為網(wǎng)絡(luò)的每個節(jié)點建立傳播路徑會產(chǎn)生巨大的計算負擔，本文借助影響力排名的結(jié)果，為傳播模型保留高影響力節(jié)點的傳播路徑，忽略低影響力節(jié)點的傳播路徑，由此降低謠言傳播模型的復(fù)雜度，并且降低謠言抑制算法的計算成本。

1 跨網(wǎng)絡(luò)謠言傳播模型

傳統(tǒng)社交網(wǎng)絡(luò)的傳播模型將網(wǎng)絡(luò)中用戶的傳播能力考慮為相等值，并未考慮影響力差異對謠言傳播不同的推動作用[9]。本文根據(jù)社交網(wǎng)絡(luò)拓撲結(jié)構(gòu)的局部連接密度評估每個節(jié)點的影響力，并且將節(jié)點按影響力排名，考慮影響力強弱對謠言擴散的不同推動力。

1.1 社交影響力排名

網(wǎng)絡(luò)中目標節(jié)點的鄰居數(shù)量(即密度)能夠反映節(jié)點的重要性和影響力，本文基于節(jié)點在網(wǎng)絡(luò)拓撲中的位置和結(jié)構(gòu)信息來評估節(jié)點的影響力。具體而言，分析用戶與鄰居節(jié)點間的拓撲結(jié)構(gòu)相似性，相似的用戶分為同一級影響力，將用戶按影響力進行聚類處理。

將社交網(wǎng)絡(luò)表示為圖G=(V,E)，用戶集為V={v1,v2,…,v|V|}，用戶關(guān)系表示為邊E={e1,e2,…,e|E|}。設(shè)Ni為節(jié)點vi的鄰居集，將鄰居數(shù)量作為vi的度，記為di。節(jié)點與鄰居之間的關(guān)系視為用戶影響力的一個決定因素，如果鄰居節(jié)點間連接較為密集，那么消息容易在小范圍內(nèi)傳播，導(dǎo)致消息的大規(guī)模擴散能力降低，因此鄰居節(jié)點之間交互過強對該節(jié)點的影響力具有負面影響。通過式(1)計算節(jié)點vi的局部聚類系數(shù)：

(1)

局部聚類系數(shù)統(tǒng)計了節(jié)點與每個鄰居的相同鄰居數(shù)量，節(jié)點間相關(guān)性的度量方法是局部分簇系數(shù)的一個關(guān)鍵因素。采用外部聚類系數(shù)排名度量(External Clustering Ranking Measure,ECRM)[10]評估目標節(jié)點與其鄰居之間的影響力等級。以圖1為例描述ECRM方法，圖中包含3個shell，第1次迭代選擇圖中度最小的節(jié)點，記為一級節(jié)點，第2次迭代從剩下的節(jié)點中選擇度最小的節(jié)點，記為二級節(jié)點，如此迭代處理，直至所有節(jié)點被分配級別。例如：圖中節(jié)點8和節(jié)點9均與第三級連接，因此第三級是這兩個節(jié)點的共性，節(jié)點8和節(jié)點9組成第4級。

圖1 ECRM方法的示意圖

將網(wǎng)絡(luò)分級后，根據(jù)鄰居等級計算每個節(jié)點vi的shell向量。

定義1滿足以下關(guān)系的向量稱為節(jié)點vi的shell向量：

(2)

式中：|Ni(k)|表示節(jié)點vi第k級的鄰居數(shù)量；f為網(wǎng)絡(luò)的最大級數(shù)。

在圖1的實例中，節(jié)點7-節(jié)點9的shell向量分別為：SV7={0,0,0,2,0,2,0},SV8={0,1,1,1,1,0,0},SV9={0,0,1,1,1,0,0}。采用皮爾森相關(guān)系數(shù)計算shell向量間的相關(guān)性，計算式為：

(3)

定義2節(jié)點vi的shell聚類系數(shù)定義為：

(4)

式中：第1項為相關(guān)系數(shù)；第2項為節(jié)點的度。節(jié)點vi與每個鄰居之間的相關(guān)性越高，對vi傳播能力的負面影響越大，(2-Ci,j)計算了節(jié)點vi的shell聚類系數(shù)。節(jié)點的度也是shell聚類系數(shù)的一部分，max(d)表示社交網(wǎng)絡(luò)圖的最大度。

運用鄰居規(guī)則[11]提高影響力節(jié)點的準確性，首先計算節(jié)點的CRM(Clustering Ranking Measure)：

(5)

式中：SCC為shell聚類系數(shù)。

對所有鄰居的CRM求和，獲得節(jié)點vi的ECRM：

(6)

算法1為節(jié)點影響力排名算法。首先通過k-shell算法為每個節(jié)點分級，通過式(2)計算每個節(jié)點的shell向量，再通過式(3)計算節(jié)點vi和vj之間的相關(guān)性Ci,j，然后計算vi的shell聚類系數(shù)SCCi。最終根據(jù)ECRM分數(shù)將節(jié)點按影響力降序排列。

算法1節(jié)點影響力排名算法

輸入：社交網(wǎng)絡(luò)圖G=(V,E)。

輸出：節(jié)點的影響力排名Lin。

1.通過k-shell算法為每個vi分配IT(vi)；

//分配等級

2.foreachifrom 1 to |V| do

3.計算SVi;

//式(2)

4.end for

5.foreachifrom 1 to |V|

6.SCCi←0;

7.foreachvjinNido

8.計算Ci,j;

//式(3)

10.end for

11.end for

12.foreachifrom 1 to |V| do

13.CRMi=0;

14.foreachvjinNido

15.CRMi=CRMi+SCCj;

16.end for

17.end for

18.foreachifrom 1 to |V|

19.ECRMi=0;

20.foreachvjinNido

21.ECRMi=ECRMi+CRMj;

22.end for

23.end for

24.將節(jié)點按ECRM分數(shù)降序排列生成Lin;

1.2 謠言傳播模型

線上社交網(wǎng)絡(luò)的一個用戶通過社交賬號在某個社交網(wǎng)絡(luò)發(fā)布消息、視頻或者圖像等內(nèi)容，關(guān)注該賬號的用戶將收到通知并閱讀該內(nèi)容。各大社交網(wǎng)絡(luò)均支持用戶跨網(wǎng)絡(luò)轉(zhuǎn)發(fā)或分享內(nèi)容，導(dǎo)致一些熱點內(nèi)容可能被廣泛傳播。圖2所示是消息跨社交網(wǎng)絡(luò)傳播的示意圖。設(shè)I={0,1,2,…,m}為社交網(wǎng)絡(luò)的標識集，每個編號對應(yīng)一個社交網(wǎng)絡(luò)，如：0表示微博，1表示微信。將標識符為j的社交網(wǎng)絡(luò)記為OSNj，謠言發(fā)布者在OSNj發(fā)布謠言內(nèi)容，然后在其他網(wǎng)絡(luò)選擇“種子用戶”，使謠言在其他網(wǎng)絡(luò)擴散，將被選擇的社交網(wǎng)絡(luò)記為TOSN。假設(shè)每個用戶的ID跨社交網(wǎng)絡(luò)唯一，每個用戶記為i∈OSNTOSN，在OSNj中關(guān)注用戶i的集合記為F(i)j。

圖2 跨社交網(wǎng)絡(luò)消息傳播示意圖

定義3將閱讀用戶i所發(fā)布謠言的人數(shù)稱為謠言到達數(shù)。

假設(shè)用戶A被100個人關(guān)注，其中50個人閱讀了A發(fā)布的謠言，那么其謠言到達數(shù)為50。本文利用謠言到達數(shù)來評估謠言的傳播力，為每個用戶分配一個權(quán)重表示該用戶在謠言傳播中的貢獻。用戶i的謠言到達數(shù)σ(i)計算為：

(7)

定義4將用戶集S中每個用戶i的謠言到達數(shù)總和稱為謠言到達總數(shù)。用戶集S的謠言到達總數(shù)計算式為：

(8)

用戶集S的傳播力可計算為：

(9)

(10)

(11)

(12)

(13)

在Φ′(S)的定義中存在一個問題：該定義并未考慮父節(jié)點和子節(jié)點間的依賴關(guān)系，設(shè)βj,i表示子節(jié)點j對父節(jié)點i的貢獻，那么包含父-子節(jié)點依賴關(guān)系的傳播力計算為：

(14)

集合S的影響力Φ(S)修改為：

Φ(S)=Φ′(S)-Φ″(S)

(15)

(16)

定義一個鄰接矩陣A=[aji]標記子節(jié)點j是否連接父節(jié)點i，矩陣元素aji定義為：

(17)

(18)

計算S集合所有用戶的傳播力σ(i)之和即可獲得Φ′(S)，然后為Φ′(S)增加父-子依賴關(guān)系的信息。設(shè)計一個矩陣Θ=[?ji]，其對角元素表示增加一個用戶產(chǎn)生的增益，其他元素為父-子依賴關(guān)系的相關(guān)信息，矩陣Θ的元素?ji定義為：

(19)

(20)

式中：Φ′(S)表示集合S的謠言到達數(shù)。

2 謠言抑制方法設(shè)計

設(shè)N為目標社交網(wǎng)絡(luò)中所有用戶的數(shù)量，xi∈{0,1}表示用戶i是否被選擇。將謠言抑制問題建模為以下的最小化問題：

(21)

算法2為基于貪婪的謠言抑制算法，輸入為可操控的用戶數(shù)量和可操控的社交網(wǎng)絡(luò)數(shù)量。貪婪算法主要通過依次將用戶加入操控用戶集S中，觀察謠言到達數(shù)是否降低，最終找到最小化謠言到達數(shù)的用戶集S。社交網(wǎng)絡(luò)可以對S中的用戶進行合理的處理，控制謠言的擴散。

算法2謠言抑制算法

輸入：目標用戶數(shù)量N，社交網(wǎng)絡(luò)數(shù)量D。

輸出：用戶集S。

1.S←NULL;

//初始化S

2.while |S|≤Ndo

3.inc′←0;

4.R←N-|S|;

5.foreachiin {N-S} do

//遍歷S集以外的用戶

6.ifR==Dthen

//檢查是否滿足跨網(wǎng)絡(luò)約束

//未能減少網(wǎng)絡(luò)數(shù)量

9.end if

10.end if

11.inc←Φ′(S∪{i})-Φ′(S);

//計算謠言到達數(shù)

12.ifinc>inc′ then

13.inc′←inc;

14.u′←i;

15.end if

16.end for

17.S←S∪{u′};

18.end while

3 仿真實驗與結(jié)果分析

實驗環(huán)境為PC機：i7- 9850H處理器，2.6 GHz主頻，32 GB內(nèi)存，編程環(huán)境為MATLAB2017b。

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

從Twitter、微博和YouTube收集了3組數(shù)據(jù)集，分別構(gòu)成兩個單一網(wǎng)絡(luò)benchmark數(shù)據(jù)集和一個跨社交網(wǎng)絡(luò)(Cross Social Networks,CSN)benchmark數(shù)據(jù)集，詳細信息如表1所示。Twitter數(shù)據(jù)集共包含458個關(guān)于“Charlie Hebdo攻擊”事件的謠言，微博數(shù)據(jù)集共包含32個關(guān)于“河北省石家莊市”的謠言。CSN數(shù)據(jù)集由Twitter數(shù)據(jù)集和YouTube數(shù)據(jù)集組成，保留了“Charlie Hebdo攻擊”謠言從Twitter分享到Y(jié)ouTube的連接，最終CSN的Twitter數(shù)據(jù)集共包含4 540個節(jié)點和62 881個有向連接，YouTube數(shù)據(jù)集的相關(guān)節(jié)點包含5 703個節(jié)點和83 245個有向連接。

表1 Benchmark數(shù)據(jù)集基本信息

3.2 謠言傳播模型的實驗

線性閾值模型(Linear Threshold Model, LT)[12]和Epidemic模型[13]是兩個主流的謠言傳播模型。LT模型是一種基于概率的微觀模型，主要分析了節(jié)點在局部區(qū)域的相關(guān)性和相互影響，從而模擬出謠言的傳播趨勢，該模型需要設(shè)立傳播指數(shù)參數(shù)k，將Twitter數(shù)據(jù)集的k設(shè)為2.5，微博數(shù)據(jù)集的k設(shè)為1.5。Epidemic模型是一種基于傳染病模型的宏觀模型，通過感染人群將謠言不斷地擴散到全網(wǎng)，該模型需要網(wǎng)絡(luò)的聚類系數(shù)參數(shù)，將Twitter數(shù)據(jù)集的聚類系數(shù)設(shè)為0.512 3，微博數(shù)據(jù)集的聚類系數(shù)設(shè)為0.076 5。

圖3為Twitter網(wǎng)絡(luò)、微博網(wǎng)絡(luò)和CSN的謠言傳播曲線。在Twitter網(wǎng)絡(luò)第6個時間步謠言出現(xiàn)第1個高峰，大約70%的用戶參與傳播謠言，在第14個時間步謠言出現(xiàn)第2個高峰，幾乎所有用戶參與傳播謠言，然后謠言的熱點開始下降，逐漸趨于平靜。LT模型成功模擬出第1個高峰，并且也幾乎模擬出第2個高峰，但LT模型僅僅模擬了傳播的上升趨勢，在峰值之后并未呈現(xiàn)下降趨勢，與實際情況不符。Epidemic模型十分粗略地模擬出了總體上升和下降趨勢，但是不包含對傳播細節(jié)的描述。本文模型準確地模擬出第1個峰值，第2個峰值出現(xiàn)的時間略遲于實際情況，另外本文模型的峰值數(shù)據(jù)低于實際情況，主要原因在于該模型為了減低復(fù)雜度，僅保留了影響力節(jié)點的傳播路徑。

(a) Twitter網(wǎng)絡(luò)的謠言傳播曲線

在微博網(wǎng)絡(luò)第2個時間步謠言出現(xiàn)第1個高峰，大約60%的用戶參與傳播謠言，在第20個時間步謠言出現(xiàn)第2個高峰，約28%的用戶參與傳播謠言，在第33個時間步謠言出現(xiàn)第3個高峰，約32%的用戶參與傳播謠言，然后謠言的熱點開始下降，逐漸趨于平靜。LT模型成功模擬出第1個高峰，LT模型僅僅模擬了傳播的上升趨勢，在峰值之后并未呈現(xiàn)下降趨勢，與實際情況不符。Epidemic模型模擬出第一個峰值的上升和下降趨勢，但不包含對傳播細節(jié)的描述。本文模型第1個峰值出現(xiàn)的時間略遲于實際情況，成功模擬出第2個峰值，另外本文模型的峰值數(shù)據(jù)低于實際情況，主要原因在于該模型為了減低復(fù)雜度，僅保留了影響力節(jié)點的傳播路徑。

由于LT模型和Epidemic模型均不支持跨網(wǎng)絡(luò)的謠言傳播，因此僅將本文模型和實際傳播情況進行了比較，如圖3(c)所示?？梢钥闯?，本文模型較為準確地模擬出了謠言跨網(wǎng)絡(luò)擴散的上升趨勢和下降趨勢，可用來預(yù)測謠言的跨網(wǎng)絡(luò)傳播趨勢，作為謠言檢測和謠言抑制的預(yù)處理步驟。

3.3 模型參數(shù)實驗

在本文模型的貪婪謠言抑制算法中需要預(yù)先確定可操作的用戶數(shù)量參數(shù)N，因此通過試錯實驗觀察不同的N值(失活節(jié)點數(shù)量)對謠言抑制效果的影響。本文算法選擇影響力高的傳播節(jié)點作為失活節(jié)點，中斷其傳播行為，由此抑制謠言的傳播。圖4所示分別為Twitter、微博和CSN網(wǎng)絡(luò)上謠言抑制實驗的結(jié)果，三組實驗表現(xiàn)出相似的現(xiàn)象，即失活的節(jié)點數(shù)量越多，謠言的下降速度越快，抑制效果越明顯。

(a) Twitter網(wǎng)絡(luò)的謠言抑制實驗

3.4 對比實驗分析

為了評估本文貪婪謠言抑制算法的有效性，選擇3個不同類型的謠言抑制算法與本文算法完成對比實驗分析，結(jié)果如圖5所示。RIM[14]是一種支持多社交網(wǎng)絡(luò)的謠言最小化傳播算法，該算法預(yù)測謠言下一步的傳播路徑，通過切斷路徑抑制謠言傳播。MRS[15]是一種單一社交網(wǎng)絡(luò)的謠言抑制方法，該方法考慮了正向意見對謠言傳播的促進作用，也考慮了反對意見對謠言的抑制作用。CSR[16]也是一種單一社交網(wǎng)絡(luò)的謠言抑制方法，該方法通過提高謠言在社區(qū)的傳播率，從而降低謠言在社區(qū)間的傳播概率。

(a) Twitter網(wǎng)絡(luò)的對比實驗

觀察Twitter網(wǎng)絡(luò)和微博兩個數(shù)據(jù)集中聽信謠言的人數(shù)比例，CSR的抑制效果差于其他三個模型，主要原因在于該模型雖然降低了社區(qū)間的傳播，但提高了社區(qū)內(nèi)的傳播，導(dǎo)致總體的傳播人數(shù)較高。本文模型和RIM模型對謠言的總體抑制效果較好，RIM模型通過對預(yù)測傳播路徑的切斷來抑制謠言傳播，本文則是通過直接失活傳播能力強的節(jié)點來抑制謠言傳播。

4 結(jié) 語

本文提出基于影響力分級的跨社交網(wǎng)絡(luò)謠言傳播模型，通過模型可計算和預(yù)測網(wǎng)絡(luò)的謠言傳播趨勢，最終基于模型設(shè)計了貪婪的謠言抑制方法。本文模型能夠較好地模擬出謠言傳播的峰值及其時間，為了降低模型的復(fù)雜度，僅保留了影響力節(jié)點的傳播路徑，導(dǎo)致峰值數(shù)據(jù)低于實際情況。另外本文模型能夠較為準確地模擬出謠言跨網(wǎng)絡(luò)擴散的上升趨勢和下降趨勢，可用來預(yù)測謠言的跨網(wǎng)絡(luò)傳播趨勢，作為謠言檢測和謠言抑制的預(yù)處理步驟。

本文模型直接通過失活一部分節(jié)點對謠言傳播進行抑制，但這會導(dǎo)致社交網(wǎng)絡(luò)用戶的滿意度降低。未來將通過增強意見領(lǐng)袖的正向言論來對謠言進行澄清，以期在抑制謠言的同時，保持用戶對社交網(wǎng)絡(luò)的滿意度。