作者：小伍哥

來源：小伍哥聊風控

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

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

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

一、LockInfer算法概述

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

給定社交網絡、專利引用網絡和電話網絡等多種大規模應用的網絡拓撲結構，如何能抓住可疑的用戶行為?

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

1、密集行為的案例

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

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

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

c) 在諸如IMDb，MovieLens和Netflix 等電影參演的網絡中，男演員/女演員/導演經常與關系已經很好的朋友一起合作參演電影，這樣會更容易在工作中交流，更容易理解電影中演員的形象。這些網絡是可以用二部圖來描述的。要注意的是密集行為是說一組演員/導演與一組電影之間的交互，并最終在理解矩陣里面形成個密集子矩陣(塊狀)。

2、低密度密集連接

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

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

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

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

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

二、密集行為的類型

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

圖5.5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

四、密集行為的特征子空間的進一步分析

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

1、密集塊定義

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

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

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

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

可以被如下估計。

如果粉絲集合F存在著密集關注偶像集合E的利益驅動的動機，那么他們也可以進行 “偽裝”，也就是關注額外的一些不在集合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 個左奇異向量的映射。可以同樣定義 N 個用戶作為被關注人的情況，所以 (i, j)-右特征子空間圖就是點集 (vn,i, vn, j) 的散點圖。這個圖能夠可視化所有點，如果恰當使用，是可以解釋很多鄰接矩陣的內在性質的。

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

是什么樣的用戶行為導致了這些特別形狀在特征子空間中出現?

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

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

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

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

2、構造仿真數據

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

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

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

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

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

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

密度：高密度是指新注入的粉絲關注90%的對應的注入的偶像；低密度是指比例為50%。

偽裝：偽裝是讓注入的粉絲關注0.1% 額外的偶像；如果沒有偽裝，那么它只關注對應的偶像。

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

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

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

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

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

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

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

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

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

圖5.8

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

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

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

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

算法 7中還給出了每一步驟的細節

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

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

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

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

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

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

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

圖5.9

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

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

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

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

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

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

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

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

圖5.10

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