共计 2329 个字符，预计需要花费 6 分钟才能阅读完成。
作者 | ANTI
一、概述
随着互联网技术的倒退，人们享受互联网带来的红利的同时，也面临着黑产对整个互联网衰弱倒退带来的危害，例如薅羊毛、刷单、刷流量 / 粉丝、品控、欺骗、快排等等，反作弊作为打击黑产的中坚力量，继续跟黑产反抗着，保障搜寻 /feed 成果的主观公正，保障广告主的合法权益。近年来反作弊算法能力继续晋升，黑产很难通过大规模机刷形式获利，已从大规模机刷转向更加荫蔽的小团伙舞弊，因而，反作弊进行了团伙舞弊开掘的摸索，Louvain 就是比拟经典的一个算法，上面具体介绍下。
二、Louvain 简介
2.1 模块度定义
模块度是对社区划分好坏水平的一种度量，当社区外部的点之间连边越多，社区之间的点连边越少时，模块度越大，示意以后的社区划分状况越好，公式定义如下：
模块度是对社区划分好坏水平的一种度量，当社区外部的点之间连边越多，社区之间的点连边越少时，模块度越大，示意以后的社区划分状况越好，公式定义如下：
其中示意所有边权和，示意节点 i 和 j 之间的权重，示意与 i 相连的所有边的权重和，示意节点 i 所在的社区，示意 x 和 y 是否雷同，是的话为 1，否则为 0。
公式并不好间接了解，进行肯定的变换可得
其中 c 示意社团，示意社区 c 中所有节点的之间的边权和，示意社区 c 中所有节点与其余节点的边权和。
模块度前一项形容的是社团内节点之间的边权，该值越大，模块度越大。第二项形容每个社团中所有节点的边权和平方，分母为常量，当所有节点（严格来说是节点的度，即边权）在不同社区中散布越平均，第二项越小，模块度越大。（第二项重要水平与社团理论的散布状况无关，比方风控场景社团大小散布极不平均，就会导致第二项后果偏大，模块度偏小，导致模块度的优化指标与理论场景抵触。）
2.2 算法
louvain 以最大化模块度为优化指标，依据模块度公式，整个社区的模块度能够以各个社区为单位计算后求和失去，louvain 算法的流程如下：
初始化
将社团中每个节点都看做一个独自的社区。
阶段 1：节点合并
遍历所有节点，计算以后节点脱离以后社区，且退出到街坊节点所在社区时，带来的模块度增益，把以后节点挪动到增益最大的街坊节点社区中。
每次计算节点 i 从社团 D 挪动到社团 C 中时，依据模块度计算公式可知，此时产生的模块度变动只与以后 C、D 社区相干，不与其余社区相干，因而计算成本较低，将节点 i 从社区 D 转移到 C 中带来的模块度增益为：
ΔQ\=ΔQ(D→i)+ΔQ(i→C)
直至节点挪动不再产生增益，阶段 1 进行。
阶段 2：社区聚合
将同一个社区的多个节点，交融为一个新的节点，社区内节点之前的权重后续不再应用，以后社区与其余社区之间的权重为两个社区所有节点的权重和，从而构建出新的图构造。
回到阶段 1 一直迭代，直至图构造不再产生扭转。
louvain 基于贪婪算法实现，理论数据中的均匀复杂度为 O(nlog(n))，当每一轮迭代中节点数量升高一半时，能达到均匀复杂度。
整体流程如下：
三、在反作弊利用
因黑产舞弊的收益较大，作弊者就算冒着守法被抓的危险，也有短缺的工夫和能源与风控团队反抗，在理论业务场景中，过来作弊者最常应用的形式是低成本批量机器舞弊被咱们严格打击殆尽，目前也只能逐渐迁徙成了高老本小批量团伙人为舞弊，这是黑产攻击方式的演变趋势，也是风控团队技术倒退的必要趋势。
咱们看一个电商风控的业务场景。多数店铺为了结构虚伪的用户体验评分、更优的算法举荐，逼上梁山组建团队做起了刷单套利、刷评分等非法操作。而商家取得的非法收益最终却由用户买单。为了还原实在的互联网、给用户带来最优质的体验，咱们对舞弊团伙进行了继续开掘反抗。
咱们基于经典的 Louvain 算法实现关系网络模型，将舞弊数据中盘根错节的关系形象成数学表白，咱们失去层次化的社区发现后果，如下图所示。其中第一张图形容了危险账户的社区发现后果，第二张图形容了交易订单的社区发现后果，精准定位了舞弊团伙，拦挡舞弊订单 / 交易，加强了危险防控能力，联结公司法务部对多个舞弊黑产团伙也进行了数次抓捕。
社区发现示例图一
社区发现示例图二
四、优化
4.1 优缺点
长处
1. 均匀工夫复杂度较低，计算速度绝对较快；
2. 反对定义边权；
3. 蕴含层次结构的社团，能够根据社团大小、社团非凡属性来限度最初造成的社团。相似决策树中依据增益、叶子节点数量来限度节点决裂。
毛病
1. 多轮迭代，不反对流式零碎；
2. 最差工夫复杂度较大，小概率遇到边界数据时，耗时较长；
3. 理论状况中数据分布不平均时，模块度定义的第二项会产生肯定负烦扰。
4.2 优化思路
模块度的最优求解自身是个 NP 问题，即工夫复杂度为 O(M!)，惯例数据中无奈在短时间内求到最优解。louvain 就是利用贪婪算法对求解过程做了肯定优化，但在 louvain 的根底上，还能够做以下优化：
1. 利用边属性对社团中的边进行对于合并优先级的排序，能勾销 louvain 的多轮迭代，适配流式计算零碎。比方边介数：社团中任意两个点的最短门路通过该边的次数；
2. 理论数据中社团散布不平均时，倡议升高模块度中第二项的权重。
———- END ———-
参考：
[1]原始 paper：https://arxiv.org/abs/0803.0476
[2]stanford keynote：http://web.stanford.edu/class…
[3]louvain：https://towardsdatascience.co…
举荐浏览【技术加油站】系列：
百度用户产品流批一体的实时数仓实际
ffplay 视频播放原理剖析
百度工程师眼中的云原生可观测性追踪技术
应用百度开发者工具 4.0 搭建专属的小程序 IDE
百度工程师教你玩转设计模式（观察者模式）
揭秘百度智能测试在测试主动执行畛域实际
