【业务实战】Fraudar算法在关系网络反欺诈实战
前言
在目前黑产对抗中, 刷单、虚假关注等都是较为常见的风控场景,
本文主要讲述 Fraudar算法 在其中的原理及其思路.
Fraudar 算法
Fraudar 算法是 Facebook 在 2016 中 《FRAUDAR: Bounding Graph Fraud in the Face of Camouflage》 提出针对社交虚假粉丝等场景的算法, 具有很好的工业效果.
场景刻画
针对 user 以及 product 评论或关注场景分析,
部分聪明欺诈者会伪装自身欺诈情况, 装作正常用户,
主要存在如下三种情况:
- 情况一: 欺诈者控制账号呈现随机用户行为加以伪装, 如图a所示
- 情况二: 欺诈者控制账号与热门目标呈现互动加以伪装, 如图b所示
- 情况三: 欺诈者劫持用户, 由于劫持用户大多数非高频用户, 可认为情况一形式, 如图c所示
核心: 欺诈用户针对待刷量对象均会呈现较为聚集的情况, 为降低成本一般账号处于批量情况, 这些账号针对其他对象关联较弱.
算法原理
考虑用户对商品评分的场景, 设定如下变量:
- 用户集: \(u = \{ u_1, \cdots, u_m \}\)
- 商品集: \(w = \{ w_1, \cdots, w_n \}\)
全局度量公式如下:
\[ \begin{aligned} g(S) = \frac{f(S)}{|S|} = \frac{(f(A) + f(B))}{|A| + |B|} \end{aligned} \]
其中 f(S) 代表图S节点可疑度的总和, |S|
是图S节点数, g(S) 是图S的平均可疑程度.
因此若一个节点的可疑度大于 g(S) 当其纳入该图中时,
会扩大该图的可疑程度.
可疑度定义: \(\frac{1}{\log (x + 5)}\),
x是单个店铺引申的边数, 公式代表交易量越大的店铺其交易可疑程度越小.
注意: 节点移除会导致剩余网络可疑度更新, 如一个用户移除, 与其相连的商铺会降低可疑程度, \(100 \times \frac{1}{\log (100 + 5)} \rightarrow 99 \times \frac{1}{\log (100 + 5)}\).
为说明度量指标的合理性, 作者证明该度量指标存在如下四个性质:
node suspiciousness：节点的可疑度越高，社区的可疑度越高 \[|S| = |S'| \land f_{\varepsilon}(S) = f_v(S') \land f_{\varepsilon}(S) > f_v(S') \Rightarrow g(S) > g(S')\]edge suspiciousness：边的可疑度越高，社区的可疑度越高 \[e \notin \varepsilon \Rightarrow g(S(\mathcal{V}, \varepsilon \cup \{e\})) > g(S(\mathcal{V}, \varepsilon))\]size：边密度一样，越大的社区可疑度越高 \[|S| > |S'| \land S \supset S' \land \rho(S) = \rho(S') \Rightarrow g(S) > g(S')\]concentration：节点和边的可疑度之和一样，越小的社区可疑度越高 \[|S| < |S'| \land f(S) = f(S') \Rightarrow g(S) > g(S')\]
优化
由于用户和商品一般均较多, 一个个节点进行迭代，成本较高, 如共1W用户, 1W商品, 则需要迭代约2W次, 因此存在如下优化思路:
- 设定阈值: 初始化时剔除大量低可疑度用户和商品
- 动态步长: 初期剔除低风险节点可寻找最低的
N个或N%个, 随着时间逐渐收敛到1个.