基于交互行為的在線社會網絡水軍檢測方法

陳侃，陳亮，朱培棟，熊岳山

(國防科學技術大學 計算機學院，湖南 長沙410073)

1 引言

網絡水軍出于政治或經濟等目的對在線社會網絡中的信息進行推廣，使目標信息在極短的時間內大范圍擴散，同時利用數量優勢影響用戶對其真實性的判斷。根據內容和功能的不同，常見目標信息包括廣告、木馬和惡意鏈接、謠言等。廣告水軍以病毒營銷的方式發布目標產品的不實描述，誘導用戶對產品真實質量產生誤判。病毒、木馬和釣魚網站被隱藏在正常內容中，或以中獎等方式吸引用戶點擊，通過超鏈接重定向到惡意程序所在的頁面感染用戶。謠言傳播目的在于散布謠言并說服他人，不僅能夠引導社會輿論，還可能引發大范圍社會恐慌，甚至對國家安全和社會穩定造成威脅[1]。近年來爆發了多起網絡造謠事件，例如“搶鹽風波”[2]、“地震謠言”[3]等，對人民生活和社會治安造成嚴重困擾和威脅。

網絡水軍已成為工業界和學術界面臨的重要課題，多種網絡水軍檢測方法也被提出，如基于文本的方法[4]、基于黑名單的方法[5]和基于用戶特征[6]的方法等。其中基于文本的方法適用于具有明顯關鍵字的水軍信息，如廣告等；基于黑名單的方法適用于檢測包含惡意鏈接的水軍信息；基于用戶行為模式的方法適用于檢測具有明顯水軍特征的水軍用戶。這些檢測方法局限性在于都只能檢測單一種類的水軍，在海量信息的條件下為保證低漏檢率需要綜合使用，從而增加檢測的復雜性和時空耗費。因此設計一個通用性的檢測方法具有重要意義。

本文提出了一種基于傳播交互的水軍檢測方法。在線社會網絡中，用戶交互是引起信息傳播的根本途徑。水軍雖然種類多樣，但在交互行為上具有共同特性，而且與正常用戶的交互行為表現出明顯差異，因此從傳播交互角度出發進行檢測更具有通用性。

2 相關研究工作

近年來，隨著在線社會網絡的流行，網絡水軍越來越多地以在線社會網絡作為水軍活動的主要平臺，知名網站如 Facebook、Twitter和 Myspace等都已經成為了水軍活動的重要場所[5～7]。其他諸如論壇[8]、視頻共享網站[9]、博客[10]等在內的在線網絡也都已成為網絡水軍發動水軍攻擊的平臺[11]。

水軍檢測可分為人員檢測和信息檢測，二者檢測對象不同。人員檢測針對水軍成員，信息檢測針對水軍傳播的信息。檢測的一般觀點是抽取特征，并利用特征分離水軍成員或水軍信息。

Irani通過用戶注冊信息對水軍成員進行檢測[6]，這種方法使檢測可以在用戶注冊時進行，但準確性較低，水軍用戶也可以隨時更改信息逃避檢測。Benevenut使用SVM分類器對Twitter中網絡水軍進行檢測[12]，使用的特征包括信息中包含鏈接的比例、用戶賬號使用時間、關注者的關注比例等。Wang利用Twitter中25 847個用戶信息對網絡水軍進行檢測[13]，檢測特征包括關注與被關注度、轉發數量、雙向交互數量以及鏈接比例等。

信息檢測主要是根據信息內容分析水軍特征，例如信息中鏈接特征以及基于自然語言處理的文本分類[14]。Zhang使用基于鏈接相似性的方法關聯水軍活動[15]，并采用基于機器學習的方法對可能的水軍活動進行檢測。Blacklist方法利用知名的blacklist站點來檢測包含惡意鏈接的水軍信息。Gao使用此方法對 Facebook留言墻中包含惡意鏈接的信息進行分析[16]。Grier研究了Twitter傳播信息中的惡意鏈接[5]，結果表明Twitter上8%的鏈接都被重定向到惡意網站。他的工作還證明blacklist無法解決新的威脅，當一個惡意鏈接被標注為 blacklist之前已經有超過90%的用戶被感染。文本內容也是水軍檢測的重要特征。Raymond通過分析評論文本與正常用戶評論的差異來發現網絡水軍發布的虛假評論[4]。Chen利用回復、積極性及語義特征對新聞網絡上的網絡水軍信息進行檢測，可以提供95%的檢測準確率[17]。

當前網絡水軍檢測的難點一方面在于檢測的準確性有待提高，另一方面在于水軍種類多樣，賬號多變，而檢測方法大都只面向于單一種類的水軍，無法提供通用的檢測方案。為了保證檢測的準確性需要同時使用多種檢測機制，造成系統復雜性的提升和計算量的增加。

3 基于交互行為的信息傳播模型

雇用網絡水軍的目的在于信息傳播，雇主將產品、言論或觀點在在線社會網絡中推廣，一方面需要增加信息傳播廣度，使其對更多用戶可見；另一方面需要增加信息可信度，從而能夠更好地影響用戶，這些都是通過用戶交互來實現的。

用戶交互是信息傳播的基本方式和根本動力。根據平臺不同，交互類型也有不同，例如關注、轉發、評論、點贊、收藏等。其中關注、轉發和評論是在線社會網絡中通用的交互方式。

關注：A關注B之后，B新發布的信息會實時推送給A。

轉發：A轉發B的信息，該信息從B的頁面復制到A的頁面，引起信息傳播。

評論：A評論B的信息，評論內容仍在B的頁面顯示，不會引起信息傳播，但會對信息可信性和說服力造成影響。

雖然水軍種類多樣，而且水軍賬號不斷變化，但從信息傳播的角度來看，無論水軍信息還是正常信息都有其固有的傳播模式。這些模式體現在用戶之間的交互上，從這3種交互行為入手對網絡水軍和正常用戶在信息傳播中的行為差異進行分析，就能為水軍信息檢測提供通用性的檢測方案。

用F(u)、R(u)、C(u)分別表示用戶u的關注、轉發和評論集合。其中，F(u)是由其他用戶組成的無序集合；R和C中的元素為類似＜user,time＞的二元組，user代表發布信息的用戶，time為信息發布時間，集合按照time排序。

由于轉發和評論在行為上都表現為信息的再發布，行為表現和特征描述都具有相似性。為避免重復將轉發和評論通稱為傳播，傳播集合用D(u)表示。根據交互主體的不同，將傳播特征分為關注者-傳播者、發布者-傳播者、傳播者-傳播者3種類型。其關系如圖1所示。

圖1 基于交互行為的信息傳播模型

3.1 關注者-傳播者特征定義

信息傳播的前提是信息可見，在線社會網絡中用戶A發布的信息對用戶B可見的方式主要有以下幾種。

1)B關注A，B就可以實時獲得A的更新。由于在線社會網絡中推送機制的廣泛使用，新的信息發布后會立即推送給關注者。

2)B關注C，C轉發A的信息。那么B就可以通過C間接訪問到A發布的信息。B和A之間可能存在多跳。

3)B直接獲取A發布信息的鏈接，通過鏈接訪問。

通過觀察發現一般用戶主要通過前2種方式訪問信息，而網絡水軍則主要通過第3種方式訪問目標信息。這是因為水軍與雇主之間通常不存在直接的關注關系，只能通過雇主給出的鏈接進行信息傳播。這使網絡水軍與正常用戶在關注-傳播關系上產生明顯差異。

定義傳播關系分布用來衡量傳播者與關注者之間的關系，用DR表示傳播關系分布，p為一條信息，u為信息發布者，DR的計算式為

其中，P(u)為用戶u發布的所有信息，|D(p)|表示集合D(p)的元素數量。DR用來衡量傳播者同時也是關注者的比例，正常用戶主要通過關注關系獲取信息，而網絡水軍主要通過鏈接方式獲取信息，因此造成DR值的差異。

3.2 發布者-傳播者特征定義

發布者與傳播者之間進行直接交互，從交互時間的角度定義了平均傳播時間（ADT）、首次傳播時間（FDT）和傳播啟動時間（DST）3個特征。

1) 平均傳播時間

傳播時間為信息從發布到最末一次傳播的總時間，平均傳播時間用來描述每一條轉發/評論的平均持續時間。用ADT表示平均傳播時間，計算式為

其中，N=|D(p)|，由于D(p)是按照時間排序的，因此

網絡水軍通過完成雇主發布的傳播任務獲取報酬，而報酬是有限的，如果任務完成數量超出獎勵限額就不會獲得報酬。因此網絡水軍期望在任務期限內盡可能早地完成任務，而且任務完成數量一旦達到限額就不會再對信息進行傳播。正常信息的傳播僅受限于用戶的使用習慣，傳播時間與傳播范圍都沒有具體的界限。

2) 首次傳播時間

首次傳播時間用來描述從信息發布到獲得第一條轉發/評論所等待的時間，用FDT表示首次傳播時間，計算式為

其中，d1為D(p)中第一個元素。

由于消息實時推送機制的廣泛使用以及移動終端應用的大力推廣，很多在線社會網絡都具有“類實時”特性，用戶之間能夠以近似實時的方式進行交互，信息也能夠在第一時間被關注者傳播。而網絡水軍訪問目標信息的方式通常不是通過對被關注者的推送，而是通過給定的鏈接，因此難以體現出實時特性。同時水軍活動任務的發布、接受、和實施都需要耗費一定的時間，使水軍信息的首次傳播時間比正常信息更長。

3) 傳播啟動時間

傳播啟動時間用來描述一條信息變“可信”所需要的時間。當一條信息的轉發和評論量達到一定程度時，能夠吸引更多用戶關注并影響用戶對信息內容的判斷。用DST表示傳播啟動時間，計算式為

其中，m為可信參數，用來描述一條信息產生影響力所需要的轉發/評論的數量。本文中定義m=1 000。即認為一條信息的轉發/評論量超過1 000就能對用戶判斷產生影響。

3.3 傳播者-傳播者特征定義

傳播者與傳播者之間并沒有或很少直接交互，只是在與發布者交互時產生時序關系。對該時序關系進行分析可以更好地理解傳播者參與的積極性和行為規律。從傳播者-傳播者角度定義了平均傳播間隔（ADI）和傳播間隔方差（VDI）2個特征。

1) 平均傳播間隔

傳播時間間隔為每兩條相鄰信息之間的時間間隔，平均傳播間隔為所有傳播時間間隔的均值。其計算式為

由于水軍行為多集中在短時間之內進行，呈現出突發特性，因此每2條相鄰信息之間的時間間隔都很小。而正常用戶發布的信息出于個人使用習慣的差異，時間間隔相對更大。

2) 傳播間隔方差

傳播間隔方差為所有的傳播間隔之間的方差，用來描述一條信息的所有轉發或評論的時間間隔的差異程度，計算方法為

水軍行為的突發性不僅表現在時間間隔短，而且間隔分布也處于一個相對較小的范圍內。而普通用戶的轉發和評論受訪問習慣的影響表現出更大的差異性。

4 基于決策樹的水軍檢測方法

將網絡水軍檢測問題看作二分類問題，設P為在線社會網絡中所有信息集合，P= {PsUPn}，其中，Ps為網絡水軍推廣的信息集合，Pn為正常信息集合。設p為一條信息,使用特征向量表示為目標函數為，其中，φ(p)為二分類函數，網絡水軍檢測即發現信息p是否屬于集合Ps。

針對二分類問題當前已經有多種方案，例如決策樹、SVM、Bayes、神經網絡方法等。分類流程包括訓練和分類2部分，訓練過程通過特征選取和分類訓練構造分類器，分類過程使用分類器對新的樣本實現分類。本文選取決策樹C5算法作為分類檢測算法。C5算法采用Boosting方式提高模型準確率，更適合在線社會網絡這類數據量較大的場景。

決策樹的根節點為數據樣本集，分支節點對應著對單一屬性的測試，該測試將數據空間分割為多個子集。每條分支對應該屬性的不同屬性值，而葉節點是帶有分類標記的樣本集分割。決策樹需要使用訓練集構建，然后實現對新樣本的分類檢測。

首先定義相關概念如下。

信息熵：在樣本集S中，依據目標屬性（是否為水軍信息）將S分為NS和SS這2個子集，則S的信息熵計算為

信息增益：屬性D的信息增益Gain(Di)計算為

信息增益比率：屬性D的信息增益比率計算為

借助各屬性的信息增益比率構建檢測決策樹。設訓練數據集S=D1D2D3D4D5D6為6維向量空間，其中，Di(1≤i≤6)分別對應模型中定義的6種特征。決策樹構建算法如下。

算法1基于傳播特征的決策樹構建算法

輸入訓練數據集S

輸出決策樹DT

1) 初始化，設t=S為DT的根節點。

2) 計算當前樣本節點t的信息熵，以及t中每個特征屬性Di的信息增益比率GainRatio(Di)。

3) 令Dk=max{GainRatio(Di)}，根據Dk的取值將t劃分為m個子集，每個子集為t的一個分支，對應一個新的決策樹節點。

4) 依次設每個新的決策樹節點為當前樣本節點，重復步驟 2)～4)，直到所有新樣本節點中的樣本滿足：①都屬于同一目標類；②所有屬性都處理完畢；③樣本的剩余屬性取值完全相同。并將這樣的節點標記為葉節點。

5) 用所有葉節點中占多數的目標分類屬性值來標記該葉節點，決策樹構建完成，返回DT。

構造成功之后，就可以使用決策樹對新的樣本值進行目標屬性的分類檢測。從決策樹的根節點開始，測試比較這個節點對應的屬性值，然后選擇正確分支向葉節點移動，重復比較和分支過程，直到到達葉節點，葉節點的類別屬性即為最終的分類檢測結果。

5 實驗和分析

5.1 數據準備

從新浪微博中抓取真實數據分析傳播特征。水軍活動以很多方式存在，如廣告水軍、意見水軍、木馬病毒水軍等。盡管內容和功能各有不同，但都以同樣的方式被組織和傳播。其中廣告水軍更常見也更容易區分，因此使用廣告水軍作為原型來分析其傳播特征。

首先通過人工方式對新浪微博中的水軍廣告進行標注，然后提取這些廣告信息中的關鍵字。利用新浪微博提供的搜索引擎使用這些關鍵字進行搜索，并保存搜索結果。

一般地，很多用戶在看到廣告時會選擇忽略，極少參與轉發或評論。在搜索結果中，80%的廣告微博的轉發和評論次數少于10次，大多數為0次。此外約10%的微博具有很高的轉發和評論量，認為它們較大概率來自于網絡水軍。過濾掉少于100次評論和轉發的微博，最后得到1 424條水軍數據集。

為了與水軍數據進行對比，還搜集了正常用戶的微博數據。采用手動方式挑選一些較小概率雇用網絡水軍的用戶，選取方式是：①熟悉的用戶，如朋友或老師；②教育或科學界的知名人士。選擇教育或科學界人士是因為認為相比其他行業，這些用戶更小概率會雇用網絡水軍。抓取了這些用戶在 4月1日到4月14日之間的所有微博。同樣過濾掉少于100次評論和轉發的微博，最后得到1 687條正常數據集。

5.2 傳播特征統計分析

使用抓取到的數據集對水軍用戶和正常用戶的傳播特征進行分析，各項特征的累積分布如圖 2所示。

圖2給出了傳播關系分布（DR）特征的累積分布，可看出水軍信息的特征值遠小于正常信息的特征值。在轉發特征圖中，80%的水軍信息的DR值小于 0.2，說明 80%的水軍信息中，由關注者給出的轉發不到總量的20%。與之形成對比的是約80%的正常信息的DR值大于0.2。這一對比在評論特征圖中更加明顯，80%的水軍信息的DR值小于0.1，說明80%的水軍信息中，僅有不到10%的轉發和評論來自于關注者。這一分布證明了正常信息的轉發和評論主要來源于關注者，而水軍信息的轉發和評論主要來源于陌生人。

圖2 基于轉發和評論的DR累積分布

圖3給出了平均傳播時間的累積分布，從圖中可以看出，80%的水軍轉發信息平均持續時間少于20 min，而90%的正常用戶的平均持續時間都大于20 min。此外，80%的水軍評論信息平均持續時間少于30 min，相同時間下正常評論信息只有不到5%。

圖4給出了首次傳播時間的累積分布，可以看出水軍和正常信息在FDT上分布差異性明顯。約90%以上的正常信息都可以在10 min之內獲取到第一條轉發和評論。而在相同時間之內，水軍信息中只有10%能夠獲取到第一條轉發，18%能獲取到第一條評論。在1 min內，約45%的正常信息可以獲得第一條轉發和評論，而水軍信息中只有2%可以獲得第一條轉發，7%獲得第一條評論。

圖3 基于轉發和評論的ADT累積分布

圖4 基于轉發和評論的FDT累積分布

圖5給出了傳播啟動時間的累積分布。從圖中可看出正常信息的啟動時間一般小于水軍信息。60%的正常信息的轉發啟動時間小于200 min，該時間之內只有20%的水軍信息獲得應有的轉發。DST特征的差異性不如其他特征明顯，評論特征更為相近。

圖5 基于轉發和評論的DST累積分布

圖6給出了平均傳播間隔的累計分布。從數量上看，水軍信息的平均傳播間隔小于正常信息。60%的水軍轉發和評論間隔都小于10 min，而在此范圍內的正常信息不到 10%。此外 25%的水軍轉發和35%的水軍評論的平均傳播間隔都在1 min之內，這證明了水軍信息轉發和評論時的突發特性。

圖6 基于轉發和評論的ADI累積分布

圖7給出了傳播間隔方差的累計分布。水軍信息傳播間隔的方差更小，說明水軍信息的傳播間隔之間的差異性更小。原因是水軍信息的突發特性使時間間隔都相對集中在一個小范圍內，而正常信息受用戶使用習慣的影響差異性更大。

5.3 檢測結果

將數據集分為訓練集和測試集，比例為7:3。按照算法1的描述對訓練集進行分類訓練，得到決策樹如圖8所示。利用該樹可以直接進行水軍檢測。

圖7 基于轉發和評論的VDI累積分布

圖8 基于交互行為特征的水軍檢測決策樹

使用測試集對決策樹檢測方法的有效性進行驗證，并同時對比了SVM算法以及神經網絡的RBF算法，驗證結果如表1所示。

表1 檢測方法結果對比

結果表明本文的決策樹算法在基于傳播模型的網絡水軍檢測方面具有明顯優勢，準確率和召回率都高于其他2種方法。其中，SVM算法可以提供較高的準確率，但召回率難以保證，漏檢率較高。RBF算法的召回率有所提升，但仍大幅度低于決策樹算法。從綜合評價來看，決策樹算法性能最優，其次是RBF算法，SVM算法由于召回率過低因此性能最差。

文獻[18]使用概念圖模型對新浪微博中的水軍進行檢測，基于平臺和檢測對象的相似性，使用它作為參考與本文的檢測方法進行對比，結果如表 2所示?？梢钥闯?，無論是在準確率、召回率還是綜合評價上，本文的檢測方法都表現出明顯優勢。這也證明了本文方法能夠有效且準確地對水軍進行檢測。

表2 檢測結果對比

對檢測算法中各特征的重要性進行了分析，結果如圖9所示。重要性按由高到低的順序排名依次是FDT＞DR＞ADI＞ADT＞VDI＞DST。

圖9 特征重要性評估

檢測結果的高準確性證明了傳播模型中特征選取的有效性，說明本文定義的特征能夠準確描述網絡水軍和正常用戶行為和傳播過程的差異。正常用戶可以根據關注關系實時獲取更新提醒，而網絡水軍需要跟蹤雇主發布的任務進行消息傳播。正常用戶對信息的訪問和傳播基于自己的日常習慣，而網絡水軍的消息傳播依賴于任務發布時間和任務限額。

6 結束語

本文提出了基于交互行為的信息傳播模型，從交互關系的角度定義了3種6個特征對傳播行為進行量化。在此模型之下利用決策樹算法對網絡水軍傳播的信息進行檢測。利用新浪微博的真實數據對傳播模型進行分析并驗證檢測方法的有效性，結果表明本文的方法可以高效地檢測出網絡水軍。盡管網絡水軍在種類功能方面各有差異，但傳播行為上的共性使得本文的檢測方法更具有通用性，可以適用于多場景下的水軍檢測。

[1] http://news.ifeng.com/opinion/special/wangluoshuijun/[EB/OL].

[2] http://zh.wikipedia.org/zh-cn/%E7%9B%B2%E6%8%A2%E7%9B%90%E4%BA%8B%E4%BB%B6[EB/OL].

[3] http://qcyn.sina.com.cn/news/ynyw/2011/1205/01134061411.html[EB/OL].

[4] RAYMOND Y K, STEPHEN L, LIAO S Y. Text mining and probabilistic language modeling for online review spam detection[J]. ACM Trans Management Inf Syst, 2011,2(4):25.

[5] GRIER C, THOMAS K, PAXSON V,et al. @spam: the underground on 140 characters or less[A]. Proceedings of the 17th ACM Conference on Computer and Communications Security[C]. Chicago, Illinois, USA, 2010. 27-37.

[6] IRANI D, WEBB S, PU C. Study of static classification of social spam profiles in MySpace[A]. ICWSM[C]. 2010.

[7] THOMAS K, GRIER C, SONG D,et al. Suspended accounts in retrospect: an analysis of twitter spam[A]. Proceedings of the 2011 ACM SIGCOMM Conference on Internet Measurement Conference[C].Berlin, Germany, 2011. 243-258.

[8] SHIN Y, GUPTA M, MYERS S. Prevalence and mitigation of forum spamming[A]. IEEE INFOCOM 2011[C]. 2011. 2309-2317.

[9] BENEVENUTO F, RODRIGUES T, ALMEIDA V,et al. Identifying video spammers in online social networks[A]. Proceedings of the 4th International Workshop on Adversarial Information Retrieval on the Web[C]. Beijing, China, 2008. 45-52.

[10] RAJADESINGAN A. MAHENDRAN A. Comment spam classi-fication in blogs through comment analysis and comment-blog post relationships[A]. Proceedings of the 13th International Conference on Computational Linguistics and Intelligent Text Processing-Volume Part II[C]. New Delhi, India: Springer-Verlag,2012.490-501.

[11] HEYMANN P, KOUTRIKA G, GARCIA-MOLINA H. Fighting spam on social Web sites: a survey of approaches and future challenges[J].IEEE Internet Computing, 2007, 11(6):36-45.

[12] BENEVENUTO F, MAGNO G, RODRIGUES T,et al. Detecting spammers on twitter[A]. CEAS[C]. 2010.

[13] WANG A H. Detecting spam bots in online social networking sites: a machine learning approach[A]. Data and Applications Security and Privacy, 25th Anunual IFIP WG11.3 Conference[C]. 2010. 335-342.

[14] 蘇金樹, 張博鋒, 徐昕等. 基于機器學習的文本分類技術研究進展[J]. 軟件學報, 2006, 19(9):1848-1859.SU J S, ZHANG B F, XU X,et al. Advances in machine learning based text categorization[J]. Journal of Software, 2006, 19(9):1848-1859.

[15] ZHANG X, ZHU S, LIANG W. Detecting spam and promoting campaigns in the Twitter social network[A]. The 12th IEEE International Conference on Data Mining[C]. 2012.1194-1199.

[16] GAO H, HU J, WILSON C,et al. Detecting and characterizing social spam campaigns[A]. The 10th ACM SIGCOMM Conference on Internet Measurement[C]. Melbourne, Australia, 2010.

[17] CHEN C, WU K, SRINIVASAN V,et al. Battling the internet water army: detection of hidden paid posters[EB/OL]. arXiv preprint ar-Xiv:1111.4297v1[cs.SI]. 2011.

[18] 韓忠明等. 面向微博的概率圖水軍識別模型[J]. 計算機研究與發展, 2013, S2:180-186.HAN Z M, XU F M, DUAN D G. Probabilistic graphical model for identifying water army in microblogging system[J]. Journal of Computer Research and Development, 2013, S2:180-186.