基于关系强度的社交网络垃圾行为检测算法的研究

申 华，汪若蓝，蒋廷鹏

(1．鞍山师范学院 数学与信息科学学院，辽宁 鞍山114007;2．大连理工大学 软件学院，辽宁 大连116024)

随着互联网的发展以及人类对沟通的需求，社交网络开始影响人们的生活，比如Twitter、新浪微博，已经成为人们日常通讯交流的重要方式．人们期待社交网络是一个安全、可靠的交流平台，不会受到其他用户的威胁．但近期的研究表明，社会网络却恰恰为网络欺骗提供了温床［1］，层出不穷的传播垃圾信息的行为引发了日益严重的社交网络安全问题．各种虚假信息、广告信息纷纷出现在社交网络上，比如:有的信息中包含指向钓鱼软件的链接地址，妄图窃取用户的个人隐私［2］;有的恶意用户利用链接工厂提高自己的影响力，最终影响微博话题的正常排名［3］，误导用户;还有的作弊者控制着若干Sybil账户，看似正常的Sybil，却在很多时候做着“刷粉”的不良行为［4，5］．总之，这些垃圾行为不仅耗费了网络资源，大大降低了网站的用户体验，同时严重威胁着社交用户的个人信息安全，甚至在一定程度上影响着社会稳定．

不同于传统的垃圾邮件、垃圾网页［6］，社交网络上垃圾信息的传播成本更低，而且正常用户在复杂的社交关系中有意或无意地也参与到其中．因此，用于邮件及Web上的反垃圾技术不适宜直接应用在社交网络上．本文提出一种计算社交关系强度的模型，并设计了基于关系强度的非信任分数的传播算法用于检测社交网络上的垃圾行为．与已有的排名算法［7］不同，本文提出的算法充分考虑了利用关系强度合理传播分数，而不只是考虑根据链接关系平均分配分数，这样不仅能够检测真正的恶意用户，也能够对参与垃圾行为的其他用户实施一定程度的惩罚．

1 关系强度模型的定义

在前期的研究工作［8］中，笔者发现，社交网络用户更愿意与自己兴趣爱好相近的其他用户建立好友关系并交互，而且交互频率越大，说明用户的相似性就越高．即用户之间的关系强度是由用户间的相似度及交互频率共同决定的．针对社交网络上的垃圾行为，本文将用户间的相似度及交互频率结合在一起，提出一种新的计算社交关系强度的模型．

1．1 用户间的相似度

本文引入了信息熵理论，用于计算用户之间的相似程度．首先，提出了一些用户特征:用户属性、用户行为和用户邻居，如表1所示．然后，计算两个用户的不同特征之间的熵，并将若干特征的熵求和．用户i与用户j的相似度定义为:

其中，n为用户的特征数量，k表示n中的某一特征．H(xi，xj)为计算特征的熵的函数，定义为

表1 用户特征

1．2 用户间的交互频率

社交网络上用户之间互动的次数能较有效地反映出用户之间的关系程度．比如，用户i主动回复或者提到用户j的次数为20次，用户j主动回复或者提到用户i的次数为10次，那么，用户i与用户j之间真正有效的互动次数为10次．相应的，若用户i主动回复或者提到用户k的次数为25次，但用户k主动回复或者提到用户i的次数为2次，那么用户i与k之间真正有效的互动次数应为2次．可见，用户i与j之间的关系亲密程度超过i与k之间的关系．据此，本文提出的用户之间的交互频率是根据用户之间的交互活动的发生次数进行计算．

1．3 用户间的关系强度

根据(1)，(2)的相似度及交互频率定义，本文提出一种关系强度模型，定义为:

其中，rij=fij+sij，此处考虑fij，sij分别归一化到(0，1)区间．N(i)表示用户i的邻居．通过关系强度的定义可见，该模型既考虑了用户之间特征表现上的相似程度，又考虑了用户在社交活动中的密切程度，客观估量了用户之间的关系强度．

2 基于关系强度非信任传播的排名算法

常见的一些基于链接的网页排名算法，如PageRank、HITS、TrustRank以及Anti-TrustRank，等等，可以用来识别链接工厂、降低垃圾网页的排名值．这些算法的基本思想对于检测社交网络上的垃圾行为具有借鉴意义．值得注意的是，恶意用户充分利用了社交网络自身特点，以很少的成本伪装成正常用户，不但可以轻而易举地构建与正常用户之间链接关系，而且很多正常用户有意或无意地也参与了链接工厂的构建．若直接应用网页排名算法，难以保证有效地检测出社交网络上复杂的垃圾行为．

不同于传统的基于链接的网页排名算法，本文根据用户之间的关系强度提出一种新的非信任传播的排名算法RSAR．在算法中，计算用户i分数rs(i)的公式如下:

其中，α表示衰减因子，d(n)表示n个用户的初始分数，Rij表示用户之间的关系强度，out(i)表示用户i关注的用户．

具体算法如下:

(1)输入:社交网络G;垃圾用户的坏种子集S;算法RSAR的衰减因子α;关系强度矩阵R．

(2)初始化G中用户节点的初值d(p)，

(3)将d(p)赋值到rs(0)，0表示算法迭代前的初始值．

(4)重复第5步，直至收敛，收敛后跳转至第6步．

(5)根据公式(4)，迭代计算rs分数．

(6)输出:RS分数矩阵．

该算法从初始坏种子集开始，将恶意分数根据用户之间的关系强度进行传播，而不是根据链接关系平均分配．这样做不仅能够降低恶意用户的排名，而且还在一定程度上合理惩罚了参与链接工厂的正常用户．

3 实验分析

本文采用真实的Twitter数据集，即文献［9］中提供的UDITwitter数据集．包括用户的信息、用户链接关系以及用户发表的推文．通过数据的选取以及多个志愿者的人工标记，最后得到Twitter数据包括约15 379个用户，其中有3 029个垃圾用户，12 350个正常用户．用户关系有近74万个以及近76万条推文．

实验中，选择PageRank、Anti-TrustRank以及RSAR算法，从垃圾用户及参与链接工厂构建的用户的降级情况进行分析，如图1、图2所示．

从图1可见，利用PageRank算法，有超过65%的垃圾用户排名在所有用户的前40%;采用Anti-TrustRank算法，有超过50%的垃圾用户被排在所有用户排名的20%之后．本文提出的RSAR算法，有接近90%的垃圾用户被排名在所有用户的后20%．

类似地，在对参与链接工厂的用户分析中看出，有超过80%的用户被PageRank算法排名在前20%，说明这部分用户通常是那些拥有较多社会资本的用户，但是却因为出于礼貌或者其他因素而关注垃圾用户，即参与了链接工厂的构建．仅仅利用PageRank算法不能合理地对这部分用户进行排名，而采用Anti-TrustRank算法，可以将超过80%的这部分用户排名在后20%．本文提出的RSAR算法能够将超过90%的这部分用户排名在所有用户排序的20%之后．

从上述实验结果可见，与PageRank、Anti-TrustRank算法相比，结合了关系强度的RSAR算法能够有效地将垃圾用户及参与链接工厂的用户同时进行检测及排名．

4 结束语

伴随着社交网络的飞速发展，大量的垃圾信息也在利用社交平台进行传播．不同于传统的垃圾邮件、垃圾网页，不仅社交网络的恶意用户更容易构建复杂的社交关系，进而实施狡猾的垃圾行为，而且，有些正常用户有意或无意地参与了社交链接工厂的构建．因此，有效地检测并降低社交网络上的垃圾行为，既充满了挑战又具有重要的意义．本文提出了一个针对社交网络用户的关系强度模型，并设计出一个基于关系强度的非信任分数传播的排名算法．实验结果表明，本文提出的算法能够有效检测垃圾用户，以及降低其他用户参与链接工厂的行为．

［1］Heymann P，Koutrika G，Garcia-Molina H．Fighting spam on social web sites:A survey of approaches and future challenges［J］．Internet Computing IEEE，2007，11(6):36－45．

［2］胡俊．在线社会网络上SPAM 行为检测方法研究［D］．武汉:华中科技大学，2011．

［3］hosh S，Viswanath B，Kooti F，et al．Understanding and combating link farming in the twitter social network［C］．Proceedings of the 21st international conference on World WideWeb．United States:Association for Computing Machinery，2012．

［4］江健，诸葛建伟，段海新，等．僵尸网络机理与防御技术［J］．软件学报，2012，23(1):82－96．

［5］Wilson C．Battling spam and sybils on the socialweb［D］．Santa Barbara:University of California，2012．

［6］李智超，余慧佳，刘奕群，等．网页作弊与反作弊技术综述［J］．山东大学学报:理学版，2011，46(5):1－8．

［7］Spirin N，Han J．Survey on web spam detection:principles and algorithms［J］．ACM SIGKDD Explorations Newsletter，2012，13(2):50－64．

［8］Liu X，Shen H，Ma F，etal．Topical Influential User Analysiswith Relationship Strength Estimation in Twitter［C］．2014 IEEE International Conference on Data Mining Workshop(ICDMW)．IEEE，Computer Society，USA，2014．

［9］Li R，Wang S，Deng H，etal．Towards social user profiling:unified and discriminative influencemodel for inferring home locations［C］．18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD)，United States:Association for Computing Machinery，2012．