作者 | ANTI
一、概述
跟着互联网技能的开展，人们享受互联网带来的盈利的一起，也面临着黑产对整个互联网健康开展带来的危害，例如薅羊毛、刷单、刷流量/粉丝、品控、欺诈、快排等等，反做弊作为冲击黑产的中坚力量，继续跟黑产对抗着，确保搜索/feed作用的客观公正，确保广告主的合法权益。近年来反做弊算法才能继续提升，黑产很难通过大规模机刷方法获利，已从大规模机刷转向愈加荫蔽的小团伙做弊，因而，反做弊进行了团伙做弊发掘的探究，Louvain便是比较经典的一个算法，下面具体介绍下。
二、Louvain简介
2.1 模块度界说
模块度是对社区区分好坏程度的一种衡量，当社区内部的点之间连边越多，社区之间的点连边越少时，模块度越大，表明当时的社区区分状况越好，公式界说如下：
模块度是对社区区分好坏程度的一种衡量，当社区内部的点之间连边越多，社区之间的点连边越少时，模块度越大，表明当时的社区区分状况越好，公式界说如下：
其间
公式并不好直接了解，进行一定的改换可得
其间 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：arxiv.org/abs/0803.04…
[2]stanford keynote：web.stanford.edu/class/cs224…
[3]louvain：towardsdatascience.com/louvain-alg…
引荐阅读【技能加油站】系列：
百度用户产品流批一体的实时数仓实践
ffplay视频播放原理剖析
百度工程师眼中的云原生可观测性追踪技能
运用百度开发者工具 4.0 搭建专属的小程序 IDE
百度工程师教你玩转规划形式（观察者形式）
揭秘百度智能测试在测试自动执行范畴实践
