CatchSync算法原理及应用

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

二、算法
CatchSync算法的原理，CatchSync算法是基于图的性质提出的异常识别算法，在有向图结构中可以利用很多性质，包括但不局限于：
a）基本的出度和入度；
b）HITS得分（hubness和authoriativeness）；
c）中介中心性（betweenness centrality）；
d）节点的入权重和出权重（带权重网络中）；
e）节点对应的左右奇异值向量的第i个元素值。

而CatchSync算法则利用了HITS得分中的authoritativeness和入度作为基本的特征。基于authoritativeness和入度，CatchSync算法提出了两个新的概念来研究源节点的特性，分别是“synchronicity”（同步性或者一致性）和“normality”（正常性），其中“synchronicity”用来描述源节点u的目标节点在特征空间（入度 VS authoritativeness，简称InF-plot）中的同步性，而“normality”用来描述源节点u的目标节点的正常性。算法中用c(V,V~)来表示在特征空间InF-plot中源节点的目标节点之间的临近性（或者相似性）。为了快速计算，算法将特征空间划分成了G个网格并将原有向图中的节点映射到每个网格中。有了这个网格之后，c(V,V~)的计算就非常容易了，如果两个节点在同一个网格中，那么临近性为1，否则为0。

得到c(V,V~)之后，就可以计算“synchronicity”和“normality”。其中“synchronicity”定义如下公式，其含义为对于源节点u的任意目标节点对的平均临近性。


“normality”定义如下公式，其含义为对于源节点u的任意目标节点与剩余节点的平均临近性。
有了“synchronicity”和“normality”，我们就可以画出特征空间SN-plot，进而基于正态分布找出异常的节点（高同步性和低正常性的节点）。

三、应用
为了评估在XX业务是否存在刷粉丝关注的情况，我们对现有XX业务中的关注关系应用CatchSync算法进行了挖掘，得到全站XX业务中关注关系的InF-plot和SN-plot的曲线如下：


从上图可以看出，在XX业务的关注关系中是存在一定的高同步性和低正常性的节点，那么这些节点在很大程度上是可疑的。

四、总结与未来挑战
复杂网络中包含了丰富的信息，利用这些信息可以挖掘出网络中异常节点，对于关注等业务而言，其数据结构中存在天然的有向图关系，正好可以利用这些基于图的算法来进行一些挖掘，而CatchSync就是其中很好的尝试之一。

五、参考文献
CatchSync: Catch Synchronized Behavior in Large Directed Graphs (KDD 2014 Best Paper Final List) Authors: Meng Jiang, Peng Cui, Alex Beutel, Christos Faloutsos and Shiqiang Yang。

最后

以上就是鲤鱼红酒为你收集整理的CatchSync算法原理及应用的全部内容，希望文章能够帮你解决CatchSync算法原理及应用所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。