SynchroTrap:基于相似度的异常检测算法
SynchroTrap简介
什么是SynchroTrap
顾名思义，SynchroTrap即在同步情况下的欺诈。黑产通过控制大量的账号，需要在有限的时间里获取最大的利益，那不可避免的就会产生多个黑产账号在某段时间内发生重合行为的现象。
原理
恶意账户在社交网络上通常会有松散同步行为，行为上具备一定的相似度，将用户产生行为的时间进行对比，构建用户的相似度网络，实现大规模筛查。
算法设计
同步性
论文采用三元组的形式，来表示用户的行为，即<U,T,C>，u表示用户id，T表示发生行为的时间戳，C表示设定的某一个场景，论文定义公式如下：
同步性，便是在某个场景下，用户在一定的时间差范围内，都产生了行为，则认为这两个用户具备同步性。
相似度计算
论文中给出了两种计算场景
约束相似度：比较两个用户在相同场景下的相似度；
全局相似度：比较两个用户在全场景下的相似度。
约束下的相似度
约束下的相似度，即为在某个场景下，两个用户之间的相似度计算。Jaccard公式如下：
其中
U
i
U_{i}
Ui、
U
j
U_{j}
Uj、
C
k
C_{k}
Ck分别表示用户i，用户j，场景k；
A
i
k
A_{i}^{k}
Aik、
A
j
k
A_{j}^{k}
Ajk分别表示用户i、j在场景k下产生的行为，即在场景k下，用户i和用户j产生的交集比上用户i和用户j产生行为的并集。
全局相似度
全局相似度，避免了在某些场景，如安装app中，相似度只能取0或者1的情况，Jaccard公式如下：
大家可以根据实际的不同情况，采用单独约束相似度或者单独约束相似度+全局相似度的组合。
以上，就是SynchroTrap如何计算相似度的过程，大家在构建图的过程中，可以将此部分作为节点之间的权重使用，判断节点之间的相似度是否能达到设定的阈值，来决定是否连接两个节点。
聚类计算
论文中拟采用单链层次聚类，就是先把每个节点当做一个簇，然后将每个簇中节点与新簇进行相似度计算，得出一个最小相似度，该相似度达到某个阈值后，则进行合并。
但是考虑到这种方式无法进行并行计算，因此论文作者将数据进行图化，遍历每一个连通子图，将每个子图中的边作为两个节点之间的相似度，只有相似度满足以下两个条件，才得以保留：
1、至少存在一个场景相似度大于设定的阈值，才能保留边；
2、全局相似度大于设定的阈值，才能保留边。
如何进行并行计算
论文中如何对用户进行并行计算呢？
如果t+n天需要进行计算，则按照如下方式进行：
1、将数据按照天数分割，最大时间单位为天；
2、在每天的数据中计算用户之间的相似度，如果有多个场景的话，还可以再进行细分场景计算；
3、由于每天的计算是独立进行的，因此，可以对天数进行并行计算，然后，再根据每个用户每天的行为进行合并，达到多天聚类的效果。
滑动窗口
论文中，作者给出一个缩短计算数据的方式，即设定一个滑动窗口，将每天时间按照小时级划分，则每天共有24个时间段，设定最短时间为T，那么在T时间的上线范围内，这些数据都将不再进行重复计算，如下图所示：
横坐标为时间T，纵向为两个用户
U
1
U_{1}
U1、
U
2
U_{2}
U2，滑动窗口为
T
s
i
m
T_{sim}
Tsim，那么在
2
T
s
i
m
2T_{sim}
2Tsim内，数据应该两个重合的数据部分将不再进行计算，即阴影部分。
复杂度
1、在理论情况下，n个用户每天产生r个动作的情况下，全局相似度计算为
O
(
r
n
2
)
O(rn^2)
O(rn2)；
2、在约束情况下，某个场景中m个用户每日产生r个动作的情况下，相似度计算为
O
(
r
m
2
)
O(rm^2)
O(rm2)；
3、有n个用户，每个用户的全连通子图查询为
O
(
n
)
O(n)
O(n)，结合第二种情况进行相似度计算，则复杂度为
O
(
r
m
2
+
n
)
O(rm^2+n)
O(rm2+n)。
好了，以上就是我对SynchroTrap的理解了，大家有指正或者需要补充的地方，可以留言或者加我QQ：1143948594，随时联系。
附：论文链接Uncovering Large Groups of Active Malicious Accounts in
Online Social Networks