作者：小伍哥

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

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

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

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

一、LockInfer算法概述

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

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

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

1、密集行為的案例

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

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

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

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

2、低密度密集連接

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

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

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

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

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

二、密集行為的類型

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

圖5.5

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

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

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

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

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

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

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

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

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

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

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

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

1、不含密集行為的隨機(jī)圖

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

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

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

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

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

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

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

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

1、密集塊定義

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

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

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

直覺(jué)上理解這個(gè)定義是說(shuō)，大又密集的塊表示了密集行為，所以看上去非?？梢?。密度閾值

可以被如下估計(jì)。

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

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

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

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

簡(jiǎn)短的答案是不同種類的密集行為。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖5.8

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

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

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

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

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

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

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

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

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

正常情況下特征子空間的散點(diǎn)圖會(huì)給出正常的 θ 和 r 頻度分布

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

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

圖5.9

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

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

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

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

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

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

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

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

圖5.10

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