复杂网络算法在平台业务安全中的应用

对于电商平台和社交平台为主的平台业务，其安全涉及方方面面，常见的如刷单、黑灰产。本文以 Louvain、FRAUDAR 和 CatchSync 这三种典型的复杂网络算法（基于图的挖掘算法）为例，结合实际业务场景，包括交易、社交和直播等互联网平台的核心业务，介绍复杂网络算法在平台业务安全中的应用实践，为互联网平台对抗黑灰产提供一些可借鉴的经验。

在电商平台作弊团伙识别中的应用

将经验性的专家规则和统计机器学习模型结合，用来识别电商平台典型的刷单行为非常有效。根据笔者的工作经验来看，前期经过长时间的积累和研发后，基本可以把采用“粗刷”（简单粗暴的刷单方法，例如，同一设备大量下单）方式的刷单者打击殆尽，后期的挑战主要是识别团伙形式的“精刷”。复杂网络算法（图模型、图挖掘）是通过“全局性”信息（群体用户信息）来找出作弊行为的，而不是仅利用“局部性”信息（单一用户的行为信息），因此复杂网络算法是打击“精刷”作弊的有效技术手段。我们在实践中采用了两种复杂网络算法来识别团伙刷单行为，用这两种算法识别隐蔽性较高、组织性较强的团伙作弊非常有效。

这两种复杂网络算法分别应用于两种典型的业务场景：针对全站全量事件的前置团伙挖掘，以及针对风险事件的后置团伙挖掘。在前置团伙挖掘中，我们使用了循环FRAUDAR算法，在经验阈值的控制下，每天召回的订单量约占平台全部订单量的10%~20%左右，而对作弊团伙的识别精度则为90%左右；在后置团伙挖掘中，我们使用了Louvain算法[6]，对作弊团伙识别的精度在70%以上。

• Louvain算法在识别作弊团伙中的应用

Louvain算法是基于模块度（modularity）的社区发现算法，该算法的效率和效果都比较好，并且能够发现层次性的社区结构。该算法的优化目标是通过对社区的划分来最大化整个图属性结构（社区网络）的模块度，从而得到社区发现结果。其中需要理解以下两个核心概念。

• 模块度：用于描述社区内的紧密程度，其值用Q表示。
• 模块度增量：即把一个孤立的点放入一个社区C后，模块度前后的变化。

模块度增量的计算方法是，首先计算一个点的模块度和社区C的模块度，再计算合并后新社区的模块度，新社区的模块度减去前两个模块度就是模块度增量，即：

将上述计算公式展开，得到模块度增量

其中括号中第一项表示的是将孤立的节点和社区C放在一起时对整个网络模块度的影响，而第二和第三项则分别表示孤立的节点和社区C分开时各自对整个网络模块度的影响，所以它们的差值就反映了将一个孤立的节点放入社区C前后对整个网络的模块度的影响。

算法的具体计算过程如下：

1. 先把每个点作为一个社区，然后考虑每个社区的邻居节点，将其合并到邻居节点所在的社区，然后分别计算找到最大的正，将该点合并到最大正所对应的社区。多进行几轮迭代，直至合并后社区划分的结果不再变动。其中存在的问题是，不同的节点访问顺序将导致不同的结果，不过笔者在实验中发现这个顺序对结果的影响不大，但是会在一定程度上影响计算所消耗的时间。
2. 将上一步得到的新的社区作为一个新的点，重复上述过程。

那么，如何确定新的点之间的权重呢？答案是，将两个社区内相邻点之间的权重之和作为两个社区各自退化成一个点后二者之间新的权重。

该算法主要有3个优点：易于理解、非监督和计算速度快。

最后，我们可以得到层次化的社区发现结果，如下图所示。其中第一张图描述了交易订单的社区发现结果，第二张图描述了风险账户的社区发现结果。另外，Louvain算法还有加速实现的版本。相关论文中提出的Louvain算法的加速实现方式比较简单直接，即只考虑一个点周围的一定比例的点来进行归并计算，可以基于Spark计算框架通过类似于多路归并的方法来实现。

社区发现结果示例图一

社区发现结果示例图二

• FRAUDAR算法在识别团队作弊中的应用

FRAUDAR算法来源于2016年的KDD（ACM SIGKDD conference on Knowledge Discovery and Data Mining）会议，提出该算法的论文获得了当年的最佳论文奖。FRAUDAR算法要解决的问题是找出社交网站内最善于伪装的虚假账户簇。其原理是虚假账户会通过增加和正常用户的联系来进行伪装，而这些伪装（边）会形成一个很紧密的子网络，这样就可以通过定义一个全局度量，再移除二部图结构中的边，使得剩余网络结构对应的度量的值最大，找到最紧密的子网络，而这个网络就是最可疑的作弊团伙。

FRAUDAR算法

• 建立优先树（一种用于快速移除图结构的边的树结构）。
• 对于二部图中的任意节点，贪心地移除优先级最高（由优先树得到）的节点，直至整个网络结构为空。
• 比较上述每一步得到的子网络对应的全局度量，取该值为最大的子网络，它就是最紧密的子网络，也代表最可疑的团伙。

其中，最关键的地方是定义一个描述可疑程度的度量（metric），该度量在描述可疑程度时具有非常好的性质，包括可扩展性、具备理论上的“界”以及对抗虚假行为的鲁棒性。特别地，该度量可以理解成子网络结构中每个节点的平均可疑程度。

令

代表用户节点的子集，令

代表目标节点的子集，那么

，而

，那么可疑程度的度量被定义为：

其中，第二个公式等式后第1项表示S中节点本身的可疑程度之和，而第2项表示S中节点之间边的可疑程度之和，整个公式用来表示点和边的总的可疑程度。根据这样的定义，很容易可以得出以下4条性质：

• 如果其他条件不变，包含更高可疑度节点的子网络比包含较低可疑度节点的子网络更可疑。
• 如果其他条件不变，在子网络中增加可疑的边会使得子网络更可疑。
• 如果节点和边的可疑程度不变，那么大的子网络比小的子网络更可疑。
• 如果节点和边的总的可疑程度相同，那么包含节点数少的子网络更可疑。

该算法的核心计算过程就是贪心地移除图中的点，使得每次变更f的变化最大。在移除一个节点时，只有与之相邻的节点会发生变化，那么这样最多产生O(|E|)次变更，如果找到合适的数据结构使得访问节点的时间复杂度为O(log|V|，那么算法总的时间复杂度就是O(NlogN）。

基于这样的考虑建立优先树，这是一个二叉树，图中的每个节点都是树的一个叶子节点，其父节点为子节点中优先级较高的节点。这棵树建完之后就可以按照O(log|V|的速度获得优先级最高的节点。

如何识别（对抗）虚假行为呢？可以通过列权重下降（Column-weighting）的方法来实现。为了识别虚假行为，我们不能简单地将图中每条边的嫌疑程度设为相等，因为出度和入度较大的节点可能真的就是很受欢迎的节点，例如“大V”用户和销量不错的商品，这些节点是天然存在的，并不是虚假的。如果图中每条边的嫌疑程度相等的话，那么在最大化可疑程度的度量时，我们就会聚焦于这些出度和入度较大的点，而不是聚焦于紧密的子网络。所以，如果存在节点i到一个出度和入度较大的节点j的边，就需要将其边对应的嫌疑程度降低，这就是列权重下降方法。该方法使得我们不仅关注出度和入度较大的节点，而且更关注紧密的子网络。

举个例子，在邻接矩阵中，令行代表用户节点，列代表目标节点，那么虚假用户向正常的目标节点增加边并不会使得子网络的嫌疑程度变低，因为虚假用户向正常的目标增加边只会使正常目标对应的边的嫌疑程度下降，而嫌疑子网络内的权重却不会发生变化。

对于Column-weighting函数的选择，论文作者的实验表明，选择类似于词频和逆文档频率（TF-IDF）形式的函数时，算法的表现会比较好，即：

其中是一个常数，避免出现分母为零的情况，原始论文的实验中把c设为5。

FRAUDAR算法的优点是：

• 采用了“贪心”的计算思想，运行速度很快。
• 理清晰明了，而且能够给出理论上的“界”。
• 能够识别虚假行为。

该算法的缺点是：

• 因为采用了贪心计算的方法，所以不能保证得到全局最优解，在原始论文中作者给出了FRAUDAR算法在理论上的“界”。
• 原始算法只能找出一个最紧密的子网络，即可疑程度最大的子网络。
• 只考虑了边的权重，没有考虑节点的权重（或者节点的权重都设为相等的常数），而且节点和边的嫌疑程度需要自定义。

为了将该算法应用到交易风控中，笔者做了一定的改进，即在网络结构中找出最可疑的子网络后，移除子网络中所有相关的边，再使用FRAUDAR算法对剩余的图结构进行挖掘，找出次可疑的子网络。通过这种方法，我们就可以得到可疑程度由高到低排列的多个子网络。我们称这种方法为循环FRAUDAR算法。

在识别虚假社交关系中的应用

在社交平台和电商平台中，用户与用户或者用户与商品之间会形成巨大的有向网络。而由于虚假行为的存在，这个有向网络中被注入了异常的行为模式，例如Twitter、Facebook、微博等社交平台中会有虚假的关注、虚假的转发等，而Amazon、淘宝等电商平台中会有误导性评论、虚假交易等。如何在这些静态的有向网络中识别可疑行为？一般来说，可疑的异常行为会形成一个紧密的子网络（dense subgraph），之前提到的FRAUDAR算法就是通过贪心策略找到这样的紧密子网络的。而CatchSync算法则利用了两个容易被欺诈者忽视的特点，一个是同步行为特性（synchronized behavior），另外一个是稀有行为特性（rare behavior）。在大多数情况下，异常的行为模式往往是稀少而集中的，我们可以设计算法来捕获它们，CatchSync算法正是基于同步行为特性和稀有行为特性来找到有向网络中的异常行为模式的。

下面简要介绍CatchSync算法的原理。CatchSync算法是基于图的性质提出的异常识别算法，在有向图结构中我们可以利用很多性质，包括但不局限于：

• 基本的出度和入度。
• HITS（Hyperlink-InducedTopic Search）得分。
• 中介中心性（betweenness centrality）。
• 节点的入权重和出权重（在带权重的网络中）。
• 节点对应的左右奇异值向量的第i个元素值。

CatchSync算法利用了HITS得分中的权威度（authoritativeness）和入度（indegree），将其作为基本的特征。基于authoritativeness和indegree，CatchSync算法提出了两个新的概念来研究源节点的特性，分别是synchronicity（同步性或者一致性）和normality（正常性）。其中，synchronicity用于描述源节点u的目标节点在特征空间（in-degreevs authoritativeness，简称InF-plot）中的同步性，而normality用于描述源节点u的目标节点的正常性。

在CatchSync算法中用c（v,v*）来表示在特征空间InF-plot中源节点的目标节点之间的临近性（或者相似性）。为了快速计算，该算法将特征空间划分成G个网格，并将原有向图中的节点映射到每个网格中。有了这个网格之后，c（v,v*）的计算就非常容易了，如果两个节点在同一个网格中，那么临近性为1，否则为0，即：

得到c（v,v*）之后，就可以计算synchronicity和normality了。其中，synchronicity定义为：

其含义为源节点u的任意目标节点对的平均临近性。

normality的定义为：

其含义为源节点u的任意目标节点与剩余节点的平均临近性。

有了synchronicity和normality，我们就可以画出特征空间SN-plot，进而基于正态分布找出异常的节点（高同步性和低正常性的节点）。

为了评估直播业务中是否存在主播刷粉丝关注量的情况，我们对现有直播业务中的关注关系应用CatchSync算法进行了挖掘，得到全站直播业务中关注关系的SN-plot和InF-plot，如下两图所示。

SN-plot示例图

InF-plot示例图

从图中可以看出，直播业务的关注关系中存在一定的高同步性和低正常性的节点，这些节点在很大程度上是可疑的。我们利用CatchSync算法提取出这些异常节点后，经过人工验证，这些节点确实有问题。

自从笔者的团队将复杂网络算法（基于图的挖掘算法）上线以来，识别团伙作弊在风控中的作用越来越显著，为打击黑灰产提供了充分的技术支撑，而且帮助团队建立起一套较完备的风险分析技术体系，包含了主流的机器学习技术：统计机器学习方法、深度学习方法和基于图的挖掘算法。同时，我们也搭建了“平台化”的风控系统，把机器学习算法和人工运营有效结合起来，不仅利用有标签的数据持续提高识别能力，还干预和控制了各种风险。当然，在和黑灰产持续对抗的道路上，我们还需要不断优化和提升风控技术手段，以应对未来充满挑战的业务安全生态环境。

本文节选自博文视点新书《机器学习互联网业务安全实践》。平台型互联网公司无不面临着垃圾注册、刷单、“薅羊毛”、信息泄露等业务安全方面的威胁，与黑灰产的对抗需要构建一套有效的业务安全模型体系，而对这个垂直领域，业内的关注度较低。本书作者结合自己多年的实践经验，从技术角度讲解了构建这套模型体系所涉及的常用算法和工具，适合从事业务安全算法领域的初学者学习，也适合中高阶的从业者参考。新中国成立70周年来临之际，不再需要任何形式的保媒拉纤，左下阅读原文即可让你们跨越时空直接会面。

内容简介：互联网产业正在从IT时代迈入DT时代（数据时代），同时互联网产业的繁荣也催生了黑灰产这样的群体。那么，在数据时代应该如何应对互联网业务安全威胁？机器学习技术在互联网业务安全领域的应用正是答案。本书首先从机器学习技术的原理入手，自成体系地介绍了机器学习的基础知识，从数学的角度揭示了算法模型背后的基本原理；然后介绍了互联网业务安全所涉及的重要业务场景，以及机器学习技术在这些场景中的应用实践；最后介绍了如何应用互联网技术栈来建设业务安全技术架构。作者根据多年的一线互联网公司从业经验给出了很多独到的见解，供读者参考。本书既适合机器学习从业者作为入门参考书，也适合互联网业务安全从业者学习黑灰产对抗手段，帮助他们做到知己知彼，了解如何应用机器学习技术来提高与黑灰产对抗的能力。

作者简介：

王帅，花名“莲华”，美丽联合集团（蘑菇街）安全部风控算法技术负责人。2015年初加入蘑菇街，主要负责风控相关的反作弊算法，从无到有搭建了电商平台的风控策略架构体系，主要研究方向是基于机器学习的风控算法策略。

吴哲夫，本科就读于山东大学，研究生就读于北京大学，曾在微软亚洲研究院实习，毕业后就职于阿里巴巴（北京），现供职于美丽联合集团。