基于交互行为的在线社会网络水军检测方法

陈侃，陈亮，朱培栋，熊岳山

(国防科学技术大学 计算机学院，湖南 长沙410073)

1 引言

网络水军出于政治或经济等目的对在线社会网络中的信息进行推广，使目标信息在极短的时间内大范围扩散，同时利用数量优势影响用户对其真实性的判断。根据内容和功能的不同，常见目标信息包括广告、木马和恶意链接、谣言等。广告水军以病毒营销的方式发布目标产品的不实描述，诱导用户对产品真实质量产生误判。病毒、木马和钓鱼网站被隐藏在正常内容中，或以中奖等方式吸引用户点击，通过超链接重定向到恶意程序所在的页面感染用户。谣言传播目的在于散布谣言并说服他人，不仅能够引导社会舆论，还可能引发大范围社会恐慌，甚至对国家安全和社会稳定造成威胁[1]。近年来爆发了多起网络造谣事件，例如“抢盐风波”[2]、“地震谣言”[3]等，对人民生活和社会治安造成严重困扰和威胁。

网络水军已成为工业界和学术界面临的重要课题，多种网络水军检测方法也被提出，如基于文本的方法[4]、基于黑名单的方法[5]和基于用户特征[6]的方法等。其中基于文本的方法适用于具有明显关键字的水军信息，如广告等；基于黑名单的方法适用于检测包含恶意链接的水军信息；基于用户行为模式的方法适用于检测具有明显水军特征的水军用户。这些检测方法局限性在于都只能检测单一种类的水军，在海量信息的条件下为保证低漏检率需要综合使用，从而增加检测的复杂性和时空耗费。因此设计一个通用性的检测方法具有重要意义。

本文提出了一种基于传播交互的水军检测方法。在线社会网络中，用户交互是引起信息传播的根本途径。水军虽然种类多样，但在交互行为上具有共同特性，而且与正常用户的交互行为表现出明显差异，因此从传播交互角度出发进行检测更具有通用性。

2 相关研究工作

近年来，随着在线社会网络的流行，网络水军越来越多地以在线社会网络作为水军活动的主要平台，知名网站如 Facebook、Twitter和 Myspace等都已经成为了水军活动的重要场所[5～7]。其他诸如论坛[8]、视频共享网站[9]、博客[10]等在内的在线网络也都已成为网络水军发动水军攻击的平台[11]。

水军检测可分为人员检测和信息检测，二者检测对象不同。人员检测针对水军成员，信息检测针对水军传播的信息。检测的一般观点是抽取特征，并利用特征分离水军成员或水军信息。

Irani通过用户注册信息对水军成员进行检测[6]，这种方法使检测可以在用户注册时进行，但准确性较低，水军用户也可以随时更改信息逃避检测。Benevenut使用SVM分类器对Twitter中网络水军进行检测[12]，使用的特征包括信息中包含链接的比例、用户账号使用时间、关注者的关注比例等。Wang利用Twitter中25 847个用户信息对网络水军进行检测[13]，检测特征包括关注与被关注度、转发数量、双向交互数量以及链接比例等。

信息检测主要是根据信息内容分析水军特征，例如信息中链接特征以及基于自然语言处理的文本分类[14]。Zhang使用基于链接相似性的方法关联水军活动[15]，并采用基于机器学习的方法对可能的水军活动进行检测。Blacklist方法利用知名的blacklist站点来检测包含恶意链接的水军信息。Gao使用此方法对 Facebook留言墙中包含恶意链接的信息进行分析[16]。Grier研究了Twitter传播信息中的恶意链接[5]，结果表明Twitter上8%的链接都被重定向到恶意网站。他的工作还证明blacklist无法解决新的威胁，当一个恶意链接被标注为 blacklist之前已经有超过90%的用户被感染。文本内容也是水军检测的重要特征。Raymond通过分析评论文本与正常用户评论的差异来发现网络水军发布的虚假评论[4]。Chen利用回复、积极性及语义特征对新闻网络上的网络水军信息进行检测，可以提供95%的检测准确率[17]。

当前网络水军检测的难点一方面在于检测的准确性有待提高，另一方面在于水军种类多样，账号多变，而检测方法大都只面向于单一种类的水军，无法提供通用的检测方案。为了保证检测的准确性需要同时使用多种检测机制，造成系统复杂性的提升和计算量的增加。

3 基于交互行为的信息传播模型

雇用网络水军的目的在于信息传播，雇主将产品、言论或观点在在线社会网络中推广，一方面需要增加信息传播广度，使其对更多用户可见；另一方面需要增加信息可信度，从而能够更好地影响用户，这些都是通过用户交互来实现的。

用户交互是信息传播的基本方式和根本动力。根据平台不同，交互类型也有不同，例如关注、转发、评论、点赞、收藏等。其中关注、转发和评论是在线社会网络中通用的交互方式。

关注：A关注B之后，B新发布的信息会实时推送给A。

转发：A转发B的信息，该信息从B的页面复制到A的页面，引起信息传播。

评论：A评论B的信息，评论内容仍在B的页面显示，不会引起信息传播，但会对信息可信性和说服力造成影响。

虽然水军种类多样，而且水军账号不断变化，但从信息传播的角度来看，无论水军信息还是正常信息都有其固有的传播模式。这些模式体现在用户之间的交互上，从这3种交互行为入手对网络水军和正常用户在信息传播中的行为差异进行分析，就能为水军信息检测提供通用性的检测方案。

用F(u)、R(u)、C(u)分别表示用户u的关注、转发和评论集合。其中，F(u)是由其他用户组成的无序集合；R和C中的元素为类似＜user,time＞的二元组，user代表发布信息的用户，time为信息发布时间，集合按照time排序。

由于转发和评论在行为上都表现为信息的再发布，行为表现和特征描述都具有相似性。为避免重复将转发和评论通称为传播，传播集合用D(u)表示。根据交互主体的不同，将传播特征分为关注者-传播者、发布者-传播者、传播者-传播者3种类型。其关系如图1所示。

图1 基于交互行为的信息传播模型

3.1 关注者-传播者特征定义

信息传播的前提是信息可见，在线社会网络中用户A发布的信息对用户B可见的方式主要有以下几种。

1)B关注A，B就可以实时获得A的更新。由于在线社会网络中推送机制的广泛使用，新的信息发布后会立即推送给关注者。

2)B关注C，C转发A的信息。那么B就可以通过C间接访问到A发布的信息。B和A之间可能存在多跳。

3)B直接获取A发布信息的链接，通过链接访问。

通过观察发现一般用户主要通过前2种方式访问信息，而网络水军则主要通过第3种方式访问目标信息。这是因为水军与雇主之间通常不存在直接的关注关系，只能通过雇主给出的链接进行信息传播。这使网络水军与正常用户在关注-传播关系上产生明显差异。

定义传播关系分布用来衡量传播者与关注者之间的关系，用DR表示传播关系分布，p为一条信息，u为信息发布者，DR的计算式为

其中，P(u)为用户u发布的所有信息，|D(p)|表示集合D(p)的元素数量。DR用来衡量传播者同时也是关注者的比例，正常用户主要通过关注关系获取信息，而网络水军主要通过链接方式获取信息，因此造成DR值的差异。

3.2 发布者-传播者特征定义

发布者与传播者之间进行直接交互，从交互时间的角度定义了平均传播时间（ADT）、首次传播时间（FDT）和传播启动时间（DST）3个特征。

1) 平均传播时间

传播时间为信息从发布到最末一次传播的总时间，平均传播时间用来描述每一条转发/评论的平均持续时间。用ADT表示平均传播时间，计算式为

其中，N=|D(p)|，由于D(p)是按照时间排序的，因此

网络水军通过完成雇主发布的传播任务获取报酬，而报酬是有限的，如果任务完成数量超出奖励限额就不会获得报酬。因此网络水军期望在任务期限内尽可能早地完成任务，而且任务完成数量一旦达到限额就不会再对信息进行传播。正常信息的传播仅受限于用户的使用习惯，传播时间与传播范围都没有具体的界限。

2) 首次传播时间

首次传播时间用来描述从信息发布到获得第一条转发/评论所等待的时间，用FDT表示首次传播时间，计算式为

其中，d1为D(p)中第一个元素。

由于消息实时推送机制的广泛使用以及移动终端应用的大力推广，很多在线社会网络都具有“类实时”特性，用户之间能够以近似实时的方式进行交互，信息也能够在第一时间被关注者传播。而网络水军访问目标信息的方式通常不是通过对被关注者的推送，而是通过给定的链接，因此难以体现出实时特性。同时水军活动任务的发布、接受、和实施都需要耗费一定的时间，使水军信息的首次传播时间比正常信息更长。

3) 传播启动时间

传播启动时间用来描述一条信息变“可信”所需要的时间。当一条信息的转发和评论量达到一定程度时，能够吸引更多用户关注并影响用户对信息内容的判断。用DST表示传播启动时间，计算式为

其中，m为可信参数，用来描述一条信息产生影响力所需要的转发/评论的数量。本文中定义m=1 000。即认为一条信息的转发/评论量超过1 000就能对用户判断产生影响。

3.3 传播者-传播者特征定义

传播者与传播者之间并没有或很少直接交互，只是在与发布者交互时产生时序关系。对该时序关系进行分析可以更好地理解传播者参与的积极性和行为规律。从传播者-传播者角度定义了平均传播间隔（ADI）和传播间隔方差（VDI）2个特征。

1) 平均传播间隔

传播时间间隔为每两条相邻信息之间的时间间隔，平均传播间隔为所有传播时间间隔的均值。其计算式为

由于水军行为多集中在短时间之内进行，呈现出突发特性，因此每2条相邻信息之间的时间间隔都很小。而正常用户发布的信息出于个人使用习惯的差异，时间间隔相对更大。

2) 传播间隔方差

传播间隔方差为所有的传播间隔之间的方差，用来描述一条信息的所有转发或评论的时间间隔的差异程度，计算方法为

水军行为的突发性不仅表现在时间间隔短，而且间隔分布也处于一个相对较小的范围内。而普通用户的转发和评论受访问习惯的影响表现出更大的差异性。

4 基于决策树的水军检测方法

将网络水军检测问题看作二分类问题，设P为在线社会网络中所有信息集合，P= {PsUPn}，其中，Ps为网络水军推广的信息集合，Pn为正常信息集合。设p为一条信息,使用特征向量表示为目标函数为，其中，φ(p)为二分类函数，网络水军检测即发现信息p是否属于集合Ps。

针对二分类问题当前已经有多种方案，例如决策树、SVM、Bayes、神经网络方法等。分类流程包括训练和分类2部分，训练过程通过特征选取和分类训练构造分类器，分类过程使用分类器对新的样本实现分类。本文选取决策树C5算法作为分类检测算法。C5算法采用Boosting方式提高模型准确率，更适合在线社会网络这类数据量较大的场景。

决策树的根节点为数据样本集，分支节点对应着对单一属性的测试，该测试将数据空间分割为多个子集。每条分支对应该属性的不同属性值，而叶节点是带有分类标记的样本集分割。决策树需要使用训练集构建，然后实现对新样本的分类检测。

首先定义相关概念如下。

信息熵：在样本集S中，依据目标属性（是否为水军信息）将S分为NS和SS这2个子集，则S的信息熵计算为

信息增益：属性D的信息增益Gain(Di)计算为

信息增益比率：属性D的信息增益比率计算为

借助各属性的信息增益比率构建检测决策树。设训练数据集S=D1D2D3D4D5D6为6维向量空间，其中，Di(1≤i≤6)分别对应模型中定义的6种特征。决策树构建算法如下。

算法1基于传播特征的决策树构建算法

输入训练数据集S

输出决策树DT

1) 初始化，设t=S为DT的根节点。

2) 计算当前样本节点t的信息熵，以及t中每个特征属性Di的信息增益比率GainRatio(Di)。

3) 令Dk=max{GainRatio(Di)}，根据Dk的取值将t划分为m个子集，每个子集为t的一个分支，对应一个新的决策树节点。

4) 依次设每个新的决策树节点为当前样本节点，重复步骤 2)～4)，直到所有新样本节点中的样本满足：①都属于同一目标类；②所有属性都处理完毕；③样本的剩余属性取值完全相同。并将这样的节点标记为叶节点。

5) 用所有叶节点中占多数的目标分类属性值来标记该叶节点，决策树构建完成，返回DT。

构造成功之后，就可以使用决策树对新的样本值进行目标属性的分类检测。从决策树的根节点开始，测试比较这个节点对应的属性值，然后选择正确分支向叶节点移动，重复比较和分支过程，直到到达叶节点，叶节点的类别属性即为最终的分类检测结果。

5 实验和分析

5.1 数据准备

从新浪微博中抓取真实数据分析传播特征。水军活动以很多方式存在，如广告水军、意见水军、木马病毒水军等。尽管内容和功能各有不同，但都以同样的方式被组织和传播。其中广告水军更常见也更容易区分，因此使用广告水军作为原型来分析其传播特征。

首先通过人工方式对新浪微博中的水军广告进行标注，然后提取这些广告信息中的关键字。利用新浪微博提供的搜索引擎使用这些关键字进行搜索，并保存搜索结果。

一般地，很多用户在看到广告时会选择忽略，极少参与转发或评论。在搜索结果中，80%的广告微博的转发和评论次数少于10次，大多数为0次。此外约10%的微博具有很高的转发和评论量，认为它们较大概率来自于网络水军。过滤掉少于100次评论和转发的微博，最后得到1 424条水军数据集。

为了与水军数据进行对比，还搜集了正常用户的微博数据。采用手动方式挑选一些较小概率雇用网络水军的用户，选取方式是：①熟悉的用户，如朋友或老师；②教育或科学界的知名人士。选择教育或科学界人士是因为认为相比其他行业，这些用户更小概率会雇用网络水军。抓取了这些用户在 4月1日到4月14日之间的所有微博。同样过滤掉少于100次评论和转发的微博，最后得到1 687条正常数据集。

5.2 传播特征统计分析

使用抓取到的数据集对水军用户和正常用户的传播特征进行分析，各项特征的累积分布如图 2所示。

图2给出了传播关系分布（DR）特征的累积分布，可看出水军信息的特征值远小于正常信息的特征值。在转发特征图中，80%的水军信息的DR值小于 0.2，说明 80%的水军信息中，由关注者给出的转发不到总量的20%。与之形成对比的是约80%的正常信息的DR值大于0.2。这一对比在评论特征图中更加明显，80%的水军信息的DR值小于0.1，说明80%的水军信息中，仅有不到10%的转发和评论来自于关注者。这一分布证明了正常信息的转发和评论主要来源于关注者，而水军信息的转发和评论主要来源于陌生人。

图2 基于转发和评论的DR累积分布

图3给出了平均传播时间的累积分布，从图中可以看出，80%的水军转发信息平均持续时间少于20 min，而90%的正常用户的平均持续时间都大于20 min。此外，80%的水军评论信息平均持续时间少于30 min，相同时间下正常评论信息只有不到5%。

图4给出了首次传播时间的累积分布，可以看出水军和正常信息在FDT上分布差异性明显。约90%以上的正常信息都可以在10 min之内获取到第一条转发和评论。而在相同时间之内，水军信息中只有10%能够获取到第一条转发，18%能获取到第一条评论。在1 min内，约45%的正常信息可以获得第一条转发和评论，而水军信息中只有2%可以获得第一条转发，7%获得第一条评论。

图3 基于转发和评论的ADT累积分布

图4 基于转发和评论的FDT累积分布

图5给出了传播启动时间的累积分布。从图中可看出正常信息的启动时间一般小于水军信息。60%的正常信息的转发启动时间小于200 min，该时间之内只有20%的水军信息获得应有的转发。DST特征的差异性不如其他特征明显，评论特征更为相近。

图5 基于转发和评论的DST累积分布

图6给出了平均传播间隔的累计分布。从数量上看，水军信息的平均传播间隔小于正常信息。60%的水军转发和评论间隔都小于10 min，而在此范围内的正常信息不到 10%。此外 25%的水军转发和35%的水军评论的平均传播间隔都在1 min之内，这证明了水军信息转发和评论时的突发特性。

图6 基于转发和评论的ADI累积分布

图7给出了传播间隔方差的累计分布。水军信息传播间隔的方差更小，说明水军信息的传播间隔之间的差异性更小。原因是水军信息的突发特性使时间间隔都相对集中在一个小范围内，而正常信息受用户使用习惯的影响差异性更大。

5.3 检测结果

将数据集分为训练集和测试集，比例为7:3。按照算法1的描述对训练集进行分类训练，得到决策树如图8所示。利用该树可以直接进行水军检测。

图7 基于转发和评论的VDI累积分布

图8 基于交互行为特征的水军检测决策树

使用测试集对决策树检测方法的有效性进行验证，并同时对比了SVM算法以及神经网络的RBF算法，验证结果如表1所示。

表1 检测方法结果对比

结果表明本文的决策树算法在基于传播模型的网络水军检测方面具有明显优势，准确率和召回率都高于其他2种方法。其中，SVM算法可以提供较高的准确率，但召回率难以保证，漏检率较高。RBF算法的召回率有所提升，但仍大幅度低于决策树算法。从综合评价来看，决策树算法性能最优，其次是RBF算法，SVM算法由于召回率过低因此性能最差。

文献[18]使用概念图模型对新浪微博中的水军进行检测，基于平台和检测对象的相似性，使用它作为参考与本文的检测方法进行对比，结果如表 2所示。可以看出，无论是在准确率、召回率还是综合评价上，本文的检测方法都表现出明显优势。这也证明了本文方法能够有效且准确地对水军进行检测。

表2 检测结果对比

对检测算法中各特征的重要性进行了分析，结果如图9所示。重要性按由高到低的顺序排名依次是FDT＞DR＞ADI＞ADT＞VDI＞DST。

图9 特征重要性评估

检测结果的高准确性证明了传播模型中特征选取的有效性，说明本文定义的特征能够准确描述网络水军和正常用户行为和传播过程的差异。正常用户可以根据关注关系实时获取更新提醒，而网络水军需要跟踪雇主发布的任务进行消息传播。正常用户对信息的访问和传播基于自己的日常习惯，而网络水军的消息传播依赖于任务发布时间和任务限额。

6 结束语

本文提出了基于交互行为的信息传播模型，从交互关系的角度定义了3种6个特征对传播行为进行量化。在此模型之下利用决策树算法对网络水军传播的信息进行检测。利用新浪微博的真实数据对传播模型进行分析并验证检测方法的有效性，结果表明本文的方法可以高效地检测出网络水军。尽管网络水军在种类功能方面各有差异，但传播行为上的共性使得本文的检测方法更具有通用性，可以适用于多场景下的水军检测。

[1] http://news.ifeng.com/opinion/special/wangluoshuijun/[EB/OL].

[2] http://zh.wikipedia.org/zh-cn/%E7%9B%B2%E6%8%A2%E7%9B%90%E4%BA%8B%E4%BB%B6[EB/OL].

[3] http://qcyn.sina.com.cn/news/ynyw/2011/1205/01134061411.html[EB/OL].

[4] RAYMOND Y K, STEPHEN L, LIAO S Y. Text mining and probabilistic language modeling for online review spam detection[J]. ACM Trans Management Inf Syst, 2011,2(4):25.

[5] GRIER C, THOMAS K, PAXSON V,et al. @spam: the underground on 140 characters or less[A]. Proceedings of the 17th ACM Conference on Computer and Communications Security[C]. Chicago, Illinois, USA, 2010. 27-37.

[6] IRANI D, WEBB S, PU C. Study of static classification of social spam profiles in MySpace[A]. ICWSM[C]. 2010.

[7] THOMAS K, GRIER C, SONG D,et al. Suspended accounts in retrospect: an analysis of twitter spam[A]. Proceedings of the 2011 ACM SIGCOMM Conference on Internet Measurement Conference[C].Berlin, Germany, 2011. 243-258.

[8] SHIN Y, GUPTA M, MYERS S. Prevalence and mitigation of forum spamming[A]. IEEE INFOCOM 2011[C]. 2011. 2309-2317.

[9] BENEVENUTO F, RODRIGUES T, ALMEIDA V,et al. Identifying video spammers in online social networks[A]. Proceedings of the 4th International Workshop on Adversarial Information Retrieval on the Web[C]. Beijing, China, 2008. 45-52.

[10] RAJADESINGAN A. MAHENDRAN A. Comment spam classi-fication in blogs through comment analysis and comment-blog post relationships[A]. Proceedings of the 13th International Conference on Computational Linguistics and Intelligent Text Processing-Volume Part II[C]. New Delhi, India: Springer-Verlag,2012.490-501.

[11] HEYMANN P, KOUTRIKA G, GARCIA-MOLINA H. Fighting spam on social Web sites: a survey of approaches and future challenges[J].IEEE Internet Computing, 2007, 11(6):36-45.

[12] BENEVENUTO F, MAGNO G, RODRIGUES T,et al. Detecting spammers on twitter[A]. CEAS[C]. 2010.

[13] WANG A H. Detecting spam bots in online social networking sites: a machine learning approach[A]. Data and Applications Security and Privacy, 25th Anunual IFIP WG11.3 Conference[C]. 2010. 335-342.

[14] 苏金树, 张博锋, 徐昕等. 基于机器学习的文本分类技术研究进展[J]. 软件学报, 2006, 19(9):1848-1859.SU J S, ZHANG B F, XU X,et al. Advances in machine learning based text categorization[J]. Journal of Software, 2006, 19(9):1848-1859.

[15] ZHANG X, ZHU S, LIANG W. Detecting spam and promoting campaigns in the Twitter social network[A]. The 12th IEEE International Conference on Data Mining[C]. 2012.1194-1199.

[16] GAO H, HU J, WILSON C,et al. Detecting and characterizing social spam campaigns[A]. The 10th ACM SIGCOMM Conference on Internet Measurement[C]. Melbourne, Australia, 2010.

[17] CHEN C, WU K, SRINIVASAN V,et al. Battling the internet water army: detection of hidden paid posters[EB/OL]. arXiv preprint ar-Xiv:1111.4297v1[cs.SI]. 2011.

[18] 韩忠明等. 面向微博的概率图水军识别模型[J]. 计算机研究与发展, 2013, S2:180-186.HAN Z M, XU F M, DUAN D G. Probabilistic graphical model for identifying water army in microblogging system[J]. Journal of Computer Research and Development, 2013, S2:180-186.