SybilFuse:Combining Local Attributes with Global Structure to Perform Robust Sybil Detect(论文笔记)
SybilFuse:Combining Local Attributes withGlobal Structure to Perform Robust Sybil Detection
1. 输入数据
2. 训练局部分类器
利用有区别的局部属性(结构或内容)来训练局部分类器。
2.1 局部节点分类器(Local node classifier )
局部节点分类器预测每个节点的信任分数(Trust Score),该分数表示该节点为正常节点的概率,这个值越大,表明该节点越是正常。
2.2 局部边分类器(Local edge classifier )
通常认为,尽管攻击者可以任意控制恶意账户之间的连接,但是攻击者很难操作正常用户和恶意账户之间的连接,因为这需要正常用户的操作。因此,正常用户与恶意账户之间存在structural gap,我们称连接二者的边为attack edges。
局部边分类器预测每条边的信任分数,该分数表示该边是非攻击边(non-attack edge)的概率,这个值越大表明这条边越是正常,即我们认为这条边的权重越大。
2.3 传播信任评分
得到每个节点的信任评分,我们通过global structure传播节点的信任评分,传播过程中经历哪条边,根据边上的权重而定,这个权重即是每条边的信任得分。
信任分数以何种方式传播呢? 可以是带权重的随机游走(Weighted random walk),也可以是带权重的置信传播(Weighted loopy belief propagation)。
3. 局部信任分数的计算
已知一个social graph
,用 表示一个节点的信任评分;
,用 表示两个节点拥有相同标签的概率;(两个节点类型相同,成为这两个节点具有同质性,homophily strength)。
怎样计算 ?
利用节点的局部属性,例如,度、局部聚类系数、用户信息等,训练机器学习分类器(例如,SVM、logistic回归等)输出概率值。
怎样计算 ?
同样地,为了衡量节点u和节点v的相似度,构建一个边分类器,有不同的similarity function可供选择,例如,Cosine, Jaccard, AdamicAdar。
4. 信任分数的传播
4.1 带权重的随机游走(Weighted random walk)
表示节点 在经过 次迭后到达另外一节点,当前这一节点的信任评分。
初始,
对于训练集中的节点,正常节点我们给它 0.9 的评分,恶意节点我们给它 0.1 的评分。
你将把更多的第i轮信任分配给结构上更相近的节点 (即你的朋友)。而不是一个陌生的连接 。这样一来,信任分数低的攻击边对传播的影响就会降低。
经过 次幂迭代步骤(其中n为节点数),得到最终得分
4.2 带权重的置信传播(Weighted loopy belief propagation)
5. 恶意账户预测和排序
5.1 节点的标签预测
对于节点 ,我们通过比较其最终得分S_v^F与阈值,预测它的标签,是正常的还是恶意的。
是正常节点的标签,是恶意节点的标签。
对训练数据进行交叉验证,可以得到阈值。
5.2 节点排名
我们还可以通过对所有节点按其最终得分的升序排列来显示Sybil帐户,分数低的将被排在前面,然后,安全分析师可以查看列表并手动清理Sybil帐户。