大家好，我是小伍哥，今天我们继续探讨一个新的方法，基于同步性-稀有性进行图网络的异常检测，用来发现大型网络中存在的异常连接。
英语论文：http://perozzi.net/publications/16_thesis.pdf
英语论文：后台回复【论文】获取
GitHub地址：https://github.com/mjiang89/CatchSync
在社交媒体上，用户相互关注的行为会形成大规模的有向图，给定一个包含数百万个节点的有向图，我们如何仅根据其连接模式来自动发现异常、可疑的节点？
在Twitter、微博、抖音、淘宝、亚马逊等线上网站中，用户之间或用户与商家之间会形成巨大的网络。Twitter上用户之间的follow，可以形成“who-rate-who”网络，电商中用户在商家下的购买、评论行为也是个巨大的网络，“who-buy-who”,“who-rate-who”。在这些巨大的网络中，有些人在做着不光彩的事，例如：在Twitter、微博里，有些人明星、网红为了提升自己或者一个话题的影响力，会购买转发形成“虚假转发“，也有人会购买“虚假关注者”。电商为了提高自己的销量或搜索权重，会花钱雇人虚假购买自己的产品，撰写虚假的评论，造成【虚假交易】和【虚假评论】，操纵社交网络，扰乱网络流量，破坏平台公平性，谋取巨额利润。
一、同步行为和稀有行为
今天介绍的算法：CatchSync，其目的就是找到这些水军，它利用了欺诈者在图中留下的两个迹象：
一个是同步行为特性（synchronized behavior），另外一个是稀有行为特性（rare behavior），也就说在大多数情况下，异常的行为模式往往是稀少而集中的，这样就可以设计算法来抓取这样的异常行为模式，CatchSync算法正是基于同步行为特性和稀有行为特性来找到有向网络中的异常行为。
同步行为：异常的源节点会倾向于形成同步行为，即他们指向的目标节点之间具有相似性
稀有行为：异常的源节点与大多数节点很不同，即他们指向的目标节点与一般节点较为不同
如下图所示，一组可疑的粉丝团体和他们所关注的人，这些粉丝总共有300 万，从1500 个的用户群体中选择刚好20 个去关注，形成了一种罕见的同步性连接结构，图中所示的Twitter 注册名相似性（@Buy_AB22, @Buy_BT27,@Buy_BT68）等附加信息是怀疑他们用脚本产生的有力证据。
同样在微博数据中，也发现了类似的情况，左下图中的出度在64的时候，产生了一个尖峰，在移除了CatchSync 所标记的可疑节点，出度分布变得更顺滑，并且接近于幂律分布（红色线条），类似的现象右下也可以看到，出度在30多的时候分布也是异常，这个数据属实有点夸张，大家知道微博的明星粉丝咋这么高了吧，我觉得大部分这种僵尸模式可以检测出来。
2011 年1 月腾讯微博 2011 年11 月腾讯微博
从细节上说，包括僵尸粉、机器人等的可疑节点在网络中会形成这样的行为模式：1) 同步性行为（同等节奏地发生），他们通常会同时关注同等数量，比如20、64 或者100 个目标用户；2) 异常的/罕见的行为，他们的行为模式和大多数节点非常不同。本文给出快速有效的方法CatchSync 来衡量两大行为特征，即一组用户节点的同步性和正常性：通过观察在同步性-正常性绘图（Synchronicity-Normality Plot）中的可疑节点，实现有效检测。我们接下来看看什么事同步性-正常性绘图。
二、可疑行为的同步性分析
有了对同步行为-稀有行为的初步认识，本小节会提出同步性行为检测问题，目标是在有向图中检测可疑节点，问题的定义如下：给定在节点集合U 的N 个节点的有向图，寻找诸如虚假粉丝、机器人的可疑源节点集合Usync和诸如被关注的人、目标主机的目标节点集合Vsync，这些节点形成了同步而又异常的连接模式。
同步性是指节点相互之间有非常相似的行为模式，异常性是说这些行为模式与图中主要节点的模式非常不同。表5.2中给出数学符号及其定义描述，解决上述问题的步骤如下：
1）给出目标节点设计特征空间
2）定义同步性和正常性来量化节点行为模式，同时对同步性-正常性图的形状给出通用的理论证明
3）最后采用基于距离的异常检测算法找到图中的可疑节点。
过去基于图的数据挖掘工作中从节点的行为模式中得到很多特征方面的启示，包括(a) 出度和入度，(b) HITS 值，包括枢纽度（hubness）和权威度（authoritativeness），(c) 中介性（betweenness）和核心性（centrality），(d) 带权图中的节点的向内权重和向外权重，(e) 图的邻接矩阵的第i 个左奇异值向量和右奇异值向量。用p(u) 2 Rk 定义了节点u 的k 维度特征向量。从图结构中抽取反映节点行为特征的特征向量，这些特征可以是上述所有特征或者是任意维度的特征。本文中选择度数和HITS 值，除却容易计算和绘图外，下述特征在异常检测中能够保证可解释性：
度数（出度和入度）：用I(u) 定义u 的源节点集合，用O(u) 定义u 的目标节点集合。节点u 的入度di(u) 是源节点的数量，也就是I(u) 的大小。节点u的出度do(u) 是目标节点的数量，也就是O(u) 的大小。在社交媒体，大的入度是说存在许多粉丝账户，而且这些顾客从这种卖粉丝的服务中得到相似的入度值，而这些入度值比起普通用户的要大很多，但比起真实知名的名人要小很多。机器人或者是僵尸粉通常有相似的出度值，因为这些服务很容易会让机器人账户关注同样数量的顾客。当机器人账户的出度值更小，他们不仅更聪明了，但还是有同步性行为。另外，度数值与之前发现的尖峰有关。
HITS 值（枢纽度和权威度）：参照Kleinberg 的著名工作，用hub(u) 定义节点u 的枢纽度，用aut(u) 定义节点u 的权威度。把“粉丝-关注的人” 网络构建成邻接矩阵，第一个左奇异值向量含有粉丝节点的枢纽度，第一个右奇异值向量含有关注的人的权威度。一个所关注的人如果有很多粉丝，那么他会有很高的权威度。连接了知名名人的粉丝比起普通用户会有更高的枢纽度。僵尸粉通常会比有同样出度值的用户有更小的枢纽度，因为顾客往往比起知名的名人要不那么出名。顾客比起有同样入度值的用户有更小的权威度，因为他们大多数的粉丝都是在网络中并不重要的僵尸粉。这两组特征代表了社交媒体中的用户行为模式。实验中这些特征能够很好地找到可疑节点。要注意的是如果存在附加信息可以使用，这个方法是能够很容易的融入这些附加特征的，而检测效果会更好。
接下来给出特征空间中一些绘图的定义。给定源节点u，画出用出度do(u) vs 枢纽度hub(u) 的对数下二维特征空间，记作“OutF-plot”。相似的，给定目标节点u，画出入度di(u) vs 权威度aut(u) 的对数下二维特征空间，记作“InF-plot”。表5.3总结了上述绘图的名字和描述。
(a) TwitterSG 中的InF-plot (b) TwitterSG 中的SN-plot
(c) WeiboJanSG 中的InF-plot (d) WeiboJanSG 中的SN-plot
特别的，上图(a) 和图(c) 是TwitterSG 和WeiboJanSG 中的InF-plots。在TwitterSG 中用X 标记为可疑的粉丝之一，用Y 标记为和X 有同样的出度的普通用户。把它们的目标节点（关注的人）标记在图(a) 中，发现X 的目标节点在InF-plot 中相近，但Y 的目标节点不相似。换句话说，X 的目标节点有相似的入度和权威度，但是Y 的目标节点有的是非常知名，有的就是普通用户，所以在特征空间中非常不同。在WeiboJanSG 中能观察到相似现象。图(c) 中看到X 的目标用户落在距离主体部分很远的小点簇中。这些点往往有从1,000 到100,000 的入度值，但是这些人并不如同样入度值下的普通用户一样有名（这些人偏左）。
由此提出了研究源节点行为模式的两个概念：
a) “同步性” sync(u) 来量化u 的目标节点在特征空间（入度vs 知名度）的同步性特征
b) “正常性” norm(u) 来量化u 的目标节点在特征空间（出度vs 枢纽度）的正常性特征。定义p(v) 来表示目标节点v归一化的特征向量，定义c(v,v′) 为目标节点v 和v′ 在特征空间（InF-plot）中的相似程度。于是有：
要快速计算每一对节点的相似度，把特征空间分割为G 个格子(grid cell)，并
且把每一个节点映射到特定的格子中。如果两个节点在同一个格子中，他们也就有相似的特征向量，在特征空间中是相近的。于是有
由此定义同步性和异常性。
定义5.1：同步性和异常性定义节点u 的同步性为u 的每一对目标节点(v,v′ ) 之间的相似程度：
定义节点u 的正常性为u 的一个目标节点和全网络的某一个随机节点(v,v′ ) 之间的相似程度：
同步性和正常性值是从0 到1 的。由此知道可疑的源节点u 往往是有相当大的sync(u) 和极其小的norm(u)：
极其大的sync(u)： 很大的sync(u) 值说明在特征空间里会存在一大群节点和节点u 有同样的特征。如果粉丝节点u 有一个很大的sync(u) 值，那么u 和其他节点一样会有相似的关注行为（相似的出度和相似的枢纽度）。也就是与同一组关注的人（节点）连接。僵尸粉往往会有极大的同步性值。
极其小的norm(u)：很小的norm(u) 值说明在特征空间里节点u 相比于大多数节点是异常节点。如果粉丝节点u 有较小的norm(u) 值，相比于社会媒体中的大多数粉丝节点来说，u 会有很不同的关注行为模式（很不同的出度和不同的枢纽至）。也就是说节点u 几乎不与大多数节点相联系。僵尸粉往往给出很小的正常性值。
三、基于行为同步性的可疑用户检测算法
首先，给目标节点生成特征空间，然后根据目标节点在特征空间的相对位置，计算源节点行为的同步性和正常性。最后，用基于距离的异常检测算法来检测同步性-正常性图中的异常节点。更准确的说，给源节点选取了“出度vs 枢纽度” 的二维特征空间，给目标节点选取了“入度vs 权威度” 的二维特征空间。图的邻接矩阵形成的第一个左(右)奇异值向量是枢纽度(权威度)。
算法的基本流程就到这里结束了，本文理论还是比较复杂的，我自己也还有部分没理解透彻，更多细节大家可以看论文细节，下期再讲实际应用方式以及应用的效果。
就目前而言，我们至少可以检测我们自己系统中各种关系网络的出度分布，能够把特别异常的用户检测出来，也算是一个很好的应用思路了。
若有收获，就点个赞吧
0 人点赞
