✓ 文件回写 ✓ 属性回写 ✓ 直接返回 ✓ 流式返回 ✕ 统计值

概述

SybilRank（西比尔排名）是一种通过提前终止的随机游走对网络中节点的可信度进行排名的算法，主要应用于在线社交网络（Online Social Network, OSN）。OSN 的普及伴随着越来越多的 Sybil 攻击，恶意攻击者会创建多个虚假帐户（Sybils），目的是发送垃圾邮件、分发恶意软件、操纵投票或内容浏览量等。

SybilRank 算法是由 Qiang Cao 等人于 2012 年提出的，它具有良好的计算性价比和大图可扩展性（可并行），能帮助社交平台或相关企业更高效地定位虚假账号。

• Q. Cao, M. Sirivianos, X. Yang, T. Pregueiro, Aiding the Detection of Fake Accounts in Large Scale Social Online Services (2012)

基本概念

威胁模型与可信节点

SybilRank 将 OSN 视为无向图，其中每个节点对应网络中的一个用户，每条边对应双边的社交关系。

在 SybilRank 的威胁模型（Threat Model）中，所有节点被划入两个不相交的集合：Non-Sybil（真实账号）集合 H 和 Sybil（虚假账号）集合 S；集合 H 以及所有 Non-Sybil 节点间的边构成 Non-Sybil 区域 G_H，集合 S 以及所有 Sybil 节点间的边构成 Sybil 区域 G_S。G_H 和 G_S 之间由攻击边（Attack Edges）相连。

指定若干认为是 Non-Sybil 的节点作为 SybilRank 运行的信任种子（Trust Seeds）。选择多个可信节点使得 SybilRank 对种子选择的错误具有鲁棒性，因为如果错误地将 Sybil 节点或接近 Sybil 的节点指定为种子，只会导致仅一小部分的可信度在 Sybil 区域中初始化和传播。

下面是一个带有信任种子的威胁模型示例：

SybilRank 的一个重要假设是攻击边数量有限。由于 SybilRank 是为大规模攻击而设计的，其中虚假帐户大都以低成本制作和维护，因此无法与许多真实用户建立社交联系。这导致 G_H 和 G_S 之间的稀疏切割。

提前终止的随机游走

在无向图中，如果随机游走以相同的概率访问每个邻居节点，当步数足够时，最后着陆到每个节点的概率会收敛到与其度数成正比。随机游走达到平稳分布所需的步数称为图的混合时间（Mixing Time）。

SybilRank 依赖于这样的观察，即从非 Sybil 节点（信任种子）开始的提前终止的随机游走（Early-Terminated Random Walk）会以更高的概率着陆到非 Sybil 节点，因为游走不太可能经过相对较少的攻击边。也就是说，非 Sybil 区域 G_H 和整个图的混合时间存在明显差异。

SybilRank 将每个节点的着陆概率（Landing Probability）称为该节点的可信度（Trust）。SybilRank 根据节点的可信度对节点进行排名，可信度分值越低的节点排名越高，是 Sybil 的可能性越大。

可信度传播：幂迭代

SybilRank 使用幂迭代（Power Iteration）来更有效率地计算大图中随机游走的着陆概率。幂迭代涉及连续矩阵乘法，其中矩阵的每个元素表示从一个节点到邻居节点的随机游走转移概率。每次迭代相当于计算增加一步随机游走后所有节点的着陆概率分布。

在无向图 G = (V, E) 中，先将设置的总可信度 T_G 均匀分配给所有的信任种子。在每次的幂迭代中，节点首先将自身的可信度均匀分配给所有邻居；然后，它收集所有邻居分发给自己的可信度，并相应地更新自身的可信度。节点 v 在第 i 次迭代中的可信度为：

其中节点 u 属于节点 v 的邻居集合，deg(u) 是节点 u 的度，全图的总可信度 T_G 始终保持不变。

如果进行足够的幂迭代，所有节点的可信度将收敛到平稳分布：

然而，SybilRank 在收敛前就会提前终止迭代，建议的迭代次数为 log(|V|)。此迭代次数足够混合 Non-Sybil 区域 G_H，使其达到近似平稳的可信度分布，但限制可信度传播到 Sybil 区域 G_S，因此 Non-Sybil 的排名将高于 Sybil。

在实践中，G_H 的混合时间受多种因素影响，因此 log(|V|) 只是一个参考，但它必须小于整个图的混合时间。

特殊说明

• 每条自环边会被视为节点的两条边。
• SybilRank 算法忽略边的方向，按照无向边进行计算。
• SybilRank 的计算复杂度是 O(n log n)，因为每次幂迭代的复杂度为 O(n)，它迭代 O(log n) 次。计算复杂度与信任种子的数量无关。

语法

• 命令：algo(sybil_rank)
• 参数：

示例

示例图如下：

文件回写

algo(sybil_rank).params({
  total_trust: 100,
  trust_seeds: [2,3,5],
  loop_num: 4
}).write({
  file:{
    filename: 'sybilRank'
  }
})

结果：文件 sybilRank

S1,0
S4,3.61111
S2,4.45602
S3,4.71065
H9,5.0434
H8,5.09259
H4,6.66667
H10,7.87037
H5,8.67766
H1,9.59491
H2,9.9537
H7,10.4167
H3,11.305
H6,12.6013

属性回写

algo(sybil_rank).params({
  total_trust: 100,
  trust_seeds: [2,3,5],
  loop_num: 4
}).write({
  db:{
    property: 'trust'
  }
})

结果：每个节点的可信度回写至名为 trust 的点属性下

直接返回

algo(sybil_rank).params({
  total_trust: 100,
  trust_seeds: [2,3,5],
  loop_num: 4
}) as trust 
return trust

结果：trust

流式返回

algo(sybil_rank).params({
  total_trust: 100,
  trust_seeds: [2,3,5],
  loop_num: 4,
  limit: 4
}).stream() as trust
find().nodes({_uuid == trust._uuid}) as nodes
return table(nodes._id, trust.rank)

结果：table(nodes._id, trust.rank)