【.com快译】自从有互联网以来，互联网上流传着各种各样的垃圾信息和恶意信息。处理各种垃圾、欺骗甚至欺诈信息，已经成为每个互联网公司必须解决的问题。尤其是随着各种社交网站的兴起，反作弊和网络安全已经成为研究界和产业界共同面临的挑战。各大互联网公司都成立了专门的反作弊团队来应对日常的反作弊情况。反作弊中最常用的技术之一是图论算法，而反作弊问题往往可以归结为图论问题。例如，SVD可以用来分解图的邻接矩阵，图遍历算法也可以用来进行反欺诈测试。具体在金融领域，图论算法可以用于风险控??制和断线修复工作。作为全球最大的社交媒体网站，Facebook一直在努力积极打击网站上的欺诈和作弊行为。CopyCatch是Facebook在2013年著名国际会议WWW上发表的一篇反作弊论文，描述了Facebook处理一种叫做Lockstep的作弊类型的算法。锁步行为是指存在这样一个页面，大量用户在短时间窗口内喜欢了这个页面。检测Lockstep行为变成检测此类用户和页面的集合。我们来看看Facebook是如何设计反作弊算法的：首先构建一个二分图。二分图中有两种类型的节点：一种是用户，另一种是Facebook页面。当Facebook用户喜欢一个页面时，在代表用户的节点和代表页面的节点之间建立一条边。Lockstep行为可以用以下数学公式来描述：这个问题本身可以转化为检测二分图中的二分核（BipartiteCore）的问题。检测二分核问题本身就是NP-hard问题，因此需要设计近似算法来解决这个问题。Facebook将此问题定义为优化问题。首先重新定义问题描述：这个问题可以简化为如下优化问题：其中L表示用户点击页面的时间矩阵，c是欺诈用户欺诈行为的中心向量，P'是欺诈页面的集合。这个优化问题的本质是：选择聚类中心c和页面子空间P'，使聚类中给定时间窗口内的用户数量和用户喜爱行为最大化。迭代算法被用来解决这个问题。算法第一步是选择聚类中心c，算法第二步是根据c选择P’。算法框架如下：UpdateCenter函数的过程如下：UpdateCenter函数的基本思想是在当前聚类中心范围内重新选择聚类中心，使得新的聚类中心能够覆盖更多的用户和更多的喜欢行为。FindUsers函数的过程如下：FindCenter函数的过程如下：FindCenter函数的基本思想是将二分图中与某个页面关联的用户按照页面时间排序，然后检查给定时间窗口中的用户子集。同类动作的最大值。将新的聚类中心点设置为用户子集合的中心。UpdateSubspace函数的流程如下：UpdateSubspace函数的基本思想是检查除当前欺诈页面子集以外的页面，看是否存在欺诈可能性较高的页面（即关联的欺诈页面）用户是当前欺诈页面对应用户的超集），如果存在，则用新页面替换当前页面。作者提供的Map-Reduce版本如下：CopyCatch算法的收敛速度非常快，在Facebook数据集上迭代10次左右就可以收敛：Facebook的CopyCatch算法的思路和实现比较简单，并且通过在线运行确认该算法效果符合在线要求，是一个非常好的算法。虽然该算法发表已有一段时间，但仍具有现实借鉴意义。CopyCatch算法使用了图论的相关知识。时至今日，图论已广泛应用于反欺诈/反作弊/信息安全等领域。精通图论知识已经成为大数据和人工智能从业者的必备技能。希望本文能为互联网行业的相关从业者提供宝贵的经验。原标题：CopyCatch：通过在社交网络中发现锁步行为来阻止群体攻击作者：AlexBeutel、WanhongXu、VenkatesanGuruswami、ChristopherPalow、ChristosFaloutsos
