论文部分内容阅读
摘 要：在线社交网络的sybil账户日益猖獗，网络攻击者利用欺诈账户进行各种恶意活动，严重影响了社交网络的正常秩序，危害了网络用户的个人隐私。现提出一种基于有向图的欺诈用户检测方法。该方法优化了已有的GANG算法。通过基于全局社会结构，建立新的马尔科夫随机场，并优化置信传播以优化检测精度。实验结果表明，优化后的GANG算法已有的算法更具有可扩展性和收敛性，且比基于无向图的检测方法精确度更高。
关键词：有向图；社交网络；关联推定
1 引 言
近几年，在线社交网络发展迅速，如我国的微信、微博、QQ等，国外的 Facebook、Twitter 等。社交网络为人们提供了一个方便的、用来交流和分享的最佳平台，也因此受到利益的驱动，社交网站也吸引了很多网络攻击者。通过制造大量非法虚假身份，网络攻击者会制造各种恶意活动，如发布“三无”信息、发送虚假邮件，收集个人信息等影响网络中社交个体中继选择意愿，窃取社交个体隐私，严重威胁了社交网络和用户的安全。
网络攻击者账户有较为明显的特征：通过前期大范围的发送请求消息，以求通过此举添加大量的合法网络用户为好友，为后续进行恶意网络攻击奠定基础。加之移动互联网时代的到来，网络的适用性越来越广泛，社交网络欺诈造成的恶劣影响也显著增加。
为此，计算机界对应对网络欺诈用户检测提出了許多方案，这些方案一般都是基于一定的假设才能达到较好的效果，并且在实际应用中这些方案准确率较低，网络欺诈者较容易躲避。针对此种情况，本文优化了GANG方法，进而有效改善现有方案中的准确率低，易躲避的情况。
2 相关工作和背景
已有的检测方法中，有的利用无向的社交链接，这过度简化了现实世界在线社交网络的定向社交结构，大大限制了检测的准确度。在这项工作中，我们提出GANG，一种关于有向图的关联推定方法，用于检测在线社交网络中的欺诈用户。在GANG中，我们设计一个新的成对马尔可夫随机场来模拟有向社会图中节点的联合概率分布。该新型马尔科夫随机场具有欺诈用户检测问题的独特特性。如果反向的边（v，u） 不存在，我们称之为单向边（u，v） ，否则我们称之为双向边。如果两个用户通过双向边链接并且具有相同的标签，那么马尔可夫随机场会产生更大的联合概率。 但是，假设u 和v 通过单向边缘（u，v） 链接，例如，在Twitter上，u 跟随v ，但v 不跟随u 。如果u 是欺诈的或v 是正常的，那么单向边 是否存在不会影响马尔可夫随机场下的联合概率，否则边（u，v） 会使联合概率变大。这是因为欺诈用户可以跟随任意用户而不会被追踪，而普通用户可以被任意用户追踪而不会追踪他们。
在GANG的基本版本中，我们使用置信传播（LBP）来估计给定实验数据集中每个二元随机变量的后验概率分布，并用它来预测相应用户的标签。然而，基本版本有两个缺点：1.它不够可扩展，因为LBP需要在每个边缘上维护消息，2.它不能保证收敛，因为LBP可能在循环图上振荡。因此，我们进一步优化GANG以解决这些缺点。我们的优化包括消除消息维护和通过简洁的矩阵形式逼近GANG，我们还得出了优化GANG收敛的条件。
我们引入了一个新的成对马尔可夫随机场，马尔可夫随机场模拟所有u∈V 的所有二元随机变量xu 的联合概率分布。我们用xv 表示所有二进制随机变量的集合。我们提出的马尔科夫随机场如下：
其中H（xv） 称为能量函数。（u，v） 或（v，u） 出现在H（xv） 中，但两者不会同时出现。
使用置信传播（LBP）计算后验概率分布：
在GANG的基本版本中，我们使用LBP来估计后验概率分布Pr（xv） 。 LBP在图中的相邻节点之间迭代地传递消息。即在第t次迭代中从v发送到u 的消息 是 ：
其中Γ（v）/u 是接收节点u 之外的v 的所有邻居的集合。该编码中每个节点通过最后一次迭代的传入消息转发结果，并基于与接收方的同质性强度将该消息适配到相应的接收方。当消息的变化在两次连续迭代中变得可忽略时LBP停止，或者它达到预定义的最大迭代次数T。LBP停止后，我们估计后验信念Pr（xv） 如下：
这相当于
消除消息维护
GANG不够可扩展的主要原因之一是LBP在每个边都维护消息。 我们观察到LBP需要在边上维护信息的关键原因是当节点v 向其邻居u 准备消息时，它需要排除u 发送给v 的消息。因此，我们的第一个优化步骤是当v 准备其消息给u 时包括u 发送给v 的消息 .形式上，我们修改公式（3）如下：
3 结构模型
假设给出了一个有向社交图G（V，E） ，其中节点v∈V 代表用户，是用户的数┃V┃ 量，有向边（u，v）∈E 表示u 和v 之间的某种关系。例如，这种关系可能是u 在Twitter上跟随v ，在Facebook上u 向v 发送朋友请求， 或者u 在Facebook上接受来自v 的朋友请求。每个节点可以是欺诈性的或正常的。欺诈性节点包括垃圾邮件发送者，虚假用户和受损用户。
定义（基于有向图的欺诈检测）：假设我们被给予一个有向社交图和一个由标记的欺诈和正常节点组成的训练数据集。欺诈检测目的是预测社交图中每个剩余节点的标签。
符号：如果边（v，u） 不存在，我们将边（u，v） 称为单向。我们用图中的E1 单向边表示，例如， 。 如果边（v，u） 也存在，我们称之为边（u，v） 双向。我们用图中的E2 双向边表示，即
4 实验评估与结果分析
首先，我们获得了一个Twitter的跟随者与被跟随者图表，其中包含41，652，230个用户和来自Kwak等人的1，468，364，884个边[4]。有205，355名用户被Twitter暂停，我们将其视为欺诈用户； 36，156，909个用户活跃，将其视为普通用户； 其余5，289，966个用户被删除，将它们视为未标记的用户。随机抽取500，000个标记用户作为实验集，并将剩余的标记用户视为测试集。 其次，我们从Fu等人的[5]中获得了一个包含3538，487个用户和652，889，971条有向边的新浪微博数据集。手工标记了随机抽样的2000名用户。其中，欺诈用户482名，正常用户1498名，未知用户20名。我们将欺诈用户和普通用户分成两部分；一个作为实验集，另一个作为测试集。表1显示了我们数据集的一些统计数据。
表1 数据集统计
数据集 Twitter Sina Weibo
节点 4165230 3538487
边 1468364884 652889971
平均度 71 369
我们将优化后的GANG算法与其他方法进行比较。
我们考虑以下基于有向图的方法：TrustRank、DistrustRank、CIA和CatchSync。TrustRank、DistrustRank和CIA都是基于随机游走，而CatchSync会利用[3]进行测试。TrustRank和DistrustRank最初是为了检测基于超链接的欺诈网页而设计的，但它们可以用于检测在线社交网络中的欺诈用户。TrustRank仅利用实验数据集中标记的正常节点；DistrustRank和CIA本质上是一样的，他们只利用标记为欺诈的节点；而CatchSync不使用实验数据集。
表2 有向图的各种方法AUC值的比较
方法 Twitter Sina Weibo
TrustRank 0.60 0.66
DistrustRank 0.63 0.64
CIA 0.63 0.64
CatchSync 0.68 0.51
GANG 0.72 0.80
整体排名表现：我们首先使用AUC来衡量比较方法的整体排名表现。AUC可以解释为在测试数据集中，一个随机抽样的欺诈节点排名高于一个随机抽样的正常节点的概率。AUC越高，性能越好。表2显示了Twitter和新浪微博数据集上所有比较方法的AUC。我们观察到GANG在两个数据集上始终优于所有的比较方法。
5 总 结
为了防范社交网络中越来越多的欺诈用户的攻击，和随之带来的越来越恶劣的影响，本文设计的基于有向图的社交网络欺诈用户检测方法可以起到较好的作用——较高的识别率。此方法通过有向图的关联推定来检测社交网络中的欺诈用户。在GANG中，我们设计了一个新的成对马尔可夫随机场来模拟有向社会图中节点的联合概率分布。该新型马尔科夫随机场具有欺诈用户检测问题的独特特性。
在实验结果的评估上，通过对比其他算法，结果显示在检测社交网络欺诈用户的识别率和准确性上，本文提出的优化算法检测效率最高，而其他四种算法为目前使用较为普遍的检测算法。因此，本文提出的优化算法可以更加有效的检测出社交网络中的欺诈用户，减少社交网络欺诈用户对社交网络和正常用户造成的危害和恶劣影响。
参考文献：
[1] 吴大鹏，司书山，闫俊杰，王汝言.基于行为特征分析的社交网络女巫节点检测机制[A].电子与信息学报，2017，39（9）.
[2] 周清清，陈志刚，黄 瑞，李 博，徐成林.在线社交网络Sybil账号检测[A].小型微型计算机系统，2017，（8）.
[3] J. Kleinberg， “Authoritative sources in a hyperlinked environment，”Journal of the ACM， vol. 46， no. 5， 1999.
[4] H. Kwak， C. Lee， H. Park， and S. Moon， “What is twitter， a social
network or a news media？” in WWW， 2010.
[5] H. Fu， X. Xie， Y. Rui， N. Z. Gong， G. Sun， and E. Chen， “Robust
spammer detection in microblogs： Leveraging user carefulness，” ACM
Transactions on Intelligent Systems and Technology （TIST）， 2017.
作者簡介：
吴彦芳，生于1996年12月，女，汉族，河南民权人，南京邮电大学本科在读，物联网工程专业.
*【基金项目】本文系南京邮电大学2018年度大学生实践创新训练计划项目，项目编号XYB2018284
关键词：有向图；社交网络；关联推定
1 引 言
近几年，在线社交网络发展迅速，如我国的微信、微博、QQ等，国外的 Facebook、Twitter 等。社交网络为人们提供了一个方便的、用来交流和分享的最佳平台，也因此受到利益的驱动，社交网站也吸引了很多网络攻击者。通过制造大量非法虚假身份，网络攻击者会制造各种恶意活动，如发布“三无”信息、发送虚假邮件，收集个人信息等影响网络中社交个体中继选择意愿，窃取社交个体隐私，严重威胁了社交网络和用户的安全。
网络攻击者账户有较为明显的特征：通过前期大范围的发送请求消息，以求通过此举添加大量的合法网络用户为好友，为后续进行恶意网络攻击奠定基础。加之移动互联网时代的到来，网络的适用性越来越广泛，社交网络欺诈造成的恶劣影响也显著增加。
为此，计算机界对应对网络欺诈用户检测提出了許多方案，这些方案一般都是基于一定的假设才能达到较好的效果，并且在实际应用中这些方案准确率较低，网络欺诈者较容易躲避。针对此种情况，本文优化了GANG方法，进而有效改善现有方案中的准确率低，易躲避的情况。
2 相关工作和背景
已有的检测方法中，有的利用无向的社交链接，这过度简化了现实世界在线社交网络的定向社交结构，大大限制了检测的准确度。在这项工作中，我们提出GANG，一种关于有向图的关联推定方法，用于检测在线社交网络中的欺诈用户。在GANG中，我们设计一个新的成对马尔可夫随机场来模拟有向社会图中节点的联合概率分布。该新型马尔科夫随机场具有欺诈用户检测问题的独特特性。如果反向的边（v，u） 不存在，我们称之为单向边（u，v） ，否则我们称之为双向边。如果两个用户通过双向边链接并且具有相同的标签，那么马尔可夫随机场会产生更大的联合概率。 但是，假设u 和v 通过单向边缘（u，v） 链接，例如，在Twitter上，u 跟随v ，但v 不跟随u 。如果u 是欺诈的或v 是正常的，那么单向边 是否存在不会影响马尔可夫随机场下的联合概率，否则边（u，v） 会使联合概率变大。这是因为欺诈用户可以跟随任意用户而不会被追踪，而普通用户可以被任意用户追踪而不会追踪他们。
在GANG的基本版本中，我们使用置信传播（LBP）来估计给定实验数据集中每个二元随机变量的后验概率分布，并用它来预测相应用户的标签。然而，基本版本有两个缺点：1.它不够可扩展，因为LBP需要在每个边缘上维护消息，2.它不能保证收敛，因为LBP可能在循环图上振荡。因此，我们进一步优化GANG以解决这些缺点。我们的优化包括消除消息维护和通过简洁的矩阵形式逼近GANG，我们还得出了优化GANG收敛的条件。
我们引入了一个新的成对马尔可夫随机场，马尔可夫随机场模拟所有u∈V 的所有二元随机变量xu 的联合概率分布。我们用xv 表示所有二进制随机变量的集合。我们提出的马尔科夫随机场如下：
其中H（xv） 称为能量函数。（u，v） 或（v，u） 出现在H（xv） 中，但两者不会同时出现。
使用置信传播（LBP）计算后验概率分布：
在GANG的基本版本中，我们使用LBP来估计后验概率分布Pr（xv） 。 LBP在图中的相邻节点之间迭代地传递消息。即在第t次迭代中从v发送到u 的消息 是 ：
其中Γ（v）/u 是接收节点u 之外的v 的所有邻居的集合。该编码中每个节点通过最后一次迭代的传入消息转发结果，并基于与接收方的同质性强度将该消息适配到相应的接收方。当消息的变化在两次连续迭代中变得可忽略时LBP停止，或者它达到预定义的最大迭代次数T。LBP停止后，我们估计后验信念Pr（xv） 如下：
这相当于
消除消息维护
GANG不够可扩展的主要原因之一是LBP在每个边都维护消息。 我们观察到LBP需要在边上维护信息的关键原因是当节点v 向其邻居u 准备消息时，它需要排除u 发送给v 的消息。因此，我们的第一个优化步骤是当v 准备其消息给u 时包括u 发送给v 的消息 .形式上，我们修改公式（3）如下：
3 结构模型
假设给出了一个有向社交图G（V，E） ，其中节点v∈V 代表用户，是用户的数┃V┃ 量，有向边（u，v）∈E 表示u 和v 之间的某种关系。例如，这种关系可能是u 在Twitter上跟随v ，在Facebook上u 向v 发送朋友请求， 或者u 在Facebook上接受来自v 的朋友请求。每个节点可以是欺诈性的或正常的。欺诈性节点包括垃圾邮件发送者，虚假用户和受损用户。
定义（基于有向图的欺诈检测）：假设我们被给予一个有向社交图和一个由标记的欺诈和正常节点组成的训练数据集。欺诈检测目的是预测社交图中每个剩余节点的标签。
符号：如果边（v，u） 不存在，我们将边（u，v） 称为单向。我们用图中的E1 单向边表示，例如， 。 如果边（v，u） 也存在，我们称之为边（u，v） 双向。我们用图中的E2 双向边表示，即
4 实验评估与结果分析
首先，我们获得了一个Twitter的跟随者与被跟随者图表，其中包含41，652，230个用户和来自Kwak等人的1，468，364，884个边[4]。有205，355名用户被Twitter暂停，我们将其视为欺诈用户； 36，156，909个用户活跃，将其视为普通用户； 其余5，289，966个用户被删除，将它们视为未标记的用户。随机抽取500，000个标记用户作为实验集，并将剩余的标记用户视为测试集。 其次，我们从Fu等人的[5]中获得了一个包含3538，487个用户和652，889，971条有向边的新浪微博数据集。手工标记了随机抽样的2000名用户。其中，欺诈用户482名，正常用户1498名，未知用户20名。我们将欺诈用户和普通用户分成两部分；一个作为实验集，另一个作为测试集。表1显示了我们数据集的一些统计数据。
表1 数据集统计
数据集 Twitter Sina Weibo
节点 4165230 3538487
边 1468364884 652889971
平均度 71 369
我们将优化后的GANG算法与其他方法进行比较。
我们考虑以下基于有向图的方法：TrustRank、DistrustRank、CIA和CatchSync。TrustRank、DistrustRank和CIA都是基于随机游走，而CatchSync会利用[3]进行测试。TrustRank和DistrustRank最初是为了检测基于超链接的欺诈网页而设计的，但它们可以用于检测在线社交网络中的欺诈用户。TrustRank仅利用实验数据集中标记的正常节点；DistrustRank和CIA本质上是一样的，他们只利用标记为欺诈的节点；而CatchSync不使用实验数据集。
表2 有向图的各种方法AUC值的比较
方法 Twitter Sina Weibo
TrustRank 0.60 0.66
DistrustRank 0.63 0.64
CIA 0.63 0.64
CatchSync 0.68 0.51
GANG 0.72 0.80
整体排名表现：我们首先使用AUC来衡量比较方法的整体排名表现。AUC可以解释为在测试数据集中，一个随机抽样的欺诈节点排名高于一个随机抽样的正常节点的概率。AUC越高，性能越好。表2显示了Twitter和新浪微博数据集上所有比较方法的AUC。我们观察到GANG在两个数据集上始终优于所有的比较方法。
5 总 结
为了防范社交网络中越来越多的欺诈用户的攻击，和随之带来的越来越恶劣的影响，本文设计的基于有向图的社交网络欺诈用户检测方法可以起到较好的作用——较高的识别率。此方法通过有向图的关联推定来检测社交网络中的欺诈用户。在GANG中，我们设计了一个新的成对马尔可夫随机场来模拟有向社会图中节点的联合概率分布。该新型马尔科夫随机场具有欺诈用户检测问题的独特特性。
在实验结果的评估上，通过对比其他算法，结果显示在检测社交网络欺诈用户的识别率和准确性上，本文提出的优化算法检测效率最高，而其他四种算法为目前使用较为普遍的检测算法。因此，本文提出的优化算法可以更加有效的检测出社交网络中的欺诈用户，减少社交网络欺诈用户对社交网络和正常用户造成的危害和恶劣影响。
参考文献：
[1] 吴大鹏，司书山，闫俊杰，王汝言.基于行为特征分析的社交网络女巫节点检测机制[A].电子与信息学报，2017，39（9）.
[2] 周清清，陈志刚，黄 瑞，李 博，徐成林.在线社交网络Sybil账号检测[A].小型微型计算机系统，2017，（8）.
[3] J. Kleinberg， “Authoritative sources in a hyperlinked environment，”Journal of the ACM， vol. 46， no. 5， 1999.
[4] H. Kwak， C. Lee， H. Park， and S. Moon， “What is twitter， a social
network or a news media？” in WWW， 2010.
[5] H. Fu， X. Xie， Y. Rui， N. Z. Gong， G. Sun， and E. Chen， “Robust
spammer detection in microblogs： Leveraging user carefulness，” ACM
Transactions on Intelligent Systems and Technology （TIST）， 2017.
作者簡介：
吴彦芳，生于1996年12月，女，汉族，河南民权人，南京邮电大学本科在读，物联网工程专业.
*【基金项目】本文系南京邮电大学2018年度大学生实践创新训练计划项目，项目编号XYB2018284