SybilWalk：Random Walk based Fake Account Detection in Online Social Networks论文笔记

1. Random Walk based Methods

基于随机游走的方法旨在利用Online Social Networks 的Social Structure，因为我们通常认为，尽管攻击者可以任意控制Sybils之间的连接，但是攻击者很难操作benign node和Sybils之间的连接，因为这种需要benign node的操作。因此，benign node与Sybils之间存在structural gap。基于随机游走的方法就针对这种这种structural gap来检测Malicious Accounts。

之前random walk based methods存在的不足：

1. 它们只能从Online Social Network中标记出良性的用户，或标记出Sybils的用户，但不能同时找出两种用户；
2. 它们对弱同质性社交网络（ weak-homophily social networks）中的Sybils检测精度有限；
3. 它们对训练数据集中的噪声标记不够健壮;

解释一下什么是weak-homophily social networks：

论文中的weak-homophily social networks意思是，虽然理论上我们认为benign region 和sybil region之间的attack edges是稀疏的，但现实世界里的Online Social Networks情况并没有这么理想，不妨举个例子，微博用户有时也会关注关注了他的Sybil，这就使得benign region 和sybil region之间的attack edges多了起来。

解释一下什么是label noise：

对于我们的Dataset，如果用户的给定标签与用户的真实标签不匹配，则该标签是有噪声的。产生噪声的原因主要有以下两种：

1. 一个benign user的账户被盗，所以实际上它已经成为了Sybil user
2. 在人工标记的过程中，出现错误

2. 论文提出了一种新的方法-----SybilWalk

假设有一Online Social Network，用$G=(V,E)$G=(V,E)表示:

1. $u\in V$u∈V表示一个用户
2. $(u,v)\in E$(u,v)∈E表示用户u和v之间的一条边

training dataset:

一个训练数据集，由一些标记过的benign users和一些标记的Sybil users组成

our goal：

Structure-based Sybil detection is to predict the label of each remaining node by leveraging the structure of the social network

2.1 SybilWalk第一步：构建 label-augmented social network

1. 圆形节点：表示用户，如果两个用户之间有关系，就在两个圆形绿色节点之间构建一条实线边
2. 方形节点：两种颜色，表示用户的标签，指明用户是benign还是sybil，如果该用户是benign user，那该用户和蓝色方形节点之间构建一条虚线边

2.2 SybilWalk第二步：Define Badness Scores Using Random Walks

一个节点的badness score 意味着该节点是Sybil user的可能性。一个较大的badness score意味着该节点更可能是一个Sybil。

直观地说，如果一个节点在拓扑结构上更接近节点标签$l_s$ls​，则该节点的badness score会更高。

在我们构建的 label-augmented social network中，共有两种类型的节点，那对于这两种不同的节点类型，它们对应的badness score 取值也不同。

标签节点的badness score

标签节点（方形的），只有两种badness score值，标签节点$l_b$lb​取值0，标签节点$l_s$ls​取值1。用户节点与标签节点$l_b$lb​相连，表示该用户是正常用户$l_s$ls​，反之是恶意账户。

用户节点的badness score

我们定义用户节点 u 的badness score为从这个节点经random walk到达 $l_b$lb​ 之前到达 $l_s$ls​ 的概率。

$p_u=\frac{w_{u v}}{\sum_{t \in \Gamma_{u}} w_{u t}}$pu​=∑t∈Γu​​wut​wuv​​

1. $p_u$pu​ 表示一个节点的badness score
2. $\Gamma_{u}$Γu​是节点 u 的邻居集合
3. $w_{uv}$wuv​是连接节点 u 和 v 的边上的权重

如果 u 在label-augmented social network的结构上就更接近$l_s$ls​ ，那么在随机游走过程中就更有可能首先到达$l_s$ls​ 。

基于随机游走的badness score计算是可行的。例如，计算节点 u 的badness score的一种方法是模拟从该节点开始的随机游走 r 次。在这 r 次中，如果有$r_s$rs​次在到达$l_b$lb​之前到达了$l_s$ls​，那么我们可以将 u 的badness score近似为$\frac{r_s}{r}$rrs​​，然而，这种方法是低效的，因为：

1. 我们通常需要为一个用户节点模拟大量的随机游动，以获得一个可靠的badness score近似值
2. 我们需要为label-augmented social network中的每个节点都模拟大量不同的随机游动

一个用户节点的badness score还可以表示为它的邻居的badness score的线性组合：
$p_{u_{1}}=\frac{w_{u_{1} u_{2}}}{w_{u_{1} u_{2}+w_{u_{1} u_{3}}}} p_{u_{2}}+\frac{w_{u_{1} u_{3}}}{w_{u_{1} u_{2}+w_{u_{1} u_{3}}}} p_{u_{3}}$pu1​​=wu1​u2​+wu1​u3​​​wu1​u2​​​pu2​​+wu1​u2​+wu1​u3​​​wu1​u3​​​pu3​​
总结地说，对于每个节点 u 我们都有以下线性方程：
$p_{u}=\sum_{v \in \Gamma_{u}} \frac{w_{u v}}{d_{u}} p_{v}$pu​=v∈Γu​∑​du​wuv​​pv​
根据上面这个线性方程，设计一个计算每个节点badness score的迭代算法：

1. 设置节点 u 的初始badness score $p_{u}^{(0)}=0$pu(0)​=0
2. 经过 t 次迭代后，节点 u 的badness score为$p_{u}^{(t)}$pu(t)​
3. 当两次迭代得到的badness score值小于某个阈值时候，就停止迭代
   $p_{u}^{(t)}=\sum_{v \in \Gamma_{u}} \frac{w_{u v}}{d_{u}} p_{v}^{(t-1)}$pu(t)​=v∈Γu​∑​du​wuv​​pv(t−1)​