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

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

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

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

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

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

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

1 引言

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

具有重要意義。

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

2 輿論領袖節(jié)點的識別

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

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

2.1 度中心性

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

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

2.2 緊密度中心性

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

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

2.3 介數(shù)中心性

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

2.4 K-shell

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

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

2.5 特征向量中心性

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

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

2.6 參數(shù)比較

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

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

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

介數(shù)中心性克服了緊密度中心性的缺點，不僅考慮了全局網(wǎng)絡拓撲并且可以應用于具有不連通組件的網(wǎng)絡，但介數(shù)中心性忽略了不處于任何最短路徑上的節(jié)點。即介數(shù)中心性沒有評估在網(wǎng)絡中不處于任何最短路徑上的節(jié)點的中心性。

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

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

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

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

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

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

將社交網(wǎng)絡映射為由節(jié)點集合V和有向邊集合E組成的有向圖G=(V,E,W)。將社交網(wǎng)絡中的用戶集合映射為網(wǎng)絡拓撲模型中的節(jié)點集合 V；用戶之間的關系映射為節(jié)點之間的有向鏈路集合E；W 為鏈路上的權(quán)值，表示每一對用戶之間的親密度量化值。

本文主要從以下3個方面評估節(jié)點間的親密度。1) 交互頻率

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

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

2) 交互類型

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

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

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

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

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

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

在社交網(wǎng)絡中，由于節(jié)點之間消息的轉(zhuǎn)發(fā)經(jīng)過每一跳節(jié)點的傳播時都存在一定的時延。如果在網(wǎng)絡中一條路徑上節(jié)點之間的親密度均較高，但是跳數(shù)較多，則無法直觀地判斷這條路徑傳播速度的快慢。因此，需要衡量一條傳播路徑上每條鏈路的親密度大小以及跳數(shù)時延帶來的影響。如圖1所示，從節(jié)點A發(fā)出一條消息，若該消息傳播到節(jié)點 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é)點A發(fā)出的消息從哪條路徑能更快地傳播到節(jié)點B，需要衡量跳數(shù)時延和親密度的大小對傳播速度的影響。

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

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

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

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

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

3 謠言傳播模型

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

3.1 SIR模型

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

該傳播模型在傳染病傳播過程中得到廣泛應用。適用于當個體感染到病毒后都有成為病原體的機會，并且成為病原體的個體康復后則具有永久免疫能力的情況。

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

3.2 SIRS模型

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

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

3.3 SEIR模型

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

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

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

3.4 傳染病模型改進

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 仿真實驗

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

4.1 信息最大化擴散效果比較

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

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

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

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

4.2 謠言抑制效果對比

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

1) 真相注入時間不同

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

圖6 1 000個節(jié)點的網(wǎng)絡中，最大化擴散效果

圖7 2 000個節(jié)點的網(wǎng)絡中，最大化擴散效果

圖8 不同時間注入真相的謠言抑制效果對比

2) 輿論領袖節(jié)點不同

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

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

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

5 結(jié)束語

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

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

[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-），女，河北保定人，西安電子科技大學碩士生，主要研究方向為復雜網(wǎng)絡、移動和無線網(wǎng)絡安全。

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

王小琴（1990-），女，山西長治人，西安電子科技大學碩士生，主要研究方向為復雜網(wǎng)絡、移動和無線網(wǎng)絡安全。

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

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

國家自然科學基金資助項目（No.61671360）；信息保障重點實驗室基金資助項目（No.KJ-14-109）；中央高?；究蒲袠I(yè)務費基金資助項目（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)