基于有向圖的社交網絡欺詐用戶檢測方法

吳彥芳 張嬌嬌 王帥

摘 要：在線社交網絡的sybil賬戶日益猖獗，網絡攻擊者利用欺詐賬戶進行各種惡意活動，嚴重影響了社交網絡的正常秩序，危害了網絡用戶的個人隱私。現提出一種基于有向圖的欺詐用戶檢測方法。該方法優化了已有的GANG算法。通過基于全局社會結構，建立新的馬爾科夫隨機場，并優化置信傳播以優化檢測精度。實驗結果表明，優化后的GANG算法已有的算法更具有可擴展性和收斂性，且比基于無向圖的檢測方法精確度更高。

關鍵詞：有向圖；社交網絡；關聯推定

1 引 言

近幾年，在線社交網絡發展迅速，如我國的微信、微博、QQ等，國外的 Facebook、Twitter 等。社交網絡為人們提供了一個方便的、用來交流和分享的最佳平臺，也因此受到利益的驅動，社交網站也吸引了很多網絡攻擊者。通過制造大量非法虛假身份，網絡攻擊者會制造各種惡意活動，如發布“三無”信息、發送虛假郵件，收集個人信息等影響網絡中社交個體中繼選擇意愿，竊取社交個體隱私，嚴重威脅了社交網絡和用戶的安全。

網絡攻擊者賬戶有較為明顯的特征：通過前期大范圍的發送請求消息，以求通過此舉添加大量的合法網絡用戶為好友，為后續進行惡意網絡攻擊奠定基礎。加之移動互聯網時代的到來，網絡的適用性越來越廣泛，社交網絡欺詐造成的惡劣影響也顯著增加。

為此，計算機界對應對網絡欺詐用戶檢測提出了許多方案，這些方案一般都是基于一定的假設才能達到較好的效果，并且在實際應用中這些方案準確率較低，網絡欺詐者較容易躲避。針對此種情況，本文優化了GANG方法，進而有效改善現有方案中的準確率低，易躲避的情況。

2 相關工作和背景

已有的檢測方法中，有的利用無向的社交鏈接，這過度簡化了現實世界在線社交網絡的定向社交結構，大大限制了檢測的準確度。在這項工作中，我們提出GANG，一種關于有向圖的關聯推定方法，用于檢測在線社交網絡中的欺詐用戶。在GANG中，我們設計一個新的成對馬爾可夫隨機場來模擬有向社會圖中節點的聯合概率分布。該新型馬爾科夫隨機場具有欺詐用戶檢測問題的獨特特性。如果反向的邊（v，u） 不存在，我們稱之為單向邊（u，v） ，否則我們稱之為雙向邊。如果兩個用戶通過雙向邊鏈接并且具有相同的標簽，那么馬爾可夫隨機場會產生更大的聯合概率。 但是，假設u 和v 通過單向邊緣（u，v） 鏈接，例如，在Twitter上，u 跟隨v ，但v 不跟隨u 。如果u 是欺詐的或v 是正常的，那么單向邊 是否存在不會影響馬爾可夫隨機場下的聯合概率，否則邊（u，v） 會使聯合概率變大。這是因為欺詐用戶可以跟隨任意用戶而不會被追蹤，而普通用戶可以被任意用戶追蹤而不會追蹤他們。

在GANG的基本版本中，我們使用置信傳播（LBP）來估計給定實驗數據集中每個二元隨機變量的后驗概率分布，并用它來預測相應用戶的標簽。然而，基本版本有兩個缺點：1.它不夠可擴展，因為LBP需要在每個邊緣上維護消息，2.它不能保證收斂，因為LBP可能在循環圖上振蕩。因此，我們進一步優化GANG以解決這些缺點。我們的優化包括消除消息維護和通過簡潔的矩陣形式逼近GANG，我們還得出了優化GANG收斂的條件。

我們引入了一個新的成對馬爾可夫隨機場，馬爾可夫隨機場模擬所有u∈V 的所有二元隨機變量xu 的聯合概率分布。我們用xv 表示所有二進制隨機變量的集合。我們提出的馬爾科夫隨機場如下：

其中H（xv） 稱為能量函數。（u，v） 或（v，u） 出現在H（xv） 中，但兩者不會同時出現。

使用置信傳播（LBP）計算后驗概率分布：

在GANG的基本版本中，我們使用LBP來估計后驗概率分布Pr（xv） 。 LBP在圖中的相鄰節點之間迭代地傳遞消息。即在第t次迭代中從v發送到u 的消息 是 ：

其中Γ（v）/u 是接收節點u 之外的v 的所有鄰居的集合。該編碼中每個節點通過最后一次迭代的傳入消息轉發結果，并基于與接收方的同質性強度將該消息適配到相應的接收方。當消息的變化在兩次連續迭代中變得可忽略時LBP停止，或者它達到預定義的最大迭代次數T。LBP停止后，我們估計后驗信念Pr（xv） 如下：

這相當于

消除消息維護

GANG不夠可擴展的主要原因之一是LBP在每個邊都維護消息。 我們觀察到LBP需要在邊上維護信息的關鍵原因是當節點v 向其鄰居u 準備消息時，它需要排除u 發送給v 的消息。因此，我們的第一個優化步驟是當v 準備其消息給u 時包括u 發送給v 的消息 .形式上，我們修改公式（3）如下：

3 結構模型

假設給出了一個有向社交圖G（V，E） ，其中節點v∈V 代表用戶，是用戶的數┃V┃ 量，有向邊（u，v）∈E 表示u 和v 之間的某種關系。例如，這種關系可能是u 在Twitter上跟隨v ，在Facebook上u 向v 發送朋友請求， 或者u 在Facebook上接受來自v 的朋友請求。每個節點可以是欺詐性的或正常的。欺詐性節點包括垃圾郵件發送者，虛假用戶和受損用戶。

定義（基于有向圖的欺詐檢測）：假設我們被給予一個有向社交圖和一個由標記的欺詐和正常節點組成的訓練數據集。欺詐檢測目的是預測社交圖中每個剩余節點的標簽。

符號：如果邊（v，u） 不存在，我們將邊（u，v） 稱為單向。我們用圖中的E1 單向邊表示，例如， 。 如果邊（v，u） 也存在，我們稱之為邊（u，v） 雙向。我們用圖中的E2 雙向邊表示，即

4 實驗評估與結果分析

首先，我們獲得了一個Twitter的跟隨者與被跟隨者圖表，其中包含41，652，230個用戶和來自Kwak等人的1，468，364，884個邊[4]。有205，355名用戶被Twitter暫停，我們將其視為欺詐用戶； 36，156，909個用戶活躍，將其視為普通用戶； 其余5，289，966個用戶被刪除，將它們視為未標記的用戶。隨機抽取500，000個標記用戶作為實驗集，并將剩余的標記用戶視為測試集。

其次，我們從Fu等人的[5]中獲得了一個包含3538，487個用戶和652，889，971條有向邊的新浪微博數據集。手工標記了隨機抽樣的2000名用戶。其中，欺詐用戶482名，正常用戶1498名，未知用戶20名。我們將欺詐用戶和普通用戶分成兩部分；一個作為實驗集，另一個作為測試集。表1顯示了我們數據集的一些統計數據。

表1 數據集統計

數據集 Twitter Sina Weibo

節點 4165230 3538487

邊 1468364884 652889971

平均度 71 369

我們將優化后的GANG算法與其他方法進行比較。

我們考慮以下基于有向圖的方法：TrustRank、DistrustRank、CIA和CatchSync。TrustRank、DistrustRank和CIA都是基于隨機游走，而CatchSync會利用[3]進行測試。TrustRank和DistrustRank最初是為了檢測基于超鏈接的欺詐網頁而設計的，但它們可以用于檢測在線社交網絡中的欺詐用戶。TrustRank僅利用實驗數據集中標記的正常節點；DistrustRank和CIA本質上是一樣的，他們只利用標記為欺詐的節點；而CatchSync不使用實驗數據集。

表2 有向圖的各種方法AUC值的比較

方法 Twitter Sina Weibo

TrustRank 0.60 0.66

DistrustRank 0.63 0.64

CIA 0.63 0.64

CatchSync 0.68 0.51

GANG 0.72 0.80

整體排名表現：我們首先使用AUC來衡量比較方法的整體排名表現。AUC可以解釋為在測試數據集中，一個隨機抽樣的欺詐節點排名高于一個隨機抽樣的正常節點的概率。AUC越高，性能越好。表2顯示了Twitter和新浪微博數據集上所有比較方法的AUC。我們觀察到GANG在兩個數據集上始終優于所有的比較方法。

5 總 結

為了防范社交網絡中越來越多的欺詐用戶的攻擊，和隨之帶來的越來越惡劣的影響，本文設計的基于有向圖的社交網絡欺詐用戶檢測方法可以起到較好的作用——較高的識別率。此方法通過有向圖的關聯推定來檢測社交網絡中的欺詐用戶。在GANG中，我們設計了一個新的成對馬爾可夫隨機場來模擬有向社會圖中節點的聯合概率分布。該新型馬爾科夫隨機場具有欺詐用戶檢測問題的獨特特性。

在實驗結果的評估上，通過對比其他算法，結果顯示在檢測社交網絡欺詐用戶的識別率和準確性上，本文提出的優化算法檢測效率最高，而其他四種算法為目前使用較為普遍的檢測算法。因此，本文提出的優化算法可以更加有效的檢測出社交網絡中的欺詐用戶，減少社交網絡欺詐用戶對社交網絡和正常用戶造成的危害和惡劣影響。

參考文獻：

[1] 吳大鵬，司書山，閆俊杰，王汝言.基于行為特征分析的社交網絡女巫節點檢測機制[A].電子與信息學報，2017，39（9）.

[2] 周清清，陳志剛，黃 瑞，李 博，徐成林.在線社交網絡Sybil賬號檢測[A].小型微型計算機系統，2017，（8）.

[3] J. Kleinberg， “Authoritative sources in a hyperlinked environment，”Journal of the ACM， vol. 46， no. 5， 1999.

[4] H. Kwak， C. Lee， H. Park， and S. Moon， “What is twitter， a social

network or a news media？” in WWW， 2010.

[5] H. Fu， X. Xie， Y. Rui， N. Z. Gong， G. Sun， and E. Chen， “Robust

spammer detection in microblogs： Leveraging user carefulness，” ACM

Transactions on Intelligent Systems and Technology （TIST）， 2017.

作者簡介：

吳彥芳，生于1996年12月，女，漢族，河南民權人，南京郵電大學本科在讀，物聯網工程專業.

*【基金項目】本文系南京郵電大學2018年度大學生實踐創新訓練計劃項目，項目編號XYB2018284