概述
SybilRank(西比尔排名,或西比尔识别),是一种通过幂迭代的短途随机游走对多社区网络中的节点进行可信度排名的算法。Sybil 原指在线社交网络(OSN)中的虚假账号,随着社交网络的飞速发展,来自 Sybil 的攻击和滥用日益增多,例如向其他账号发送垃圾信息,恶意增加广告或网页链接的点击次数,爬取私人账户信息来充当水军或实施网络暴力等。
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 算法中的可信节点(Trust Seeds)是指由用户指定的多个可信赖的节点(认定为真实账号)。
威胁模型
SybilRank 规定,图中每个参与计算的节点必须代表社交帐号,每个参与计算的边(忽略方向)必须代表某两个账号之间的关系。SybilRank 将这些社交账号划分为由真实账号(non-Sybil)和虚假账号(Sybil)构成的两个集合,分别记作 H
和 S
;将 H
和 S
之间的边视为由 Sybil 向 non-Sybil 发起的攻击,并且这些攻击边(Attack Edges)的数量应远远少于 non-Sybil 之间的边的数量。以上就是 SybilRank 的威胁模型(Threat Model)。
注意,由图中所有真实账号构成的集合 H
以及它们之间的边构成的子图 G(H)
不能是二分图,目的是使 SybilRank 中的随机游走在各个可信节点上着陆(止步)的概率与节点度成正比。
下图是威胁模型的一个示例:
着陆概率 / 可信度
SybilRank 使用的随机游走是一种提前终止的幂迭代计算(Early-Terminated Power Iteration)。由于 H
和 S
间的攻击边的数量有限,出发于可信节点的随机游走在全图稳定之前更大概率会走到 non-Sybil 上,这个概率称为着陆概率(Landing Probability),或者理解为节点的可信度(Node's Trust)。对每个节点的可信度进行排名,可信度越低的节点是 Sybil 的可能性越大。
算法初始化时,用户需要指定一个全图可信度总分(Total Trust),该值首先在各个可信节点之间平均分配,并在每次迭代时沿着分值所在节点的各条边(忽略方向)平均分配给节点的各个邻居。全图可信度总分始终保持不变,每一轮迭代后节点 i
的可信度分值为:
其中,j
为节点 i
的任意一个邻居,i
的邻居个数等于 i
的节点度,即每条自环边代表两个邻居;D(j)
为 j
的节点度。
原始论文中,算法在最终排名之前对每个节点的可信度做了归一化处理(Degree-Normalization),即用分值除以节点度。Ultipa 的 SybilRank 算法对此进行了简化,直接使用迭代后得到的可信度分值作为排名的依据。
算法开始时,根据算法的参数设置给所有可信点分配初始分值;在每轮迭代中,为每个节点计算其将要获得的分值并进行更新。按此规则循环迭代,直至迭代轮数达到限制。
混合时间
同样是采用幂迭代计算来传递分值,PageRank 的目的是让有向图全图区域的分值分布达到稳定,而 SybilRank 的目的是让无向图的 G(H)
区域的分值分布达到稳定。后者所需的游走步数,也称混合时间(Mixing Time),就是所需的迭代次数,通常取以 2 为底的对数 log(点数量)
(向上取整)。在实际应用中,G(H)
区域的混合时间受很多因素影响,因此 log(点数量)
只是一种参考,但其必定小于全图的混合时间,这就是该迭代的特性——提前终止。
特殊处理
孤点、不连通图
由于没有连接其他节点的边,未被指定为可信节点时,孤点的可信度为 0;被指定为可信节点时,孤点的可信度等于全图可信度除以可信节点的个数。
不连通图的各个连通分量之间没有分值传递。
自环边
自环边会被看作一条出边和一条入边,即每条自环边会被视为节点的两条边。
有向边
对于有向边,本算法会忽略边的方向,按照无向边进行计算。
结果和统计值
以下面的社交网络图为例,绿色节点为 non-Sybil,红色节点为 Sybil,运行 SybilRank 算法,指定 [H1,H2,H3] 为可信节点,可信度总分为 100,迭代 log14
= 3.8074
≈ 4
次:
算法结果:为每个点计算可信度,根据算法执行方式,返回 _id
、rank
两列或 _uuid
、rank
两列
_uuid | _id | rank |
---|---|---|
11 | S1 | 0.0000000 |
8 | H8 | 0.0000000 |
9 | H9 | 3.7355320 |
12 | S2 | 3.8078699 |
13 | S3 | 4.0046301 |
14 | S4 | 6.1284719 |
4 | H4 | 6.8836799 |
5 | H5 | 7.6562500 |
7 | H7 | 10.416666 |
10 | H10 | 10.416666 |
3 | H3 | 10.691550 |
1 | H1 | 11.114004 |
2 | H2 | 12.500000 |
6 | H6 | 12.644675 |
算法统计值:无
命令和参数配置
- 命令:
algo(sybil_rank)
params()
参数配置项如下:
名称 |
类型 |
默认值 |
规范 |
描述 |
---|---|---|---|---|
total_trust | float | / | > 0 | 全图可信度总分,初始时平均分配给各个可信节点 |
trust_seeds | []_uuid |
/ | / | 可信节点的 UUID 列表,建议为各个社区均设置可信节点;忽略表示指定全部节点 |
loop_num | int | 5 | > 0 | 算法迭代轮数,可参考以 2 为底数的 log(点总数) ,向上取整 |
limit | int | -1 | >=-1 | 需要返回的结果条数,-1 或忽略表示返回所有结果 |
示例:运行 SybilRank 算法,指定 UUID = 1,2,3 为可信节点,可信度总分为 100,迭代 4 次
algo(sybil_rank).params({
total_trust: 100,
trust_seeds: [1,2,3],
loop_num: 4
}) as rank return rank
算法执行
任务回写
1. 文件回写
配置项 | 各列数据 |
---|---|
filename | _id ,rank |
示例:运行 SybilRank 算法,指定 UUID = 1,2,3 为可信节点,可信度总分为 100,迭代 4 次,将算法结果回写至名为 sybilRank 的文件
algo(sybil_rank).params({
total_trust: 100,
trust_seeds: [1,2,3],
loop_num: 4
}).write({
file:{
filename: "sybilRank"
}
})
2. 属性回写
配置项 | 回写内容 | 类型 | 数据类型 |
---|---|---|---|
property | rank |
点属性 | float |
示例:运行 SybilRank 算法,指定 UUID = 1,2,3 为可信节点,可信度总分为 100,迭代 4 次,将算法结果回写至名为 trust 的点属性
algo(sybil_rank).params({
total_trust: 100,
trust_seeds: [1,2,3],
loop_num: 4
}).write({
db:{
property: "trust"
}
})
3. 统计回写
算法无统计值。
直接返回
别名序号 | 类型 | 描述 | 列名 |
---|---|---|---|
0 | []perNode | 点及其可信度 | _uuid , rank |
示例:运行 SybilRank 算法,指定 UUID = 1,2,3 为可信节点,可信度总分为 100,迭代 4 次,将算法结果定义为别名 rank 并返回
algo(sybil_rank).params({
total_trust: 100,
trust_seeds: [1,2,3],
loop_num: 4
}) as rank return rank
流式返回
别名序号 | 类型 | 描述 | 列名 |
---|---|---|---|
0 | []perNode | 点及其可信度 | _uuid , rank |
示例:运行 SybilRank 算法,指定 UUID = 1,2,3 为可信节点,可信度总分为 100,迭代 4 次,返回最可疑的 4 个点的 name 属性和可信度分值
algo(sybil_rank).params({
total_trust: 100,
trust_seeds: [1,2,3],
loop_num: 4,
order: "asc",
limit: 10
}).stream() as results
find().nodes({_uuid == results._uuid}) as nodes
return table(nodes.name, results.rank)
实时统计
算法无统计值。
算法效率
SybilRank 算法的计算复杂度为 O(n log n)
,该复杂度与可信节点数量无关。