Louvain算法在反作弊上的应用
一、概述
二、Louvain简介
将社团中每个节点都看做一个单独的社区。
遍历所有节点，计算当前节点脱离当前社区，且加入到邻居节点所在社区时，带来的模块度增益，把当前节点移动到增益最大的邻居节点社区中。
将同一个社区的多个节点，融合为一个新的节点，社区内节点之前的权重后续不再使用，当前社区与其他社区之间的权重为两个社区所有节点的权重和，从而构建出新的图结构。
回到阶段1不断迭代，直至图结构不再产生改变。
三、在反作弊应用
我们看一个电商风控的业务场景。少数店铺为了构造虚假的用户体验评分、更优的算法推荐，铤而走险组建团队做起了刷单套利、刷评分等非法操作。而商家获得的非法收益最终却由用户买单。为了还原真实的互联网、给用户带来最优质的体验 ，我们对作弊团伙进行了持续挖掘对抗。
我们基于经典的Louvain算法实现关系网络模型，将作弊数据中错综复杂的关系抽象成数学表达，我们得到层次化的社区发现结果，如下图所示。其中第一张图描述了风险账户的社区发现结果，第二张图描述了交易订单的社区发现结果，精准定位了作弊团伙，拦截作弊订单/交易，增强了风险防控能力，联合公司法务部对多个作弊黑产团伙也进行了数次抓捕。
四、优化
1. 平均时间复杂度较低，计算速度相对较快；
2. 支持定义边权 ；
3. 包含层次结构的社团，可以依据社团大小、社团特殊属性来限制最后形成的社团。类似决策树中根据增益、叶子节点数量来限制节点分裂 。
1. 多轮迭代，不支持流式系统 ；
2. 最差时间复杂度较大，小概率遇到边界数据时，耗时较长；
3. 实际情况中数据分布不均匀时，模块度定义的第二项会产生一定负干扰。
1. 利用边属性对社团中的边进行关于合并优先级的排序，能取消louvain的多轮迭代，适配流式计算系统。比如边介数：社团中任意两个点的最短路径通过该边的次数；
2. 实际数据中社团分布不均匀时，建议降低模块度中第二项的权重。
[2]stanford keynote：http://web.stanford.edu/class/cs224w/slides/14-communities.pdf
[3]louvain：https://towardsdatascience.com/louvain-algorithm-93fde589f58c