作者：小伍哥

來源：小伍哥聊風(fēng)控

大家好，我是小伍哥，今天給大家分享的是一個基于密度的欺詐檢測算法，思想非常牛逼，大家可以試試，先給出論文地址和代碼

論文地址：http://pengcui.thumedialab.com/papers/lockinfer-kais15.pdf

代碼地址：https://github.com/mjiang89/LockInfer

一、LockInfer算法概述

互聯(lián)網(wǎng)上泛濫著形形色色的欺詐行為，特別是社交網(wǎng)絡(luò)誕生以來，許多職業(yè)黑客和黑色產(chǎn)業(yè)鏈便通過欺詐行為謀生，淘寶的刷單、微博刷粉、抖音刷贊等都成了眾所周知的事情。這種擁有批量賬戶為用戶提供作弊的行為，叫做lockstep行為，如何檢測這些作弊用戶，成為一個非常大的課題。

給定社交網(wǎng)絡(luò)、專利引用網(wǎng)絡(luò)和電話網(wǎng)絡(luò)等多種大規(guī)模應(yīng)用的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，如何能抓住可疑的用戶行為?

如何能找到驚人的、難以預(yù)知的連接模式?有很多工作已經(jīng)研究了通信商的欺詐行為、Ebay 中的虛假評價和 Facebook 上虛假的頁面 “喜歡”，而這里所研究的是常見的異常行為模式，并嘗試開發(fā)一種通用的有效方法從不同的應(yīng)用中檢測出這類行為，一種基于密集行為的檢測方法。

1、密集行為的案例

在這里我們先展示出密集行為的三個案例 ：

a) 在Facebook或是Twitter 的類似的可以被表示為無向圖/有向圖的社交網(wǎng)絡(luò)中，許多售粉公司都設(shè)置了百萬級的僵尸粉一起行動，共同關(guān)注同一群人(顧客)來提升他們的市場價值。所以，雖然這些 被關(guān)注的人并不知名，但是他們會最終有很多粉絲。這些粉絲是花錢雇傭來的，或者是用腳本創(chuàng)造出來的。這種密集行為會在圖對應(yīng)的鄰接矩陣中形成大的、密集的塊。

b) 在論文引用的網(wǎng)絡(luò)中，在同一個研究問題或者是同一個項目里的研究 者們往往會互相引用對方的文章，即使這些文章與他們的工作毫不相關(guān)。

c) 在諸 如IMDb，MovieLens和Netflix 等電影參演的網(wǎng)絡(luò)中，男演員/女演員/導(dǎo)演經(jīng)常與關(guān)系已經(jīng)很好的朋友一起合作參演電影，這樣會更容易在工作中交流，更容易理解電影中演員的形象。這些網(wǎng)絡(luò)是可以用二部圖來描述的。要注意的是密集行為是說一組演員/導(dǎo)演與一組電影之間的交互，并最終在理解矩陣?yán)锩嫘纬蓚€密集子矩陣(塊狀)。

2、低密度密集連接

在基于圖的應(yīng)用中，密集行為模式是非常常見的，所以一個很重要又很有趣的問題是：如何來找到幾乎滿員的密集塊狀子矩陣，也就是如何找到密集行為的鏈接?

這個問題做起來并不那么容易，就社交網(wǎng)絡(luò)為例，其中有很多幫助顧客提粉絲數(shù)的僵尸粉公司存在，這類行為扭曲社交媒體的網(wǎng)絡(luò)結(jié)果，導(dǎo)致正常用戶體驗受到嚴(yán)重傷害，僵尸粉公司會開發(fā)出各種辦法來繞開檢測，一種方法是形成密度較低的塊。

比如上圖(a) 中就提出了一個更難的問題:如何檢測到密集卻不是100% 密集的塊狀結(jié)構(gòu)?

什么情況下一個塊過于大過于密集，以至于在圖中很難出現(xiàn)?

圖(b) 中給出了多組僵尸粉與顧客相連接的案例，僵尸粉群往往很分享顧客，而他們形成的密集行為會產(chǎn)生部分重合，如何檢測部分重合的密集行為?

二、密集行為的類型

近年來的一些研究把社交圖數(shù)據(jù)轉(zhuǎn)為連接模式來研究社區(qū)結(jié)構(gòu)以及聚類屬性。然而，并沒有任何分析能夠指出如何檢測出特殊行為的方式方法。本文在騰訊微博的完整有向圖數(shù)據(jù)上做研究。這份數(shù)據(jù)是 2011年1月爬取得 到，含有1.17億的用戶和33.3億的社交關(guān)系。在微博圖中研究用戶的關(guān)注行為時討論了不同種類的密集行為。

圖5.5

比如圖5.5(a-b) 中的無密集行為，圖5.5(c-d) 中的不重合密集行為，圖5.5(e-f) 中的部分重合密集行為。在鄰接矩陣中尋找連接模式并 檢查特征子空間中對應(yīng)的形態(tài)。

圖5.5(a)、5.5(c) 和 5.5(e) 中展現(xiàn)了鏈接關(guān)系，也就是用黑點描述鄰接矩陣中的非零值，所在 X 軸是粉絲編號，所在Y軸是被關(guān)注人的編號。密集行為形成的 密集黑塊用虛線高亮出來。

圖5.5(b)，5.5(d)，5.5(f) 中畫出了粉絲節(jié)點的一對矩陣 的左奇異向量值。這些圖能夠可視化特征子空間，虛線分別是 X 軸和Y軸。借助 表5.5中的名詞表征復(fù)雜模式可以討論如下:

不含密集行為：根據(jù)Chung-Lu模型[260] 仿真了不含密集行為的隨機冪律圖。圖5.5(a) 中的鄰接矩陣并不含有大的、密集的塊。本工作研究了每一對二維 的特征子空間，看到在圖5.5(b) 中原點周圍的粉絲。

不重合的密集行為：在騰訊微博中存在一組僵尸粉 F0 關(guān)注同一組人。那么圖5.5(c) 所示，鄰接矩陣中就會有一個大的密集的塊(83,208 個粉絲，密度 為 81.3%)。圖5.5(d) 畫出了第 1 個和第 3 個左奇異向量形成的特征子空間。粉絲組 F0 在 Y 軸一側(cè)形成鐳射形狀的點簇。

部分重合的密集行為:在鄰接矩陣中會看到更驚奇的連接模式，也就是如 圖5.5(e) 中的階梯狀(10,052 個粉絲，密度為 43.1%)。僵尸粉組 F1-F3 的密 集行為分別形成三個密度超過 89% 的密集塊。然而不同于不重合密集行為， F1 和 F2 有同樣的關(guān)注人群 E1，而 F1 和 F3 有同樣的關(guān)注人群 E2。重合的密集行為的鄰接矩陣的第2個和第 8 個左奇異向量形成了特征子空間，如 圖5.5(f) 所示，含有多個微小的簇以同樣的半徑圍繞著原點。如同不完整的 球狀，又像珍珠項鏈，稱之為 “珍珠狀” 模式。

三、不同密集行為特征子空間可視化

根據(jù)不同類型的仿真密集行為在奇異向量中留下的痕跡，總結(jié) 出一系列的診斷方法。這些方法能夠讓數(shù)據(jù)科學(xué)家和實踐者能夠從奇特的連 接行為中發(fā)現(xiàn)可疑的用戶行為。

首先要了解一個概念，特征空間，也就是鄰接矩陣經(jīng)過SVD分解后任取兩個左奇異向量構(gòu)成的二維分布空間。

通過領(lǐng)接矩陣特征空間的可視化可以量化lockstep行為：密集行為會在鄰接矩陣中形成特定的連接模式和奇特的特征子空間的形狀

• 在模擬的隨機仿真圖中，在特征子空間中粉絲都在原點周圍分散。
• 在微博數(shù)據(jù)中，粉絲組 F0 的不重合密 集行為會在鄰接矩陣中形成密集塊，在特征子空間中形成鐳射線。
• 粉絲組 F1-F3 的重合 密集行為會形成階梯狀結(jié)構(gòu)和珍珠狀的子空間分布。

接下來我們將仔細(xì)的對比一下不同密集圖的鄰接矩陣和特征空間的可視化結(jié)果，如下所示。

1、不含密集行為的隨機圖

在節(jié)點之間隨機產(chǎn)生邊的仿真圖中，在特征子空間中粉絲都在原點周圍分散。（左圖是鄰接矩陣可視化，右圖是譜子空間可視化，下同）

2、存在不重合密集行為的圖

在微博數(shù)據(jù)中，粉絲組 F0 的不重合密 集行為會在鄰接矩陣中形成密集塊，在特征子空間中形成鐳射線。

3、存在部分重合密集行為的圖

粉絲組 F1-F3 的重合 密集行為會形成階梯狀結(jié)構(gòu)和珍珠狀的子空間分布。

下面是針對不同lockstep分類的可視化分析結(jié)論：

四、密集行為的特征子空間的進(jìn)一步分析

在這一小節(jié)，首先介紹 “密集塊” 的定義和理論上的密度閾值，然后介紹如何 繪制特征子空間。通過討論不同類密集行為，給出行為形成的密集塊性質(zhì)，并給出一系列從特征子空間的模式和連接模式來判斷密集行為類型的規(guī)則。

1、密集塊定義

用 (S , T ) 表示源節(jié)點集合 S 與目標(biāo)節(jié)點 T 形成的子圖。通過節(jié)點重排序之后， 鄰接矩陣中就會出現(xiàn) “塊” 的形狀。用 d(S , T ) 表示塊密度即非零值比例。那么密 集塊可疑定義為實際密度比均一假設(shè)下要高的塊。正式的定義如下:

密集塊：在鄰接矩陣 A(大小為 M×N，密度為 D)，一個大小為 m×n 的塊 (S , T ) 可以被叫做 “密集塊”，當(dāng)且僅當(dāng)密度 d(S , T ) 比均一密度

要高，即d (S,T)>=

直覺上理解這個定義是說，大又密集的塊表示了密集行為，所以看上去非常可疑。密度閾值

可以被如下估計。

如果粉絲集合F存在著密集關(guān)注偶像集合E的利益驅(qū)動的動機，那么他們也可以進(jìn)行 “偽裝”，也就是關(guān)注額外的一些不在集合E中的用戶;

• k維度的奇異值分解(SVD)是把形式為 A = UΣVT 的矩陣因子化，其中 Σ 是由前 k 大的奇異值組成的、大小為 k × k 的對角矩陣，U 和 V 是大小為 N × k 的 正交矩陣，其中分別包含左奇異向量和右奇異向量。un,i 是矩陣 U 的第 (n,i) 個元 素，相似的，vn,i 是矩陣 V 的元素。un,i 是第 n 個粉絲在第 i 個左奇異向量中的值。定義 (i, j)-左特征子空間圖為點集 (un,i, un, j) 形成的散點圖，這就是 N 個粉絲的第 i 和第 j 個左奇異向量的映射?？梢酝瑯佣x N 個用戶作為被關(guān)注人的情況，所以 (i, j)-右特征子空間圖就是點集 (vn,i, vn, j) 的散點圖。這個圖能夠可視化所有點，如果恰當(dāng)使用，是可以解釋很多鄰接矩陣的內(nèi)在性質(zhì)的。

如同在圖5.5(a-b) 中介紹的，給定一個隨機冪律分布圖，特征空間會是在原點周圍的一些云一樣的點集合。然而，在騰訊微博數(shù)據(jù)中看到了如鐳射線狀和珍珠 狀的特別形狀。

是什么樣的用戶行為導(dǎo)致了這些特別形狀在特征子空間中出現(xiàn)?

簡短的答案是不同種類的密集行為。

接下來會詳細(xì)介 紹密集行為類型和這些特征形狀之間的關(guān)系。在枚舉所有密集行為的類型，首先要給出 “偽裝” 和 “偽知名” 的概念。

如果粉絲集合F存在著密集關(guān)注偶像集合E的利益驅(qū)動的動機，那么他們也可以進(jìn)行 “偽裝”，也就是關(guān)注額外的一些不在集合E中的用戶;

那些E中的用戶也可能會 “偽知名”，也就是被一些額外的不在集合F中的粉絲關(guān)注。

2、構(gòu)造仿真數(shù)據(jù)

根據(jù)這些概念可以構(gòu)造仿真數(shù)據(jù)研究密集行為，首先產(chǎn)生一個大小為1M×1M 的隨機冪律分布圖，然后注入兩組不同的存在密集行為的粉絲集合。細(xì)節(jié)上說， 注入集合 F1(50個新的粉絲)一起關(guān)注集合 E1(50個新的被關(guān)注的人)。相似地，注入另一組集合F2一起關(guān)注集合E2。下圖中左側(cè)用黑點畫出鄰接矩陣中的非零元素，能看到兩個大小為 50 × 50 的非重合密集塊，不重合的密集行為的屬性設(shè)置如下:

規(guī)則 1-3 (“鐳射線”):鄰接矩陣中不重合的密集塊。

規(guī)則 1 (短 “鐳射線”): 兩個密集塊，90% 的高密度，不含 “偽裝”，不含 “偽知名”

規(guī)則 2 (長 “鐳射線”): 兩個密集塊，50% 的低密度，不含 “偽裝”，不含 “偽知名”

規(guī)則 3 (旋轉(zhuǎn)的 “鐳射線”): 兩個密集塊，含有 “偽裝”, 不含 “偽知名”

規(guī)則 3 (旋轉(zhuǎn)的 “鐳射線”): 兩個密集塊，含有 “偽知名”, 不含 “偽裝”

密 度：高密度是指新注入的粉絲關(guān)注90%的對應(yīng)的注入的偶像；低密度是指比例為50%。

偽 裝：偽裝是讓注入的粉絲關(guān)注0.1% 額外的偶像；如果沒有偽裝，那么它只關(guān)注對應(yīng)的偶像。

偽知名：偽知名是讓注入的偶像還會被0.1%額外的粉絲關(guān)注；如果沒有偽知名，那么它只被新注入的粉絲關(guān)注。

在上圖的中間和右側(cè)分別給出了左奇異向量和右奇異向量構(gòu)成的特征子空間。于是能看到不同類型的非重合密集行為存在下述的可疑蹤跡：

規(guī)則 1 (短 “鐳射線”)：如果注入粉絲的密集行為非常緊密，鄰接矩陣中會有一個或者多個密度高達(dá)90%的不重合塊。特征子空間圖會展現(xiàn)出短 “鐳射 線”:向原點延伸過去的貼近軸的線狀密集點集。

規(guī)則 2 (長 “鐳射線”)：如果注入的粉絲行為密集，但較為松散，鄰接矩陣中有若干個密度為 50%的不重合塊。特征子空間圖展現(xiàn)出長 “鐳射線”:鐳射線會貼近軸，并且向原點伸長。

規(guī)則 3 (旋轉(zhuǎn)的 “鐳射線”)：如果注入的粉絲有 “偽裝” 或者是注入的偶像有 “偽知名” 的問題，鄰接矩陣會在密集塊以外形成稀疏的額外鏈接。和規(guī)則 1、 2 不同的是，向原點延伸的鐳射線會以某個角度旋轉(zhuǎn)，叫做旋轉(zhuǎn)的 “鐳射線”。

另一方面，如果注入的粉絲密集地關(guān)注對應(yīng)的偶像集合，這些偶像集合存在 部分的重合，稱之為部分重合的密集行為。仿真數(shù)據(jù)是在隨機圖中注入3個粉絲集合Fi (i = 1,...,3)和5個偶像集合Ei (i = 1,...,5)。每一個粉絲集合都含有1000個粉絲，每一個偶像集合都含有10個偶像。F1 的粉絲集合關(guān)注集合 E1 到 E3 的偶像；F2 的粉絲集合關(guān)注集合 E2 到 E4 的偶像;F3 的粉絲集合關(guān)注集合 E3 到 E5 的偶像。圖5.8中可以看到鄰接矩陣和特征子空間之間的關(guān)系。

規(guī)則 4 (“珍珠狀”)：重合的密集行為在鄰接矩陣中形成 “階梯狀” 塊，因為粉 絲集合會連接若干個偶像集合，多個密集塊之間是存在重合的。特征子空間 中顯示出離原點距離相近的球狀，或者叫 “珍珠狀” 的點簇。

圖5.8(b) 給出 3 組 F1 到 F3 的粉絲集合在特征子空間中形成的3個點簇構(gòu)成的珍珠狀。圖5.8(c) 給出 5 組 E1 到 E5 的偶像集合在特征子空間中形成的5個點簇構(gòu)成的珍珠狀。具有相近的或者是重合的偶像的注入粉絲會在特征子空間中靠近。

規(guī)則 4 (“珍珠狀”): 三個部分重合的密集塊形成的 “階梯狀” 塊。

圖5.8

五、基于特征子空間的密集行為檢測算法實現(xiàn)

本工作中所給出密集行為的檢測算法 LockInfer 有下面兩個步驟:

種子選取: 根據(jù)上一個小節(jié)給出的規(guī)則1到4，選擇具有密集行為的粉絲節(jié)點，并叫做 “有密集行為” 的粉絲。

密集值傳遞: 在粉絲集合和偶像集合之間傳遞 “有密集行為” 的值，簡稱密集值。每次用高于密度閾值定理給出的密度閾值 d選取有密集行為的粉絲用戶，去掉并不足夠密集的用戶，接下來是對偶像集合做同樣的處理。

算法 7中還給出了每一步驟的細(xì)節(jié)

LockInfer可以從任意種子節(jié)點集合出發(fā)，甚至隨機選取的節(jié)點。然而認(rèn)真選取種子節(jié)點能加快檢測速度。如下線索指出如何找到合適的種子:選擇出度在尖峰處的粉絲，但出度在尖峰處的節(jié)點大多數(shù)實際上正常。用之前所給出的規(guī)則集合來選取粉絲，后續(xù)會證實這是非常有效的。

當(dāng)然，如果采用額外信息，比如 IP地址、個人信息等內(nèi)容，可以用這些額外 信息來選擇可疑節(jié)點，例如，大量的可疑粉絲會設(shè)置自己的生日為同一年的第一 天，都是男性，都來自同樣的城市。然而，如果沒有額外信息，LockInfer 還是能 夠從規(guī)則中有效選取種子。

圖5.9給出找到種子的步驟方法。種子選取的算法有三 個步驟，如下:

首先，生成一系列的特征子空間圖，計算最大的 k 個左奇異向量 u1, . . . , uk，并 畫出所有粉絲節(jié)點在每一對奇異向量張成的子空間中的分布，如圖5.9(a) 所示。在高維度的情況下，例如 U19 vs U20，常見的特征子空間圖中原點附近有一大簇云 狀點集。然而，從 U1 vs U3 中可以看到構(gòu)成直角的鐳射線，從 U1 vs U2 中可以看 到旋轉(zhuǎn)的鐳射線，從 U2 vs U8 中可以看到珍珠狀分布，這些都是非常奇怪的。

正常情況下特征子空間的散點圖會給出正常的 θ 和 r 頻度分布

“鐳射線” 會在 θ 的頻度圖上形成兩個尖峰，出現(xiàn)在 0o 和 90o

“鐳射線” 會在 θ 的頻度圖上形成兩個尖峰，出現(xiàn)在 0o 和 90o

“珍珠狀” 在 r 的頻度圖上形成一個離原點很遠(yuǎn)的尖峰

圖5.9

第二，用極坐標(biāo)變換把所有的點畫成 (r,θ)，其中 r 是點離原點的距離，θ 是旋 轉(zhuǎn)的角度。如圖5.9(b) 所示，鐳射線會形成在 θ = 0o 和 θ = 90o 處的兩個團(tuán)簇，珍 珠狀會形成在較大的 r 處的一些微小的點簇。

第三，可以把距離 (r) 和角度 (θ) 的軸分割為若干個部分，并且把 r 和 θ 的頻度畫在柱狀圖中。鐳射線構(gòu)成的角度分布圖會在 0°和 90° 形成尖峰，但是在其他部位并沒有尖峰;珍珠狀構(gòu)成的距離分布圖會形成單個尖峰，而其他圖中頻度會 隨著距離增大而慢慢減小。用中位數(shù)過濾法[278] 可以檢測尖峰，并且把尖峰處的 節(jié)點放入種子集合中。

要注意的是，如果不存在密集行為，鄰接矩陣中沒有密集塊，特征子空間圖會在原點周圍形成云狀節(jié)點。角度 θ 的頻度會幾乎是一個常數(shù)，而 r 的節(jié)點頻度 會隨著 r 的增大而減小。

設(shè)定參數(shù)時，密集塊的最小規(guī)模是 mmin×nmin (mmin = 100, nmin = 10)，最小的密度是 d。同時可以設(shè)置 k = 20 來權(quán)衡特征子空間圖的數(shù)量和 SVD 的運算時間。通 過閱讀極坐標(biāo)圖，畫出距離和角度的頻度分布圖，切割距離的軸為Kr =20個柱 子，切割角度的軸為Kθ =2 Kr =40個柱子，因為θ可能為正也可能為負(fù)。

下面是進(jìn)行 “密集值” 的傳遞來找到所有有密集行為的粉絲和偶像節(jié)點。定 義粉絲節(jié)點的密集值為其對應(yīng)的有密集行為的偶像節(jié)點的百分比，定義偶像節(jié)點 的密集值為對應(yīng)的有密集行為的粉絲節(jié)點百分比，由此每一次用一個密度閾值來 選擇新的具有密集行為的粉絲節(jié)點和偶像節(jié)點集合。Scoop 函數(shù)如信任傳遞算法， 迭代地從粉絲到偶像，從偶像到粉絲傳遞密集值。下面來解釋其中每一個步驟。

從源節(jié)點(粉絲)到目標(biāo)節(jié)點(偶像): 圖5.10(a) 的有向圖中上面是粉絲集 合，下面是偶像集合。如果從 5 個密集的粉絲出發(fā)，對每一個偶像，計算他 們粉絲在種子集合中的比例。選取有比例高的偶像作為有密集行為的偶像。函數(shù) S2T 給出如何從源節(jié)點傳遞密集值到目標(biāo)節(jié)點。

從目標(biāo)節(jié)點(偶像)到源節(jié)點(粉絲):接著是對每一個粉絲，計算他有多 少比例的偶像是有密集行為的。圖5.10(b) 給出了如何選取新的密集行為粉 絲，并去除無辜的不關(guān)注或者只關(guān)注 1 個的偶像。函數(shù) T 2S 給出了如何從 目標(biāo)節(jié)點傳遞密集值到源節(jié)點。

重復(fù)到收斂:當(dāng)收斂的時候如果密集塊并不為空，報告有密集行為的粉絲和偶像集合。

圖5.10

LockInfer 的時間復(fù)雜度為 O(E)，算法是隨著邊數(shù)呈線性關(guān)系。在仿真的呈 對角塊狀的鄰接矩陣中運用該算法，每一個塊都有 10,000 個節(jié)點和 40,000 個隨機 邊，重復(fù)塊結(jié)構(gòu)得到含有 1,300,000 個節(jié)點和 5,100,000 個邊的仿真圖。圖5.11展示 了隨著仿真圖數(shù)據(jù)的大小(邊數(shù))變化的運行時間。注意到的是時間曲線與社交 圖的規(guī)模呈線性關(guān)系，LockInfer 算法是可擴展的，可被用于真實應(yīng)用中。

六、與其他算法的對比

下表給出本工作的 LockInfer 算法與采用特征向量和特征子空間的傳統(tǒng)圖挖掘方法相比，既有效、又有可解釋性，還兼具可擴展性。

LockInfer 算法與采用特征向量和特征子空間的傳統(tǒng)圖挖掘方法相比，既有效、又有可解釋性，還兼具可擴展性。