吳彥芳 張嬌嬌 王帥

摘 要：在線社交網(wǎng)絡(luò)的sybil賬戶日益猖獗，網(wǎng)絡(luò)攻擊者利用欺詐賬戶進(jìn)行各種惡意活動(dòng)，嚴(yán)重影響了社交網(wǎng)絡(luò)的正常秩序，危害了網(wǎng)絡(luò)用戶的個(gè)人隱私?，F(xiàn)提出一種基于有向圖的欺詐用戶檢測(cè)方法。該方法優(yōu)化了已有的GANG算法。通過基于全局社會(huì)結(jié)構(gòu)，建立新的馬爾科夫隨機(jī)場(chǎng)，并優(yōu)化置信傳播以優(yōu)化檢測(cè)精度。實(shí)驗(yàn)結(jié)果表明，優(yōu)化后的GANG算法已有的算法更具有可擴(kuò)展性和收斂性，且比基于無向圖的檢測(cè)方法精確度更高。

關(guān)鍵詞：有向圖；社交網(wǎng)絡(luò)；關(guān)聯(lián)推定

1 引 言

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

網(wǎng)絡(luò)攻擊者賬戶有較為明顯的特征：通過前期大范圍的發(fā)送請(qǐng)求消息，以求通過此舉添加大量的合法網(wǎng)絡(luò)用戶為好友，為后續(xù)進(jìn)行惡意網(wǎng)絡(luò)攻擊奠定基礎(chǔ)。加之移動(dòng)互聯(lián)網(wǎng)時(shí)代的到來，網(wǎng)絡(luò)的適用性越來越廣泛，社交網(wǎng)絡(luò)欺詐造成的惡劣影響也顯著增加。

為此，計(jì)算機(jī)界對(duì)應(yīng)對(duì)網(wǎng)絡(luò)欺詐用戶檢測(cè)提出了許多方案，這些方案一般都是基于一定的假設(shè)才能達(dá)到較好的效果，并且在實(shí)際應(yīng)用中這些方案準(zhǔn)確率較低，網(wǎng)絡(luò)欺詐者較容易躲避。針對(duì)此種情況，本文優(yōu)化了GANG方法，進(jìn)而有效改善現(xiàn)有方案中的準(zhǔn)確率低，易躲避的情況。

2 相關(guān)工作和背景

已有的檢測(cè)方法中，有的利用無向的社交鏈接，這過度簡(jiǎn)化了現(xiàn)實(shí)世界在線社交網(wǎng)絡(luò)的定向社交結(jié)構(gòu)，大大限制了檢測(cè)的準(zhǔn)確度。在這項(xiàng)工作中，我們提出GANG，一種關(guān)于有向圖的關(guān)聯(lián)推定方法，用于檢測(cè)在線社交網(wǎng)絡(luò)中的欺詐用戶。在GANG中，我們?cè)O(shè)計(jì)一個(gè)新的成對(duì)馬爾可夫隨機(jī)場(chǎng)來模擬有向社會(huì)圖中節(jié)點(diǎn)的聯(lián)合概率分布。該新型馬爾科夫隨機(jī)場(chǎng)具有欺詐用戶檢測(cè)問題的獨(dú)特特性。如果反向的邊（v，u） 不存在，我們稱之為單向邊（u，v） ，否則我們稱之為雙向邊。如果兩個(gè)用戶通過雙向邊鏈接并且具有相同的標(biāo)簽，那么馬爾可夫隨機(jī)場(chǎng)會(huì)產(chǎn)生更大的聯(lián)合概率。 但是，假設(shè)u 和v 通過單向邊緣（u，v） 鏈接，例如，在Twitter上，u 跟隨v ，但v 不跟隨u 。如果u 是欺詐的或v 是正常的，那么單向邊 是否存在不會(huì)影響馬爾可夫隨機(jī)場(chǎng)下的聯(lián)合概率，否則邊（u，v） 會(huì)使聯(lián)合概率變大。這是因?yàn)槠墼p用戶可以跟隨任意用戶而不會(huì)被追蹤，而普通用戶可以被任意用戶追蹤而不會(huì)追蹤他們。

在GANG的基本版本中，我們使用置信傳播（LBP）來估計(jì)給定實(shí)驗(yàn)數(shù)據(jù)集中每個(gè)二元隨機(jī)變量的后驗(yàn)概率分布，并用它來預(yù)測(cè)相應(yīng)用戶的標(biāo)簽。然而，基本版本有兩個(gè)缺點(diǎn)：1.它不夠可擴(kuò)展，因?yàn)長(zhǎng)BP需要在每個(gè)邊緣上維護(hù)消息，2.它不能保證收斂，因?yàn)長(zhǎng)BP可能在循環(huán)圖上振蕩。因此，我們進(jìn)一步優(yōu)化GANG以解決這些缺點(diǎn)。我們的優(yōu)化包括消除消息維護(hù)和通過簡(jiǎn)潔的矩陣形式逼近GANG，我們還得出了優(yōu)化GANG收斂的條件。

我們引入了一個(gè)新的成對(duì)馬爾可夫隨機(jī)場(chǎng)，馬爾可夫隨機(jī)場(chǎng)模擬所有u∈V 的所有二元隨機(jī)變量xu 的聯(lián)合概率分布。我們用xv 表示所有二進(jìn)制隨機(jī)變量的集合。我們提出的馬爾科夫隨機(jī)場(chǎng)如下：

其中H（xv） 稱為能量函數(shù)。（u，v） 或（v，u） 出現(xiàn)在H（xv） 中，但兩者不會(huì)同時(shí)出現(xiàn)。

使用置信傳播（LBP）計(jì)算后驗(yàn)概率分布：

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

其中Γ（v）/u 是接收節(jié)點(diǎn)u 之外的v 的所有鄰居的集合。該編碼中每個(gè)節(jié)點(diǎn)通過最后一次迭代的傳入消息轉(zhuǎn)發(fā)結(jié)果，并基于與接收方的同質(zhì)性強(qiáng)度將該消息適配到相應(yīng)的接收方。當(dāng)消息的變化在兩次連續(xù)迭代中變得可忽略時(shí)LBP停止，或者它達(dá)到預(yù)定義的最大迭代次數(shù)T。LBP停止后，我們估計(jì)后驗(yàn)信念Pr（xv） 如下：

這相當(dāng)于

消除消息維護(hù)

GANG不夠可擴(kuò)展的主要原因之一是LBP在每個(gè)邊都維護(hù)消息。 我們觀察到LBP需要在邊上維護(hù)信息的關(guān)鍵原因是當(dāng)節(jié)點(diǎn)v 向其鄰居u 準(zhǔn)備消息時(shí)，它需要排除u 發(fā)送給v 的消息。因此，我們的第一個(gè)優(yōu)化步驟是當(dāng)v 準(zhǔn)備其消息給u 時(shí)包括u 發(fā)送給v 的消息 .形式上，我們修改公式（3）如下：

3 結(jié)構(gòu)模型

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

定義（基于有向圖的欺詐檢測(cè)）：假設(shè)我們被給予一個(gè)有向社交圖和一個(gè)由標(biāo)記的欺詐和正常節(jié)點(diǎn)組成的訓(xùn)練數(shù)據(jù)集。欺詐檢測(cè)目的是預(yù)測(cè)社交圖中每個(gè)剩余節(jié)點(diǎn)的標(biāo)簽。

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

4 實(shí)驗(yàn)評(píng)估與結(jié)果分析

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

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

表1 數(shù)據(jù)集統(tǒng)計(jì)

數(shù)據(jù)集 Twitter Sina Weibo

節(jié)點(diǎn) 4165230 3538487

邊 1468364884 652889971

平均度 71 369

我們將優(yōu)化后的GANG算法與其他方法進(jìn)行比較。

我們考慮以下基于有向圖的方法：TrustRank、DistrustRank、CIA和CatchSync。TrustRank、DistrustRank和CIA都是基于隨機(jī)游走，而CatchSync會(huì)利用[3]進(jìn)行測(cè)試。TrustRank和DistrustRank最初是為了檢測(cè)基于超鏈接的欺詐網(wǎng)頁而設(shè)計(jì)的，但它們可以用于檢測(cè)在線社交網(wǎng)絡(luò)中的欺詐用戶。TrustRank僅利用實(shí)驗(yàn)數(shù)據(jù)集中標(biāo)記的正常節(jié)點(diǎn)；DistrustRank和CIA本質(zhì)上是一樣的，他們只利用標(biāo)記為欺詐的節(jié)點(diǎn)；而CatchSync不使用實(shí)驗(yàn)數(shù)據(jù)集。

表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

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

5 總 結(jié)

為了防范社交網(wǎng)絡(luò)中越來越多的欺詐用戶的攻擊，和隨之帶來的越來越惡劣的影響，本文設(shè)計(jì)的基于有向圖的社交網(wǎng)絡(luò)欺詐用戶檢測(cè)方法可以起到較好的作用——較高的識(shí)別率。此方法通過有向圖的關(guān)聯(lián)推定來檢測(cè)社交網(wǎng)絡(luò)中的欺詐用戶。在GANG中，我們?cè)O(shè)計(jì)了一個(gè)新的成對(duì)馬爾可夫隨機(jī)場(chǎng)來模擬有向社會(huì)圖中節(jié)點(diǎn)的聯(lián)合概率分布。該新型馬爾科夫隨機(jī)場(chǎng)具有欺詐用戶檢測(cè)問題的獨(dú)特特性。

在實(shí)驗(yàn)結(jié)果的評(píng)估上，通過對(duì)比其他算法，結(jié)果顯示在檢測(cè)社交網(wǎng)絡(luò)欺詐用戶的識(shí)別率和準(zhǔn)確性上，本文提出的優(yōu)化算法檢測(cè)效率最高，而其他四種算法為目前使用較為普遍的檢測(cè)算法。因此，本文提出的優(yōu)化算法可以更加有效的檢測(cè)出社交網(wǎng)絡(luò)中的欺詐用戶，減少社交網(wǎng)絡(luò)欺詐用戶對(duì)社交網(wǎng)絡(luò)和正常用戶造成的危害和惡劣影響。

參考文獻(xiàn)：

[1] 吳大鵬，司書山，閆俊杰，王汝言.基于行為特征分析的社交網(wǎng)絡(luò)女巫節(jié)點(diǎn)檢測(cè)機(jī)制[A].電子與信息學(xué)報(bào)，2017，39（9）.

[2] 周清清，陳志剛，黃 瑞，李 博，徐成林.在線社交網(wǎng)絡(luò)Sybil賬號(hào)檢測(cè)[A].小型微型計(jì)算機(jī)系統(tǒng)，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.

作者簡(jiǎn)介：

吳彥芳，生于1996年12月，女，漢族，河南民權(quán)人，南京郵電大學(xué)本科在讀，物聯(lián)網(wǎng)工程專業(yè).

*【基金項(xiàng)目】本文系南京郵電大學(xué)2018年度大學(xué)生實(shí)踐創(chuàng)新訓(xùn)練計(jì)劃項(xiàng)目，項(xiàng)目編號(hào)XYB2018284