论文部分内容阅读
近年来,随着在线社交网络规模的不断发展,攻击者们为了牟取利益通过虚假账户进行恶意攻击行为,包括传播垃圾信息,窃取用户隐私等,极大的威胁了社交网络用户的安全,阻碍了社交网络的发展。因此,社交网络虚假账户的检测成为了网络安全及信息安全的关键研究性问题之一。目前,关于虚假账户检测的方法有很多,包括基于用户行为特征,基于用户信息内容以及基于社交网络图结构等三大类检测方法。其中,基于图结构的检测方法有着检测效率高,攻击者不能轻易模拟去躲避检测,特征抓取简单等优点。但是随着社交网络规模的不断扩大,现有的复杂的检测算法很难扩展并应用到实际的大规模的社交网络检测中。并且,传统的大规模处理框架,如Map Reduce,很难去处理非结构化的图结构数据,因此,一些工作,开始使用Pregel/Giraph等,一类以点为中心的图计算系统,来实现检测大规模社交网络。但是目前的图计算系统的设计都是过度通用化的,即它们都是被设计出来处理通用图的,而不是针对具有特征的社交网络图,因此现有的系统在处理社交网络图时性能不佳。本文通过对社交网络图数据的研究,提出了一种针对社交网络图特征优化的以点为中心的单机图计算系统框架,并且分析现有的检测算法,在我们的系统实现了2种不同类别的基于图结构的虚假账户检测算法。具体工作如下:1.在系统层面,我们对目前的社交网络图进行分析,考虑到目前社交网络以及单机服务器的配置,参考利用核外计算技术来提高计算扩展性的单机图计算系统来设计检测系统框架。2.在数据层面,考虑到社交网络图的幂率分布,将图按照顶点度数分成2个不相交集合,称为重集合和轻集合,对轻重集合使用不同的存储格式,执行模式,选择性调度策略以及缓存策略来优化图系统。3.在算法层面,分析了目前现有的基于图结构的虚假账户检测算法,将其中涉及的图算法归为两类,一类是基于随机游走的幂迭代算法,如Sybil Rank;一类是基于社区发现的遍历型算法,如COLOR/COLOR+,本文提出d Sybil Rank和d COLOR算法,即将两类算法转化为以点为中心的并行迭代式图算法,来提高原有检测算法的效率。4.最后,我们在我们系统上测试了以上两类社交网络检测算法的性能。实验结果显示,我们的系统展现了很好的性能,比如,我们在单机服务器上处理5千万顶点的网络需要459秒,相比于Sybil Rank处理1.6亿顶点数据需要11台m1.large集群同时处理33小时表现的很优秀。同时,我们也将我们的系统与现有的图计算系统相比较,其性能在社交网络图上提高到1.14~5.91倍。