【51CTO.com自从互联网出现以来，各种垃圾和恶意信息一直在互联网上流传。处理各种垃圾、作弊甚至欺诈信息已成为互联网公司必须解决的问题。特别是随着各种社交网站的兴起，反作弊和互联网安全已成为研究和行业面临的挑战。主要的互联网公司已经建立了一个专门的反作弊团队来处理每天的反作弊行为。
图论算法是反作弊中最常用的技术之一，它通常可以归类为图论问题。例如， 可以使用SVD 分解图的邻接矩阵的 *** 也可以使用图遍历算法进行反欺诈检查。在金融领域，图论算法可用于风险控制和失去联系的修复。
作为全球***社交媒体网站，Facebook 一直在努力积极应对网站上的欺诈和作弊。CopyCatch 是 Facebook 发表于2013年的著名国际会议 WWW 反作弊论文讲述了 Facebook 处理一类叫作 Lockstep 欺诈算法。
Lockstep 行为是指存在此类页面，大量用户在短时间窗口内称赞此页面。Lockstep 行为已经成为测试此类用户和页面的 *** 。让我们来看看 Facebook 如何设计反作弊算法：
首先，构建一个二部图。二部图有两种节点：一种是用户，另一种是 Facebook 页面Facebook 用户称赞某个页面时，会在代表用户的节点和代表页面的节点之间建立一个边缘。Lockstep 行为可以用以下数学公式来描述:
这个问题本身可以转化为二部图检测二部核(Bipartite Core)问题。检测二部核问题本身就是 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 : Stopping Group Attacks by Spotting Lockstep Behavior in Social Networks
作者：Alex Beutel ,Wanhong Xu ,Venkatesan Guruswami ,Christopher Palow , Christos Faloutsos
【51CTO转载合作网站时，请注明原译者和出处51CTO.com】
版权声明
本文仅代表作者观点，不代表本站立场。
本文系作者授权发表，未经许可，不得转载。
