修改密码

请输入密码
请输入密码 请输入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

v5.0
搜索
    v5.0

      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
      请完成以下信息后可下载此书
      *
      公司名称不能为空
      *
      公司邮箱必须填写
      *
      你的名字必须填写
      *
      你的电话必须填写
      *
      你的电话必须填写