修改密码

请输入密码
请输入密码 请输入8-64长度密码 和 email 地址不相同 至少包括数字、大写字母、小写字母、半角符号中的 3 个
请输入密码
提交

修改昵称

当前昵称:
提交

申请证书

证书详情

Please complete this required field.

  • Ultipa Graph V4

Standalone

Please complete this required field.

Please complete this required field.

服务器的MAC地址

Please complete this required field.

Please complete this required field.

取消
申请
ID
产品
状态
核数
申请天数
审批时间
过期时间
MAC地址
申请理由
审核信息
关闭
基础信息
  • 用户昵称:
  • 手机号:
  • 公司名称:
  • 公司邮箱:
  • 地区:
  • 语言:
修改密码
申请证书

当前未申请证书.

申请证书
Certificate Issued at Valid until Serial No. File
Serial No. Valid until File

Not having one? Apply now! >>>

ProductName CreateTime ID Price File
ProductName CreateTime ID Price File

No Invoice

搜索
    中文

      SybilRank

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

      概述

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

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

      基本概念

      威胁模型与可信节点

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

      在 SybilRank 的威胁模型(Threat Model)中,所有节点被划入两个不相交的集合:Non-Sybil(真实账号)集合 H 和 Sybil(虚假账号)集合 S;集合 H 以及所有 Non-Sybil 节点间的边构成 Non-Sybil 区域 GH,集合 S 以及所有 Sybil 节点间的边构成 Sybil 区域 GS。GH 和 GS 之间由攻击边(Attack Edges)相连。

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

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

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

      提前终止的随机游走

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

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

      SybilRank 将每个节点的着陆概率(Landing Probability)称为该节点的可信度(Trust)。SybilRank 根据节点的可信度对节点进行排名,可信度越低的节点是 Sybil 的可能性越大。

      可信度传播:幂迭代

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

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

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

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

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

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

      特殊说明

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

      语法

      • 命令:algo(sybil_rank)
      • 参数:
      名称
      类型
      规范
      默认
      可选
      描述
      total_trust float >0 / 全图可信度总分
      trust_seeds []_uuid / / 信任种子的 UUID 列表,建议在各个社区均挑选信任种子,忽略则指定所有节点为信任种子
      loop_num int >0 5 算法迭代轮数,建议设置为 log(|V|)(以 2 为底)
      limit int >=-1 -1 返回的结果条数,-1 返回所有结果

      示例

      示例图如下:

      文件回写

      配置项 回写内容
      filename _id,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
      

      属性回写

      配置项 回写内容 回写至 数据类型
      property rank 点属性 float
      algo(sybil_rank).params({
        total_trust: 100,
        trust_seeds: [2,3,5],
        loop_num: 4
      }).write({
        db:{
          property: "trust"
        }
      })
      

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

      直接返回

      别名序号 类型 描述 列名
      0 []perNode 点及其可信度 _uuid, rank
      algo(sybil_rank).params({
        total_trust: 100,
        trust_seeds: [2,3,5],
        loop_num: 4
      }) as trust 
      return trust
      

      结果:trust

      _uuid rank
      11 0.0000000
      14 3.6111109
      12 4.4560180
      13 4.7106481
      9 5.0434031
      8 5.0925918
      4 6.6666660
      10 7.8703699
      5 8.6776609
      1 9.5949059
      2 9.9537029
      7 10.416666
      3 11.304976
      6 12.601272

      流式返回

      别名序号 类型 描述 列名
      0 []perNode 点及其可信度 _uuid, rank
      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)

      nodes._id trust.rank
      S1 0.0000000
      S4 3.6111109
      S2 4.4560180
      S3 4.7106481
      请完成以下信息后可下载此书
      *
      公司名称不能为空
      *
      公司邮箱必须填写
      *
      你的名字必须填写
      *
      你的电话必须填写
      *
      你的电话必须填写