作者 | ANTI

一、概述

隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，人們享受互聯(lián)網(wǎng)帶來(lái)的紅利的同時(shí)，也面臨著黑產(chǎn)對(duì)整個(gè)互聯(lián)網(wǎng)健康發(fā)展帶來(lái)的危害，例如薅羊毛、刷單、刷流量/粉絲、品控、詐騙、快排等等，反作弊作為打擊黑產(chǎn)的中堅(jiān)力量，持續(xù)跟黑產(chǎn)對(duì)抗著，保證搜索/feed效果的客觀公正，保證廣告主的合法權(quán)益。近年來(lái)反作弊算法能力持續(xù)提升，黑產(chǎn)很難通過(guò)大規(guī)模機(jī)刷方式獲利，已從大規(guī)模機(jī)刷轉(zhuǎn)向更加隱蔽的小團(tuán)伙作弊，因此，反作弊進(jìn)行了團(tuán)伙作弊挖掘的探索，Louvain就是比較經(jīng)典的一個(gè)算法，下面詳細(xì)介紹下。

二、Louvain簡(jiǎn)介

2.1 模塊度定義

模塊度是對(duì)社區(qū)劃分好壞程度的一種度量，當(dāng)社區(qū)內(nèi)部的點(diǎn)之間連邊越多，社區(qū)之間的點(diǎn)連邊越少時(shí)，模塊度越大，表示當(dāng)前的社區(qū)劃分情況越好，公式定義如下：

模塊度是對(duì)社區(qū)劃分好壞程度的一種度量，當(dāng)社區(qū)內(nèi)部的點(diǎn)之間連邊越多，社區(qū)之間的點(diǎn)連邊越少時(shí)，模塊度越大，表示當(dāng)前的社區(qū)劃分情況越好，公式定義如下：

其中表示所有邊權(quán)和，表示節(jié)點(diǎn) i 和 j 之間的權(quán)重，表示與 i 相連的所有邊的權(quán)重和，表示節(jié)點(diǎn) i所在的社區(qū)，表示 x 和 y 是否相同，是的話為 1，否則為 0。

公式并不好直接理解，進(jìn)行一定的變換可得

其中 c 表示社團(tuán)，表示社區(qū) c 中所有節(jié)點(diǎn)的之間的邊權(quán)和，表示社區(qū) c 中所有節(jié)點(diǎn)與其他節(jié)點(diǎn)的邊權(quán)和。

模塊度前一項(xiàng)描述的是社團(tuán)內(nèi)節(jié)點(diǎn)之間的邊權(quán)，該值越大，模塊度越大。第二項(xiàng)描述每個(gè)社團(tuán)中所有節(jié)點(diǎn)的邊權(quán)和平方，分母為常量，當(dāng)所有節(jié)點(diǎn)（嚴(yán)格來(lái)說(shuō)是節(jié)點(diǎn)的度，即邊權(quán)）在不同社區(qū)中分布越均勻，第二項(xiàng)越小，模塊度越大。（第二項(xiàng)重要程度與社團(tuán)實(shí)際的分布情況有關(guān)，比如風(fēng)控場(chǎng)景社團(tuán)大小分布極不均勻，就會(huì)導(dǎo)致第二項(xiàng)結(jié)果偏大，模塊度偏小，導(dǎo)致模塊度的優(yōu)化目標(biāo)與實(shí)際場(chǎng)景沖突。）

2.2 算法

louvain 以最大化模塊度為優(yōu)化目標(biāo)，根據(jù)模塊度公式，整個(gè)社區(qū)的模塊度可以以各個(gè)社區(qū)為單位計(jì)算后求和得到，louvain算法的流程如下：

初始化
將社團(tuán)中每個(gè)節(jié)點(diǎn)都看做一個(gè)單獨(dú)的社區(qū)。

階段1：節(jié)點(diǎn)合并
遍歷所有節(jié)點(diǎn)，計(jì)算當(dāng)前節(jié)點(diǎn)脫離當(dāng)前社區(qū)，且加入到鄰居節(jié)點(diǎn)所在社區(qū)時(shí)，帶來(lái)的模塊度增益，把當(dāng)前節(jié)點(diǎn)移動(dòng)到增益最大的鄰居節(jié)點(diǎn)社區(qū)中。

每次計(jì)算節(jié)點(diǎn) i 從社團(tuán) D 移動(dòng)到社團(tuán) C 中時(shí)，根據(jù)模塊度計(jì)算公式可知，此時(shí)產(chǎn)生的模塊度變化只與當(dāng)前C、D社區(qū)相關(guān)，不與其他社區(qū)相關(guān)，因此計(jì)算成本較低，將節(jié)點(diǎn) i 從社區(qū) D 轉(zhuǎn)移到 C 中帶來(lái)的模塊度增益為：

ΔQ=ΔQ(D→i)+ΔQ(i→C)

直至節(jié)點(diǎn)移動(dòng)不再產(chǎn)生增益，階段1停止。

階段2：社區(qū)聚合
將同一個(gè)社區(qū)的多個(gè)節(jié)點(diǎn)，融合為一個(gè)新的節(jié)點(diǎn)，社區(qū)內(nèi)節(jié)點(diǎn)之前的權(quán)重后續(xù)不再使用，當(dāng)前社區(qū)與其他社區(qū)之間的權(quán)重為兩個(gè)社區(qū)所有節(jié)點(diǎn)的權(quán)重和，從而構(gòu)建出新的圖結(jié)構(gòu)。
回到階段1不斷迭代，直至圖結(jié)構(gòu)不再產(chǎn)生改變。

louvain基于貪心算法實(shí)現(xiàn)，實(shí)際數(shù)據(jù)中的平均復(fù)雜度為 O(nlog(n))，當(dāng)每一輪迭代中節(jié)點(diǎn)數(shù)量降低一半時(shí)，能達(dá)到平均復(fù)雜度。

整體流程如下：

三、在反作弊應(yīng)用

因黑產(chǎn)作弊的收益較大，作弊者就算冒著違法被抓的風(fēng)險(xiǎn)，也有充足的時(shí)間和動(dòng)力與風(fēng)控團(tuán)隊(duì)對(duì)抗，在實(shí)際業(yè)務(wù)場(chǎng)景中，過(guò)去作弊者最常使用的方式是低成本批量機(jī)器作弊被我們嚴(yán)格打擊殆盡，目前也只能逐步遷移成了高成本小批量團(tuán)伙人為作弊，這是黑產(chǎn)攻擊方式的演化趨勢(shì)，也是風(fēng)控團(tuán)隊(duì)技術(shù)發(fā)展的必要趨勢(shì)。
我們看一個(gè)電商風(fēng)控的業(yè)務(wù)場(chǎng)景。少數(shù)店鋪為了構(gòu)造虛假的用戶體驗(yàn)評(píng)分、更優(yōu)的算法推薦，鋌而走險(xiǎn)組建團(tuán)隊(duì)做起了刷單套利、刷評(píng)分等非法操作。而商家獲得的非法收益最終卻由用戶買單。為了還原真實(shí)的互聯(lián)網(wǎng)、給用戶帶來(lái)最優(yōu)質(zhì)的體驗(yàn) ，我們對(duì)作弊團(tuán)伙進(jìn)行了持續(xù)挖掘?qū)埂?br /> 我們基于經(jīng)典的Louvain算法實(shí)現(xiàn)關(guān)系網(wǎng)絡(luò)模型，將作弊數(shù)據(jù)中錯(cuò)綜復(fù)雜的關(guān)系抽象成數(shù)學(xué)表達(dá)，我們得到層次化的社區(qū)發(fā)現(xiàn)結(jié)果，如下圖所示。其中第一張圖描述了風(fēng)險(xiǎn)賬戶的社區(qū)發(fā)現(xiàn)結(jié)果，第二張圖描述了交易訂單的社區(qū)發(fā)現(xiàn)結(jié)果，精準(zhǔn)定位了作弊團(tuán)伙，攔截作弊訂單/交易，增強(qiáng)了風(fēng)險(xiǎn)防控能力，聯(lián)合公司法務(wù)部對(duì)多個(gè)作弊黑產(chǎn)團(tuán)伙也進(jìn)行了數(shù)次抓捕。

社區(qū)發(fā)現(xiàn)示例圖一

社區(qū)發(fā)現(xiàn)示例圖二

四、優(yōu)化

4.1優(yōu)缺點(diǎn)

優(yōu)點(diǎn)

1. 平均時(shí)間復(fù)雜度較低，計(jì)算速度相對(duì)較快；
2. 支持定義邊權(quán) ；
3. 包含層次結(jié)構(gòu)的社團(tuán)，可以依據(jù)社團(tuán)大小、社團(tuán)特殊屬性來(lái)限制最后形成的社團(tuán)。類似決策樹中根據(jù)增益、葉子節(jié)點(diǎn)數(shù)量來(lái)限制節(jié)點(diǎn)分裂 。

缺點(diǎn)

1. 多輪迭代，不支持流式系統(tǒng) ；
2. 最差時(shí)間復(fù)雜度較大，小概率遇到邊界數(shù)據(jù)時(shí)，耗時(shí)較長(zhǎng)；
3. 實(shí)際情況中數(shù)據(jù)分布不均勻時(shí)，模塊度定義的第二項(xiàng)會(huì)產(chǎn)生一定負(fù)干擾。

4.2優(yōu)化思路

模塊度的最優(yōu)求解本身是個(gè) NP 問(wèn)題，即時(shí)間復(fù)雜度為 O(M!)，常規(guī)數(shù)據(jù)中無(wú)法在短時(shí)間內(nèi)求到最優(yōu)解。louvain就是利用貪心算法對(duì)求解過(guò)程做了一定優(yōu)化，但在 louvain 的基礎(chǔ)上，還可以做以下優(yōu)化：

1. 利用邊屬性對(duì)社團(tuán)中的邊進(jìn)行關(guān)于合并優(yōu)先級(jí)的排序，能取消louvain的多輪迭代，適配流式計(jì)算系統(tǒng)。比如邊介數(shù)：社團(tuán)中任意兩個(gè)點(diǎn)的最短路徑通過(guò)該邊的次數(shù)；
2. 實(shí)際數(shù)據(jù)中社團(tuán)分布不均勻時(shí)，建議降低模塊度中第二項(xiàng)的權(quán)重。

---------- END ----------

參考：

[1]原始paper：https://arxiv.org/abs/0803.0476 [2]stanford keynote：http://web.stanford.edu/class/cs224w/slides/14-communities.pdf [3]louvain：https://towardsdatascience.com/louvain-algorithm-93fde589f58c

推薦閱讀【技術(shù)加油站】系列：

百度用戶產(chǎn)品流批一體的實(shí)時(shí)數(shù)倉(cāng)實(shí)踐

ffplay視頻播放原理分析

百度工程師眼中的云原生可觀測(cè)性追蹤技術(shù)

使用百度開發(fā)者工具 4.0 搭建專屬的小程序 IDE

百度工程師教你玩轉(zhuǎn)設(shè)計(jì)模式（觀察者模式）

揭秘百度智能測(cè)試在測(cè)試自動(dòng)執(zhí)行領(lǐng)域?qū)嵺`

總結(jié)

以上是生活随笔為你收集整理的Louvain算法在反作弊上的应用的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。