基于節(jié)點(diǎn)親密度挖掘的謠言抑制算法

田亞平，楊力，王小琴，喬雅峰

（西安電子科技大學(xué)網(wǎng)絡(luò)與信息安全學(xué)院，陜西 西安 710071）

基于節(jié)點(diǎn)親密度挖掘的謠言抑制算法

田亞平，楊力，王小琴，喬雅峰

（西安電子科技大學(xué)網(wǎng)絡(luò)與信息安全學(xué)院，陜西 西安 710071）

通過對(duì)謠言等易誤導(dǎo)大眾輿論的信息傳播進(jìn)行抑制，從而實(shí)現(xiàn)對(duì)謠言、錯(cuò)誤輿論等負(fù)面信息的控制。首先，通過對(duì)社交網(wǎng)絡(luò)的結(jié)構(gòu)拓?fù)湟约肮?jié)點(diǎn)行為特點(diǎn)的分析，提出了基于節(jié)點(diǎn)親密度的社交網(wǎng)絡(luò)輿論領(lǐng)袖節(jié)點(diǎn)識(shí)別方法；然后，利用謠言傳播特性及節(jié)點(diǎn)的親密度，建立謠言傳播模型，并分析謠言在社交網(wǎng)絡(luò)中傳播時(shí)節(jié)點(diǎn)的狀態(tài)轉(zhuǎn)化過程；最后，提出了一種利用節(jié)點(diǎn)親密度實(shí)現(xiàn)謠言抑制的方法。

謠言傳播模型；親密度；社交網(wǎng)絡(luò)；謠言抑制

1 引言

近年來，隨著科技的進(jìn)步以及互聯(lián)網(wǎng)技術(shù)的發(fā)展，社交網(wǎng)絡(luò)得到了迅速的發(fā)展。無論是在國內(nèi)還是國外，社交網(wǎng)絡(luò)都擁有數(shù)億的用戶量，如新浪微博、Facebook等。社交網(wǎng)絡(luò)為廣大的用戶提供了一個(gè)信息分享和溝通的平臺(tái)，極大地滿足了人們的社交需求，已不再是一個(gè)純粹虛擬的社會(huì)，而是與現(xiàn)實(shí)社會(huì)密不可分。越來越多的人喜歡在社交平臺(tái)上交流互動(dòng)，同時(shí)也熱衷于從社交平臺(tái)中獲取信息并進(jìn)行轉(zhuǎn)發(fā)評(píng)論。而這些信息中，一些未經(jīng)求證的謠言泛濫成災(zāi)，因此而造成的惡意事件也逐漸增多，影響和干擾著人們正常的生活秩序。謠言在社交網(wǎng)絡(luò)中的肆意傳播，嚴(yán)重影響到社會(huì)穩(wěn)定、經(jīng)濟(jì)發(fā)展，有效地控制社交網(wǎng)絡(luò)中信息的傳播

具有重要意義。

本文首先通過對(duì)社交網(wǎng)絡(luò)中結(jié)構(gòu)拓?fù)湟约肮?jié)點(diǎn)的行為特征進(jìn)行分析討論，得到信息傳播過程中存在的“熟人效應(yīng)”現(xiàn)象[1,2]，通過節(jié)點(diǎn)親密度實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)中的輿論領(lǐng)袖節(jié)點(diǎn)進(jìn)行識(shí)別。然后，分析了謠言傳播模型，以及謠言在社交網(wǎng)絡(luò)中傳播時(shí)節(jié)點(diǎn)的狀態(tài)轉(zhuǎn)化過程。最后，提出了一種基于親密度的謠言抑制方案。

2 輿論領(lǐng)袖節(jié)點(diǎn)的識(shí)別

社交網(wǎng)絡(luò)中謠言的散播一般具有普遍性，可以引起群體大眾在思想上的某種共鳴；為吸引大眾的關(guān)注，散布者有意地夸大某種事實(shí)，滿足人群的獵奇心理；同時(shí)具有一定的模糊性，使謠言不易被識(shí)破，無法短時(shí)間判斷信息的真實(shí)性。Soh等[3]提出在多變的動(dòng)態(tài)環(huán)境影響下，網(wǎng)絡(luò)中節(jié)點(diǎn)間的連接矩陣是隨著時(shí)間而動(dòng)態(tài)變化的，并進(jìn)一步分析了在動(dòng)態(tài)網(wǎng)絡(luò)中謠言的傳播；Panagiotou等[4]提出具有不同拓?fù)浣Y(jié)構(gòu)的社交網(wǎng)絡(luò)、謠言傳播的特點(diǎn)；Acan等[5]提出了對(duì)于謠言推動(dòng)和挽回策略；Fountoulakis等[6]提出隨機(jī)網(wǎng)絡(luò)中網(wǎng)絡(luò)密度對(duì)于信息廣播傳播的影響；Giakkoupi[7]和Chierichetti等[8]對(duì)于謠言傳播過程中傳播范圍進(jìn)行了進(jìn)一步細(xì)致的分析。

社交網(wǎng)絡(luò)中謠言傳播的控制一直是一個(gè)關(guān)鍵性的問題，也是一個(gè)難點(diǎn)。在現(xiàn)存的解決方法中主要分為兩類措施[9]：1) 積極措施，包括通過控制社交網(wǎng)絡(luò)中的節(jié)點(diǎn)，從而實(shí)現(xiàn)對(duì)謠言傳播的阻塞作用；2) 亡羊補(bǔ)牢型措施，通過社交網(wǎng)絡(luò)中注入與謠言相對(duì)的真實(shí)信息實(shí)現(xiàn)對(duì)謠言的澄清，當(dāng)人們先后接收到2種相對(duì)的信息時(shí)，降低了謠言的可信度，達(dá)到亡羊補(bǔ)牢的效果。社交網(wǎng)絡(luò)一般具有用戶基數(shù)大的特點(diǎn)，通過控制所有的節(jié)點(diǎn)從而達(dá)到對(duì)于謠言傳播的阻塞是不可能實(shí)現(xiàn)的，所以需要識(shí)別出社交網(wǎng)絡(luò)在信息傳播過程中起關(guān)鍵作用的輿論領(lǐng)袖節(jié)點(diǎn)。

2.1 度中心性

節(jié)點(diǎn)的重要性只考慮了一個(gè)節(jié)點(diǎn)參與網(wǎng)絡(luò)的總水平而沒有考慮與其相連的鄰居節(jié)點(diǎn)所具有的重要性對(duì)其影響的數(shù)量，可認(rèn)為是節(jié)點(diǎn)中鄰居節(jié)點(diǎn)的數(shù)目，如式(1)所示[10]。

其中，i表示網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)，j表示網(wǎng)絡(luò)中所有其他的節(jié)點(diǎn)，N為所有的節(jié)點(diǎn)總數(shù)，x表示鄰接矩陣，若ijx的值為1，則表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間存在一條連邊；否則值為0。

2.2 緊密度中心性

緊密度中心性[11]的測(cè)量方法依賴于網(wǎng)絡(luò)中通過某節(jié)點(diǎn)的最短路徑的長(zhǎng)度。在網(wǎng)絡(luò)分析的過程中，若使用緊密度中心性作為節(jié)點(diǎn)重要程度的衡量標(biāo)準(zhǔn)則，表示距離其他節(jié)點(diǎn)越近的節(jié)點(diǎn)有越高的緊密度中心性，如式(2)所示。

其中，節(jié)點(diǎn)i到節(jié)點(diǎn) j的最短路徑長(zhǎng)度用 (,)d i j表示。

2.3 介數(shù)中心性

一個(gè)節(jié)點(diǎn)的介數(shù)中心性衡量了在網(wǎng)絡(luò)中通過該節(jié)點(diǎn)的最短路徑的數(shù)目，介數(shù)中心性分為邊介數(shù)和點(diǎn)介數(shù)[12]。邊介數(shù)表示網(wǎng)絡(luò)中所有最短路徑中通過該邊的最短路徑數(shù)目占總數(shù)的比例。點(diǎn)介數(shù)則表示網(wǎng)絡(luò)中所有最短路徑通過該節(jié)點(diǎn)的最短路徑數(shù)目占總數(shù)的比例，如式(3)所示。

2.4 K-shell

K-shell[13]分解法是一種粗粒度的網(wǎng)絡(luò)中節(jié)點(diǎn)重要度分析方法，其分解過程如下。從度的角度來看，網(wǎng)絡(luò)中度為1的節(jié)點(diǎn)就是網(wǎng)絡(luò)中影響力最小的節(jié)點(diǎn)（假設(shè)網(wǎng)絡(luò)中不存在度為 0的孤立節(jié)點(diǎn)）。把度為 1的節(jié)點(diǎn)以及與其相連的邊全部去掉，則網(wǎng)絡(luò)中剩余節(jié)點(diǎn)的度相應(yīng)地發(fā)生改變。如果剩余的網(wǎng)絡(luò)中仍然存在度為1的節(jié)點(diǎn)，則重復(fù)該操作，直到網(wǎng)絡(luò)中不存在度為1的節(jié)點(diǎn)為止，相當(dāng)于在網(wǎng)絡(luò)中一次一次地剝?nèi)プ钔饷娴臍?。稱

這些被除去的度為1的節(jié)點(diǎn)為1-shell。在網(wǎng)絡(luò)節(jié)點(diǎn)重要性分析過程中，認(rèn)為在網(wǎng)絡(luò)中節(jié)點(diǎn)對(duì)應(yīng)的K-shell值越大，則節(jié)點(diǎn)在網(wǎng)絡(luò)中的影響力越大。

2.5 特征向量中心性

特征向量中心性也是衡量節(jié)點(diǎn)重要程度的一個(gè)關(guān)鍵指標(biāo)。在特征向量中心性的算法中，一個(gè)節(jié)點(diǎn)的重要程度與其所有鄰居節(jié)點(diǎn)的重要程度有關(guān)。如果一個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)都很重要，則該節(jié)點(diǎn)具有很高的重要程度，如式(4)所示。

其中，λ為常數(shù)，A為網(wǎng)絡(luò)的鄰接矩陣。

2.6 參數(shù)比較

上述介紹的5種指標(biāo)通常均應(yīng)用于衡量節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要程度。但這幾種參數(shù)各有長(zhǎng)處和不足，簡(jiǎn)要分析如下。

度中心性的簡(jiǎn)單性是一個(gè)優(yōu)勢(shì)，即只需要知道網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)的局部拓?fù)浣Y(jié)構(gòu)即可計(jì)算其度中心性，但其忽略了節(jié)點(diǎn)的全局拓?fù)涞奶匦?，如某個(gè)節(jié)點(diǎn)雖然與很多節(jié)點(diǎn)相連，但它并不處在可以快速獲得信息的位置，因此無法成為關(guān)鍵節(jié)點(diǎn)。

緊密度中心性定義為從某個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑和的倒數(shù)，但緊密度中心性不適用于網(wǎng)絡(luò)中具有2個(gè)不連通組件的情況。假設(shè)節(jié)點(diǎn)i位于A組件中，節(jié)點(diǎn)j位于B組件中，且2個(gè)組件不連通，則節(jié)點(diǎn)i到節(jié)點(diǎn)j的最短路徑長(zhǎng)度無法計(jì)算，因此在計(jì)算最短路徑和的倒數(shù)時(shí)會(huì)使所有節(jié)點(diǎn)的緊密度中心性的值均相同。

介數(shù)中心性克服了緊密度中心性的缺點(diǎn)，不僅考慮了全局網(wǎng)絡(luò)拓?fù)洳⑶铱梢詰?yīng)用于具有不連通組件的網(wǎng)絡(luò)，但介數(shù)中心性忽略了不處于任何最短路徑上的節(jié)點(diǎn)。即介數(shù)中心性沒有評(píng)估在網(wǎng)絡(luò)中不處于任何最短路徑上的節(jié)點(diǎn)的中心性。

K-shell分解法是一種粗粒度的方法，在該分解方法中，會(huì)存在大量的節(jié)點(diǎn)具有相同的 k-shell值，無法進(jìn)一步區(qū)分這些具有相同的k-shell值的節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要程度。

特征向量中心性。若存在2個(gè)或多個(gè)不同的組件，則鄰接矩陣的特征向量只能識(shí)別出一個(gè)組件，也就意味著特征向量中心性不適用于分析含有多個(gè)組件的網(wǎng)絡(luò)。

綜上可知，介數(shù)中心性與度中心性以及緊密度中心性相比能夠更準(zhǔn)確地識(shí)別出關(guān)鍵節(jié)點(diǎn)，并且適用于更廣泛的網(wǎng)絡(luò)應(yīng)用場(chǎng)景。K-shell方法需要對(duì)網(wǎng)絡(luò)中的所有節(jié)點(diǎn)進(jìn)行一遍一遍的脫殼處理，過程慢且識(shí)別出的節(jié)點(diǎn)是粗粒度的，相比介數(shù)中心性準(zhǔn)確度較低。介數(shù)中心性在識(shí)別鄰接矩陣不對(duì)稱的網(wǎng)絡(luò)模型時(shí)，較特征向量中心性更具有優(yōu)勢(shì)。由于在社交網(wǎng)絡(luò)中用戶之間的關(guān)系具有有向性，所以本文基于介數(shù)中心性識(shí)別輿論領(lǐng)袖節(jié)點(diǎn)而實(shí)現(xiàn)謠言的抑制。

2.7 基于親密度算法輿論節(jié)點(diǎn)的識(shí)別分析

在社交網(wǎng)絡(luò)中信息傳播的過程中，用戶節(jié)點(diǎn)通常會(huì)收到朋友節(jié)點(diǎn)的影響。Bakshy[1]以及Onnela[2]通過實(shí)驗(yàn)證實(shí)了這種說法，并得出信息通過用戶節(jié)點(diǎn)間的鏈路進(jìn)行傳播的結(jié)論，即熟人傳播，因此社交網(wǎng)絡(luò)展現(xiàn)了“口碑效應(yīng)”的影響。通過“口碑效應(yīng)”可以看出，在社交網(wǎng)絡(luò)中用戶之間的關(guān)系越親密，則推薦的消息更容易被接受并加以傳播，通過節(jié)點(diǎn)間關(guān)系的親密度來實(shí)現(xiàn)輿論節(jié)點(diǎn)的識(shí)別?？紤]到社交網(wǎng)絡(luò)中節(jié)點(diǎn)之間信息的傳播存在主觀因素的影響，所以本文在社交網(wǎng)絡(luò)中引入了親密度的概念，并衡量了不相鄰節(jié)點(diǎn)之間的影響力大小，利用在介數(shù)中心性算法的基礎(chǔ)上實(shí)現(xiàn)輿論領(lǐng)袖節(jié)點(diǎn)的識(shí)別[14]，并通過對(duì)網(wǎng)絡(luò)中與鄰居節(jié)點(diǎn)均具有較高的親密度的節(jié)點(diǎn)進(jìn)行謠言的控制，都會(huì)達(dá)到較好的效果，本文提出了基于節(jié)點(diǎn)親密度的謠言抑制方法。

節(jié)點(diǎn)親密度的影響因素分析如下。

將社交網(wǎng)絡(luò)映射為由節(jié)點(diǎn)集合V和有向邊集合E組成的有向圖G=(V,E,W)。將社交網(wǎng)絡(luò)中的用戶集合映射為網(wǎng)絡(luò)拓?fù)淠Ｐ椭械墓?jié)點(diǎn)集合 V；用戶之間的關(guān)系映射為節(jié)點(diǎn)之間的有向鏈路集合E；W 為鏈路上的權(quán)值，表示每一對(duì)用戶之間的親密度量化值。

本文主要從以下3個(gè)方面評(píng)估節(jié)點(diǎn)間的親密度。1) 交互頻率

社交網(wǎng)絡(luò)中2個(gè)節(jié)點(diǎn)之間的交互行為是自發(fā)的，所以經(jīng)常會(huì)造成2個(gè)節(jié)點(diǎn)之間存在突發(fā)的交互情況。為了防止突發(fā)現(xiàn)象的發(fā)生，本文取在一段時(shí)間內(nèi)多次交互的時(shí)間間隔的平均值作為衡量標(biāo)準(zhǔn)。假設(shè)2個(gè)節(jié)點(diǎn)交互的時(shí)間間隔為Δt，一段時(shí)間為T，則計(jì)算方法如式(5)所示。

其中，n為在時(shí)間T內(nèi)2個(gè)節(jié)點(diǎn)的交互次數(shù)，itΔ表示2個(gè)節(jié)點(diǎn)第i次和第 1i+次交互的時(shí)間間隔。

2) 交互類型

僅通過交互頻率來衡量節(jié)點(diǎn)的親密度會(huì)出現(xiàn)社交網(wǎng)絡(luò)中公共賬號(hào)與用戶之間的親密度異常高的情況。這是因?yàn)樯缃痪W(wǎng)絡(luò)中的一些公共賬號(hào)為了推廣自己的產(chǎn)品或廣告，會(huì)以固定的頻率向用戶推送消息，導(dǎo)致公共賬號(hào)與用戶之間的交互時(shí)間間隔短、交互頻率高。在使用交互頻率來衡量節(jié)點(diǎn)之間的親密度時(shí)忽略了這種情況。為了彌補(bǔ)這個(gè)缺點(diǎn)，本文對(duì)處于不同好友類型的節(jié)點(diǎn)賦予不同的權(quán)值。

對(duì)使用式(5)計(jì)算達(dá)到的交互頻率賦予權(quán)值，如式(6)和式(7)所示。

其中，sw表示2個(gè)節(jié)點(diǎn)之間的好友類型為陌生人時(shí)鏈路上的權(quán)值，fw表示2個(gè)節(jié)點(diǎn)之間的好友類型為好友時(shí)鏈路上的權(quán)值，1η和2η為2個(gè)平衡因子，用來協(xié)調(diào)不同的好友類型的交互頻率。

3) 節(jié)點(diǎn)間跳數(shù)

在以往對(duì)社交網(wǎng)絡(luò)的研究中，沒有考慮不相鄰節(jié)點(diǎn)之間的親密度，但在社交網(wǎng)絡(luò)中不相鄰的節(jié)點(diǎn)之間確實(shí)存在親密度，即“朋友的朋友也是朋友，朋友的敵人就是敵人”。所以不存在直接鏈路的2個(gè)節(jié)點(diǎn)不代表沒有親密度。

如圖1所示，圖中的每個(gè)節(jié)點(diǎn)表示一個(gè)用戶，每條鏈路表示2個(gè)節(jié)點(diǎn)之間的關(guān)系，鏈路上的權(quán)值表示節(jié)點(diǎn)之間的親密度，假設(shè)權(quán)值越大，則 2個(gè)節(jié)點(diǎn)之間的親密度越高，交互越頻繁。可以看出，圖中節(jié)點(diǎn)D和節(jié)點(diǎn)E以及節(jié)點(diǎn)E和節(jié)點(diǎn)B之間的親密度均較高，且節(jié)點(diǎn)D和節(jié)點(diǎn)B之間不存在直接鏈路。若節(jié)點(diǎn)D發(fā)布一條消息，因?yàn)楣?jié)點(diǎn)D與節(jié)點(diǎn)E之間的交互頻率較高，所以節(jié)點(diǎn)E會(huì)很快接收到節(jié)點(diǎn)D的消息，并繼續(xù)傳播，則很快節(jié)點(diǎn)B就可以通過節(jié)點(diǎn)E接收到節(jié)點(diǎn)D發(fā)送過來的消息。由此可見不相鄰的2個(gè)節(jié)點(diǎn)之間也具有親密度。

在社交網(wǎng)絡(luò)中，由于節(jié)點(diǎn)之間消息的轉(zhuǎn)發(fā)經(jīng)過每一跳節(jié)點(diǎn)的傳播時(shí)都存在一定的時(shí)延。如果在網(wǎng)絡(luò)中一條路徑上節(jié)點(diǎn)之間的親密度均較高，但是跳數(shù)較多，則無法直觀地判斷這條路徑傳播速度的快慢。因此，需要衡量一條傳播路徑上每條鏈路的親密度大小以及跳數(shù)時(shí)延帶來的影響。如圖1所示，從節(jié)點(diǎn)A發(fā)出一條消息，若該消息傳播到節(jié)點(diǎn) B具有 3條路徑，分別是 A-＞D-＞E-＞B、A-＞C-＞B和A-＞B。這3條路徑的跳數(shù)分別為3跳、2跳和1跳。但鏈路上的親密度不盡相同，在A-＞D-＞E-＞B這條鏈路上，每一跳的親密度均較大，但跳數(shù)較多；在A-＞C-＞B和A-＞B這2條路徑上，雖然跳數(shù)較少，但鏈路上的親密度不高，所以無法直觀地比較節(jié)點(diǎn)A發(fā)出的消息從哪條路徑能更快地傳播到節(jié)點(diǎn)B，需要衡量跳數(shù)時(shí)延和親密度的大小對(duì)傳播速度的影響。

圖1 節(jié)點(diǎn)親密度以及跳數(shù)時(shí)延的影響

在信息傳播過程中，已有的社交網(wǎng)絡(luò)中信息擴(kuò)散程度最大化的研究[15]表明，信息若從節(jié)點(diǎn) i開始傳播，則信息在傳播了3～4跳之后，則節(jié)點(diǎn)i對(duì)之后的其他節(jié)點(diǎn)幾乎沒有影響。所以本文也只考慮了某節(jié)點(diǎn)與任意距離它間隔3跳之內(nèi)的節(jié)點(diǎn)之間的跳數(shù)時(shí)延對(duì)親密度的影響。

在社交網(wǎng)絡(luò)中，消息在節(jié)點(diǎn)之間進(jìn)行傳播的過程是相互獨(dú)立的，即2個(gè)節(jié)點(diǎn)之間信息的傳播速度以及接受程度不受上一跳節(jié)點(diǎn)之間傳播速度的影響。根據(jù)上述分析，得出計(jì)算節(jié)點(diǎn)間跳數(shù)對(duì)親密度的影響公式，如式(8)所示。

其中，γ1和 γ2為2個(gè)權(quán)值，用來調(diào)節(jié)交互頻率與節(jié)點(diǎn)間跳數(shù)對(duì)親密度的影響關(guān)系，且 γ1, γ2≤ 1；hi,j表示節(jié)點(diǎn)i到節(jié)點(diǎn) j之間間隔的跳數(shù)，且hi,j≤ 3； wn表示節(jié)點(diǎn)i到節(jié)點(diǎn)j之間距離節(jié)點(diǎn)i的跳數(shù)為n的節(jié)點(diǎn) nodei,n與跳數(shù)為 n+1的節(jié)點(diǎn)nodei,n+1之間鏈路上的權(quán)值，該權(quán)值通過式(6)或式(7)計(jì)算，如果節(jié)點(diǎn) nodei,n與節(jié)點(diǎn) nodei,n+1之間的關(guān)系為陌生人關(guān)系，則使用式(6)計(jì)算；若為好友關(guān)系則使用式(7)進(jìn)行計(jì)算。

在結(jié)合了節(jié)點(diǎn)之間的交互頻率、好友類型和跳數(shù)時(shí)延3方面綜合量化之后，得到最終的節(jié)點(diǎn)之間親密度評(píng)估方法。因?yàn)樵谟?jì)算網(wǎng)絡(luò)拓?fù)渲凶疃搪窂綍r(shí)，鏈路上的權(quán)值越小表示路徑越短，所以將節(jié)點(diǎn)間的親密度量化結(jié)果也表示為值越小則親密度越高。根據(jù)介數(shù)中心性的大小識(shí)別輿論領(lǐng)袖節(jié)點(diǎn)，增加了對(duì)網(wǎng)絡(luò)圖加邊和更新權(quán)值的過程，這個(gè)過程的時(shí)間復(fù)雜度是隨著節(jié)點(diǎn)的增多線性增加的，對(duì)每個(gè)節(jié)點(diǎn)及其鄰居節(jié)點(diǎn)進(jìn)行一遍計(jì)算。所以整個(gè)基于親密度的輿論領(lǐng)袖節(jié)點(diǎn)識(shí)別算法的時(shí)間復(fù)雜度是在 Brande[13]算法的基礎(chǔ)上加上更新過程的時(shí)間復(fù)雜度，為O(nm+n2lbn+ ＜k＞n)。其中，＜k＞為網(wǎng)絡(luò)平均度的大小。

3 謠言傳播模型

由于在社交網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)都是一個(gè)用戶，所以在謠言傳播的過程中，每個(gè)節(jié)點(diǎn)都具備多種不同的狀態(tài)。在本文的信息擴(kuò)散模型中，將信息傳播過程中的節(jié)點(diǎn)分為3種狀態(tài)：未感染狀態(tài)、感染狀態(tài)（infected）和傳播狀態(tài)。

3.1 SIR模型

在經(jīng)典的SIR傳染病模型中，將節(jié)點(diǎn)狀態(tài)分為易感染狀態(tài)（susceptible）、感染狀態(tài)和治愈狀態(tài)（recovered）。社交網(wǎng)絡(luò)中除傳染源之外的節(jié)點(diǎn)初始狀態(tài)均為易感染狀態(tài)。當(dāng)處于易感染狀態(tài)的節(jié)點(diǎn)接觸到感染節(jié)點(diǎn)后以一定的概率變?yōu)楦腥緺顟B(tài)。當(dāng)處于感染狀態(tài)的節(jié)點(diǎn)在接觸到易感染狀態(tài)的節(jié)點(diǎn)時(shí)，又會(huì)以一定的概率將其感染。但當(dāng)處于感染狀態(tài)的節(jié)點(diǎn)以一定的概率被治愈后，將處于治愈狀態(tài)，并具有免疫能力，不會(huì)再被感染。主要的節(jié)點(diǎn)狀態(tài)轉(zhuǎn)化過程如圖2所示。

該傳播模型在傳染病傳播過程中得到廣泛應(yīng)用。適用于當(dāng)個(gè)體感染到病毒后都有成為病原體的機(jī)會(huì)，并且成為病原體的個(gè)體康復(fù)后則具有永久免疫能力的情況。

圖2 SIR模型中節(jié)點(diǎn)狀態(tài)轉(zhuǎn)化

3.2 SIRS模型

SIRS模型是SIR模型的進(jìn)一步演化，在SIR模型的基礎(chǔ)上增加了從治愈狀態(tài)到易感染狀態(tài)的過程。這個(gè)過程表示，當(dāng)個(gè)體感染到病原體并被治愈后，并不是處于永久免疫的狀態(tài)，而是具有一個(gè)免疫周期。即處于治愈狀態(tài)的節(jié)點(diǎn)可以以一定的概率喪失自身的免疫能力，恢復(fù)到易感染狀態(tài)。SIRS模型的節(jié)點(diǎn)狀態(tài)轉(zhuǎn)化過程如圖3所示。

圖3 SIRS模型中節(jié)點(diǎn)狀態(tài)轉(zhuǎn)化

3.3 SEIR模型

SEIR模型在 SIR模型中添加了潛伏狀態(tài)（exposed）。當(dāng)處于易感染狀態(tài)的節(jié)點(diǎn)與處于感染狀態(tài)的節(jié)點(diǎn)接觸后，并不是以一定的概率轉(zhuǎn)變?yōu)楦腥竟?jié)點(diǎn)，而是先以一定的概率轉(zhuǎn)變?yōu)闈摲鼱顟B(tài)。處于潛伏狀態(tài)的節(jié)點(diǎn)仍然是一個(gè)健康的個(gè)體，不具備傳染其他節(jié)點(diǎn)的能力。然后處于潛伏狀態(tài)的節(jié)點(diǎn)會(huì)以一定的概率轉(zhuǎn)變?yōu)楦腥緺顟B(tài)。與 SIR模型相同，SEIR模型中處于治愈狀態(tài)的節(jié)點(diǎn)也具有了永久免疫的能力。這種模型更適用于描述具有典型潛伏期的傳染現(xiàn)象，如狂犬病，感染后并不是馬上發(fā)病，而是潛伏一段時(shí)間后以一定的概率發(fā)病。所以在社交網(wǎng)絡(luò)中這種模型并不是十分實(shí)用，因?yàn)樵谏缃痪W(wǎng)絡(luò)中用戶對(duì)接收到的信息具有即時(shí)反饋特性。即時(shí)反饋特性指當(dāng)用戶收到消息后會(huì)馬上做出反饋，無論是選擇轉(zhuǎn)發(fā)還是評(píng)論，都會(huì)在接收到信息后做出該行為。

SEIR模型的節(jié)點(diǎn)狀態(tài)轉(zhuǎn)化過程如圖4所示。

圖4 SEIR模型中節(jié)點(diǎn)狀態(tài)轉(zhuǎn)化

3.4 傳染病模型改進(jìn)

通過向社交網(wǎng)絡(luò)中的輿論領(lǐng)袖節(jié)點(diǎn)注入真相從而控制社交網(wǎng)絡(luò)中謠言的傳播。因此在這一部分將社交網(wǎng)絡(luò)中節(jié)點(diǎn)傳播的狀態(tài)進(jìn)一步細(xì)化，其中包含了當(dāng)節(jié)點(diǎn)接收到真相后的各種狀態(tài)。

1) 易感染狀態(tài)。處于易感染狀態(tài)的節(jié)點(diǎn)既沒有接收過謠言的信息也沒有接收過真相的信息。處于該狀態(tài)的節(jié)點(diǎn)很容易以一定的概率被謠言或真相感染。假設(shè)節(jié)點(diǎn)i處于易感染狀態(tài)，

當(dāng)其接收到關(guān)于謠言的信息，則以概率λ選擇相信謠言，變?yōu)楦腥緺顟B(tài)。若節(jié)點(diǎn)i接收到的是關(guān)于真相的信息，則以概率β選擇相信真相，變?yōu)槊庖吖?jié)點(diǎn)。

2) 感染狀態(tài)。處于感染狀態(tài)的節(jié)點(diǎn)具有傳染性。該狀態(tài)的節(jié)點(diǎn)具有將謠言傳播給其他節(jié)點(diǎn)的能力。但當(dāng)處于感染狀態(tài)的節(jié)點(diǎn)接收到真相相關(guān)的信息后則以概率α選擇相信真相，變?yōu)橹斡鸂顟B(tài)。

3) 治愈狀態(tài)。處于治愈狀態(tài)的節(jié)點(diǎn)不再相信謠言，并以一定的概率傳播真相。由于在社交網(wǎng)絡(luò)中，每一個(gè)節(jié)點(diǎn)都是現(xiàn)實(shí)生活中的一個(gè)個(gè)體，具有記憶機(jī)制，所以處于治愈狀態(tài)的節(jié)點(diǎn)同樣也屬于免疫狀態(tài)。

4) 免疫狀態(tài)（defended）。當(dāng)處于易感染狀態(tài)的節(jié)點(diǎn)接收到真相后選擇了相信真相，則會(huì)進(jìn)入免疫狀態(tài)。處于該狀態(tài)的節(jié)點(diǎn)通常具有較強(qiáng)的自我判斷能力。

通過上述對(duì)抑制謠言過程中節(jié)點(diǎn)狀態(tài)的分類，總結(jié)社交網(wǎng)絡(luò)中節(jié)點(diǎn)狀態(tài)變化過程，如圖 5所示。上述過程在SIR模型的基礎(chǔ)上增加了免疫狀態(tài)，更形象地描述了社交網(wǎng)絡(luò)中的節(jié)點(diǎn)直接相信真相的過程。

圖5 抑制謠言過程中節(jié)點(diǎn)狀態(tài)轉(zhuǎn)化

處于免疫狀態(tài)和傳播狀態(tài)的節(jié)點(diǎn)都具有2種狀態(tài)：活躍狀態(tài)（active）和不活躍狀態(tài)（inactive）。處于活躍狀態(tài)的節(jié)點(diǎn)具有感染其他節(jié)點(diǎn)的能力，繼續(xù)將謠言或真相傳播給其他節(jié)點(diǎn)。而處于不活躍狀態(tài)的節(jié)點(diǎn)則不具備傳播信息的能力，處于感染狀態(tài)的不活躍節(jié)點(diǎn)繼續(xù)保持自身原有狀態(tài)直到接觸到免疫節(jié)點(diǎn)后以一定的概率轉(zhuǎn)變?yōu)橹斡鸂顟B(tài)，處于免疫狀態(tài)的不活躍節(jié)點(diǎn)則始終保持自身原有狀態(tài)不變。

假設(shè)節(jié)點(diǎn)i在 t時(shí)刻處于易受感染狀態(tài)或感染狀態(tài)，則節(jié)點(diǎn)i在下一時(shí)刻接收到其鄰居節(jié)點(diǎn)傳播的真相的概率如式(9)所示。

其中， nei( i)表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集合， wi,j表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的親密度， Xj(t)表示節(jié)點(diǎn)j在t時(shí)刻所處的狀態(tài)，Pj( Xj(t) =refended. a ctive)表示節(jié)點(diǎn)j在 t時(shí)刻處于免疫狀態(tài)下的活躍狀態(tài)的概率。只要節(jié)點(diǎn)i在t+1時(shí)刻接受了任何一個(gè)其處于免疫狀態(tài)的鄰居節(jié)點(diǎn)傳播的真相，則節(jié)點(diǎn) i將會(huì)變?yōu)槊庖郀顟B(tài)。

由此可知，在網(wǎng)絡(luò)中的任意一個(gè)節(jié)點(diǎn)接受真相的平均時(shí)間如式(10)所示。

假設(shè)節(jié)點(diǎn)i在t時(shí)刻處于易受感染狀態(tài)，而在t+1時(shí)刻仍然處于易受感染狀態(tài)的概率如式(11)所示。

其中， ()t iP S表示節(jié)點(diǎn)i在t時(shí)刻處于易受感染狀態(tài)的概率，節(jié)點(diǎn)j表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)中在t時(shí)刻處于感染狀態(tài)并活躍的節(jié)點(diǎn)，節(jié)點(diǎn)k表示節(jié)點(diǎn)i的論據(jù)節(jié)點(diǎn)中在t時(shí)刻處于免疫狀態(tài)并活躍的節(jié)點(diǎn)。若節(jié)點(diǎn)在t+1時(shí)刻仍然處于易受感染狀態(tài)，則說明其鄰居節(jié)點(diǎn)對(duì)其任何消息的傳播均沒有被接受。

同理，可以推導(dǎo)出節(jié)點(diǎn)在任意時(shí)刻處于某種狀態(tài)的概率。節(jié)點(diǎn)i在t+1時(shí)刻處于感染狀態(tài)的概率以及處于免疫狀態(tài)的概率分別如式(12)和式(13)所示。

通過上述分析可以看出，社交網(wǎng)絡(luò)中處于免疫狀態(tài)的節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)之間的親密度越大，則處于免疫狀態(tài)的節(jié)點(diǎn)傳播的真相信息更容易被其鄰居節(jié)點(diǎn)接受，從而使真相能夠在整個(gè)網(wǎng)絡(luò)中迅速傳播，進(jìn)而達(dá)到快速控制謠言的目的。

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

對(duì)于謠言控制，若通過網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)實(shí)現(xiàn)謠言的阻塞，但是謠言的傳播迅速，往往當(dāng)人們了解到謠言信息時(shí)，謠言傳播已達(dá)到一定的范圍。為挽救謠言散播的局面，此時(shí)就需要補(bǔ)救措施進(jìn)行補(bǔ)救，通過輿論領(lǐng)袖節(jié)點(diǎn)向整個(gè)網(wǎng)絡(luò)中注入與謠言相對(duì)的真實(shí)信息，當(dāng)真實(shí)信息與謠言先后達(dá)到某個(gè)節(jié)點(diǎn)時(shí)，該節(jié)點(diǎn)對(duì)于信息的真實(shí)度會(huì)重新判斷，同時(shí)，當(dāng)散播真實(shí)信息的節(jié)點(diǎn)親密度較高時(shí)，會(huì)降低謠言的可信度。整個(gè)網(wǎng)絡(luò)中不再存在接收謠言信息的節(jié)點(diǎn)，但是這種狀態(tài)基本不能實(shí)現(xiàn)[9]，因此為實(shí)現(xiàn)謠言的控制，應(yīng)在最短的時(shí)間內(nèi)，將信任謠言信息的節(jié)點(diǎn)控制在一定的范圍內(nèi)。

4.1 信息最大化擴(kuò)散效果比較

為驗(yàn)證基于節(jié)點(diǎn)間親密度對(duì)于謠言控制的有效性，分別使用隨機(jī)選取、度中心性選取、介數(shù)中心性選取和基于親密度選取，在1 000個(gè)節(jié)點(diǎn)和2 000個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)模型中識(shí)別出10個(gè)輿論領(lǐng)袖節(jié)點(diǎn)作為信息源，比較最終被信息感染節(jié)點(diǎn)的數(shù)目。具有1 000個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中選取10個(gè)節(jié)點(diǎn)作為信息源，得到最終感染節(jié)點(diǎn)數(shù)目，即最大化擴(kuò)散效果對(duì)比方法，實(shí)驗(yàn)結(jié)果如圖6所示，根據(jù)親密度方法選擇的輿論領(lǐng)袖節(jié)點(diǎn)最大化擴(kuò)散過程仍然是一個(gè)慢起步的過程，但最終的最大化擴(kuò)散規(guī)模較其他2種方法大。

其中，closeness表示通過基于親密度識(shí)別輿論領(lǐng)袖節(jié)點(diǎn)的方法；random表示隨機(jī)選取方法；degree表示通過度中心性選取輿論領(lǐng)袖節(jié)點(diǎn)的方法；betweenness表示使用介數(shù)中心性識(shí)別方法識(shí)別的輿論領(lǐng)袖節(jié)點(diǎn)擴(kuò)散過程。

在2 000個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中選取10個(gè)節(jié)點(diǎn)作為信息源，得到最終感染節(jié)點(diǎn)數(shù)目，即最大化擴(kuò)散效果對(duì)比方法，實(shí)驗(yàn)結(jié)果如圖7所示。

由于隨機(jī)選取的節(jié)點(diǎn)具有隨機(jī)性，所以在本次對(duì)比實(shí)驗(yàn)中，隨機(jī)選取的輿論領(lǐng)袖節(jié)點(diǎn)沒有辦法擴(kuò)散信息。度中心性和親密度選取的輿論領(lǐng)袖節(jié)點(diǎn)在影響力最大化擴(kuò)散效果中，可以與有1 000個(gè)節(jié)點(diǎn)以及2 000個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)得到相同的結(jié)論。

4.2 謠言抑制效果對(duì)比

將改進(jìn)的謠言傳播模型引入到獨(dú)立級(jí)聯(lián)模型中，增加獨(dú)立級(jí)聯(lián)模型中節(jié)點(diǎn)的狀態(tài)，并分別從以下幾方面進(jìn)行謠言抑制擴(kuò)散效果對(duì)比。

1) 真相注入時(shí)間不同

本節(jié)分別對(duì)比不同的真相注入時(shí)間t對(duì)謠言抑制效果的影響，結(jié)果如圖8所示。分別對(duì)比了真相在不同時(shí)刻t=2、t=3和t=4注入到網(wǎng)絡(luò)中的情況，其中，時(shí)間t表示在真相的注入時(shí)刻，t=2為較早時(shí)刻，t=3為中間時(shí)刻，t=4表示較晚時(shí)刻。從圖8中可以看出，真相注入的時(shí)間越早，則可以越好地抑制謠言的傳播范圍。

圖6 1 000個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中，最大化擴(kuò)散效果

圖7 2 000個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中，最大化擴(kuò)散效果

圖8 不同時(shí)間注入真相的謠言抑制效果對(duì)比

2) 輿論領(lǐng)袖節(jié)點(diǎn)不同

本節(jié)分別對(duì)使用不同的輿論領(lǐng)袖節(jié)點(diǎn)識(shí)別方法識(shí)別出的節(jié)點(diǎn)在相同的時(shí)間注入真相，并對(duì)比其謠言抑制效果。

圖9表示在相同的時(shí)間分別向多種方法識(shí)別出的輿論領(lǐng)袖節(jié)點(diǎn)注入真相（在較晚時(shí)刻）抑制謠言的效果對(duì)比情況。從圖9可以看出，向使用度中心性識(shí)別出的輿論領(lǐng)袖節(jié)點(diǎn)注入真相后，被謠言感染的節(jié)點(diǎn)數(shù)量依然有一個(gè)上升的趨勢(shì)，然后才開始逐漸被抑制。

從圖9(b)可以看出，介數(shù)中心性識(shí)別方法與基于親密度識(shí)別輿論領(lǐng)袖節(jié)點(diǎn)的方法在抑制謠言的過程中，初始階段相差不大，均在注入真相后就會(huì)對(duì)謠言有顯著的抑制作用，但之后親密度方法抑制謠言的速度較介數(shù)中心性方法更快，所以，親密度方法對(duì)謠言抑制速度較快，能較早達(dá)到穩(wěn)定狀態(tài)，控制效果較好。

5 結(jié)束語

本文首先分析了謠言傳播模型，以及謠言在社交網(wǎng)絡(luò)中傳播時(shí)節(jié)點(diǎn)的狀態(tài)轉(zhuǎn)化過程。其次通

過數(shù)值分析的方法提出了一種基于親密度的謠言抑制方案，并通過理論分析和仿真對(duì)比驗(yàn)證了該方案的有效性。本文從社交網(wǎng)絡(luò)節(jié)點(diǎn)間親密的角度識(shí)別了社交網(wǎng)絡(luò)中的輿論領(lǐng)袖節(jié)點(diǎn)，并取得了一定的研究成果[14]，但識(shí)別輿論領(lǐng)袖節(jié)點(diǎn)最終的目的是為了更好地控制社交網(wǎng)絡(luò)。本文雖然給出了基于輿論領(lǐng)袖節(jié)點(diǎn)的謠言控制方法，但只是從數(shù)值分析和理論分析的角度進(jìn)行了闡述，仍需要深入探索。

[1] BAKSHY E, KARRER B, ADAMIC L A. Social influence and the diffusion of user-created content[C]//The 10th ACM Conference on Electronic Commerce. 2009: 325-334.

[2] ONNELA J P, SARAM?KI J, HYV?NEN J, et al. Structure and tie strengths in mobile communication networks[J]. The National Academy of Sciences, 2007, 104(18): 7332-7336.

[3] SOH D W, QUEK T Q S, TAY W P. Randomized rumor spreading in non-static networks[C]// IEEE International Conference on ICT Convergence. 2011:156 - 160.

[4] PANAGIOTOU K, PéREZGIMéNEZ X, SUN T S H. Randomized rumour spreading: the effect of the network topology[J]. Combinatorics Probability & Computing, 2014, 24(2):1-23.

[5] ACAN H, COLLEVECCHIO A, MEHRABIAN A, et al. On the push&pull protocol for rumour spreading[J]. Klinische Padiatrie, 2014, 226(3):161-168.

[6] FOUNTOULAKIS N, HUBER A, PANAGIOTOU K. Reliable broadcasting in random networks and the effect of density[C]// Infocom. 2010:1-9.

[7] GIAKKOUPIS G. Tight bounds for rumor spreading in graphs of a given conductance[C]//The 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). 2011: 57-68.

[8] CHIERICHETTI F, LATTANZI S, PANCONESI A. Almost tight bounds for rumour spreading with conductance.[J]. The ACM International Symposium on Theory of Computing, 2010:399-408.

[9] WEN S, JIANG J, XIANG Y, et al. To shut them up or to clarify: restraining the spread of rumors in online social networks[J]. Parallel and Distributed Systems, 2014, 25(12): 3306-3316.

[10] AI J, ZHAO H, CARLEY K M, et al. Neighbor vector centrality of complex networks based on neighbors degree distribution[J]. Physics of Condensed Matter, 2013, 86(4):1-7.

[11] WEHMUTH K, ZIVIANI A. Distributed assessment of the closeness centrality ranking in complex networks[C]// The Workshop on Simplifying Complex Networks for Practitioners. 2012:43-48.

[12] BRANDESU. A faster algorithm for betweenness centrality[J]. Journal of Mathematical Sociology, 2010, 25(2):163-177.

[13] KITSAK M, GALLOS L K, HAVLIN S, et al. Identification of influential spreaders in complex networks[J]. Nature Physics, 2010, 6(11): 888-893.

[14] YANG L, QIAO Y, LIU Z, et al. Identifying opinion leader nodes in online social networks with a new closeness evaluation algorithm[J]. Soft Computing, 2016:1-12.

[15] LU Z, FAN L, WU W, et al. Efficient influence spread estimation for influence maximization under the linear threshold model[J]. Computational Social Networks, 2014, 1(1): 1-19.

田亞平（1991-），女，河北保定人，西安電子科技大學(xué)碩士生，主要研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)、移動(dòng)和無線網(wǎng)絡(luò)安全。

楊力（1977-），男，陜西西安人，博士，西安電子科技大學(xué)副教授、碩士生導(dǎo)師，主要研究方向?yàn)橐苿?dòng)互聯(lián)網(wǎng)安全——認(rèn)證方法與技術(shù)、云計(jì)算安全、數(shù)據(jù)安全存儲(chǔ)與刪除、移動(dòng)終端安全、運(yùn)行環(huán)境安全驗(yàn)證、可信計(jì)算、遠(yuǎn)程證明技術(shù)。

王小琴（1990-），女，山西長(zhǎng)治人，西安電子科技大學(xué)碩士生，主要研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)、移動(dòng)和無線網(wǎng)絡(luò)安全。

喬雅峰（1993-），女，內(nèi)蒙古呼倫貝爾人，西安電子科技大學(xué)碩士生，主要研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)、移動(dòng)和無線網(wǎng)絡(luò)安全。

Suppress the diffusion of rumors with nodes closeness mining

TIAN Ya-ping, YANG Li, WANG Xiao-qin, QIAO Ya-feng
(School of Cyber Engineering, Xidian University, Xi’an 710071, China)

Through making the analysis of information spread in social networks, the supression of rumors, error information and other negative information was realized. Firstly, by analyzing the structure of social networks and the characteristics of node behavior, a method for the identification of opinion leader nodes was proposed based on the degree of intimacy between nodes in social networks. Then, the rumor propagation model and the analysis of nodes’ state transformation process were made when the rumor spread in social networks. At last, the control method was proposed to suppress the diffusion of rumors with the nodes’ closeness.

rumor propagation model, closeness, social networks, supression of rumors

TP393

A

10.11959/j.issn.2096-109x.2016.00114

2016-09-20；

2016-10-23。通信作者：田亞平，typ19920110@sina.com

國家自然科學(xué)基金資助項(xiàng)目（No.61671360）；信息保障重點(diǎn)實(shí)驗(yàn)室基金資助項(xiàng)目（No.KJ-14-109）；中央高?；究蒲袠I(yè)務(wù)費(fèi)基金資助項(xiàng)目（No.JB161505）

Foundation Items: The National Natural Science Foundation of China (No.61671360), The Foundation of Science and Technology on Information Assurance Laboratory (No.KJ-14-109), The Fundamental Research Funds for the Central Universities (No.JB161505)