1引言
随着微博的迅猛发展，微博已经成为重要的网络媒体，在人们的生活中起着不可或缺的作用。由于微博的用户数量大、发布信息便捷、传播速度快，微博营销越来越得到重视。和传统营销相比，微博营销所需的成本低、覆盖广、针对性强，目前已应用于各行各业[1]。微博平台的这些特点使得它成为水军肆虐的新阵地，并由此产生了谋取利益的灰产业。以水军密集交互形成虚假热点是当今微博营销的重要手段，这类发帖在中文微博社会中所占的比重也不断提升。为了给客户的发帖造势，公关公司会使用大批通过软件注册的账号对目标帖子进行转发或者评论，从而在营销上制造出一种泡沫式的虚假繁荣[2]。
与传统的单个水军相比，现阶段的水军已经形成了一定的规模，并在水军之间形成了一定的网络关系[3]。微博社会中普遍存在着提供水军服务的组织，如何从这些数据中发现危害极高的水军集团，是网络水军识别研究中一个极其重要的方向[4]。这些水军集团之间具有密切的联系，识别水军团体能够从源头上最大程度地遏制微博中水军的泛滥和蔓延。
本文的研究重点是水军集团的发现，以一个典型的水军账号作为种子，逐层探索其粉丝。通过水军之间的间接互粉，将会发现属于同一水军集团的水军，从而更好地从整体上研究这些水军的活动和行为。
基于网络关系的微博水军集团发现方法
叶施仁，叶仁明，朱明峰
YE Shiren,YE Renming,ZHU Mingfeng
常州大学信息科学与工程学院，江苏常州213164
School of Information Science&Engineering,Changzhou University,Changzhou,Jiangsu213164,China
YE Shiren,YE Renming,ZHU Mingfeng.Method to find spammer group for Weibo based on network relation-ship.Computer Engineering and Applications,2017,53（6）：96-100.
Abstract：Due to high camouflage of current spammer,classic spammer discovered algorithms become no longer valid. Same with real users,spammers can also form a network structure.This paper proposes an algorithm based on the network relationship to find spammer group.The first step is to find a typical spammer account as seed.Then it extends fans’rela-tionship step by step and searches account which occurs frequently to get a collection which contains a large amount of spammer accounts,according to the clustering of the relationship between spammers and the characteristics of the sparse nature between spammer and real users,using Fast Unfolding algorithm to community detection.Through experimental analysis,the method can well find spammer group.
Key words：spammer group;network relationship;community detection
摘要：由于目前水军的高伪装性，经典的水军识别算法变得不再有效。与真实用户相同，水军用户之间也会形成一定的网络结构，提出了一种基于网络关系的方法来发现水军集团，首先以一个典型的水军账号作为种子，逐层扩展粉丝关系，优先搜索出现次数频繁的用户，从而获得一个包含大量水军账号的集合，按照水军用户之间关系的高度聚集性以及与真实用户之间关系稀疏性的特点，用Fast Unfolding算法进行社区检测。实验结果表明，该方法能够很好地发现水军集团。
关键词：水军集团；网络关系；社区检测
文献标志码：A中图分类号：TP391doi：10.3778/j.issn.1002-8331.1508-0118
基金项目：国家自然科学基金（No.61272367）。
作者简介：叶施仁（1970—），男，博士，高级工程师，主要研究方向为数据挖掘；叶仁明（1990—），男，硕士研究生，主要研究方向为数据挖掘，E-mail：310289194@qq；朱明峰（1990—），男，硕士研究生，主要研究方向为数据挖掘。
收稿日期：2015-08-12修回日期：2015-10-16文章编号：1002-8331（2017）06-0096-05
2问题的提出
在互联网技术的影响下，社会媒体蓬勃发展，越来越多的人开始使用微博。由于微博平台的优势，为了谋取利益，微博社会中存在着大量扰乱公众舆论或者进行虚假宣传的水军。当前，在对网络水军的检测和发现的研究主要集中在邮件领域、电子商务领域、社交网络领域以及论坛领域。研究的方法一般是基于内容特征、用户行为特征、用户关系特征。文献[5-6]都是对水军所发布的内容进行文本分析，通过其情感或内容的倾向来出水军的分布特点。文献[7]通过对邮件水军所发的邮件进行分析，以邮件特征作为出发点发现邮件水军的行为特征，然后在此基础上使用聚类算法，将具有相似特征的水军聚类成为水军集团。文献[8-10]也都是对水军的行为特征进行了研究。文献[11]认为利用用户行为的特征来进行水军识别具有一定的延时性，而且行为特征易于模仿和伪造，这就导致识别变得尤为困难，但是与行为特征相比，用户形成的整个网络关系具有一定的稳定性，而且不容易受用户行为的影响，使用网络关系特征进行网络水军识别具有更好的效果。文献[12]发现在社交领域，水军用户与普通用户相似，也可以形成一定程度的网络水军社区。文献[13]利用网络水军之间形成的组织关系，发现网络水军会形成网络水军团体。
本文在借鉴已有研究成果的基础上，对微博社会中的水军集团的发现进行了两个方面的研究：
（1）水军粉丝背包中的网络关系。
（2）水军集团发现。
3水军粉丝背包中的网络关系
3.1确定水军账号
为了防止垃圾消息和恶意营销在微博上的传播，新浪专门成立了微博反垃圾部门。由于微博的打击力度加强，控制着一大批水军账号的公关公司为了继续生存获得利益，开始对水军账号进行高度伪装，其特征和正常用户十分接近，从而躲避微博的封杀，这就使得利用算法从账号是否有头像，是否有原创微博，是否有粉丝以及粉丝关注比等特征上很难判别该用户是否为水军。通过对营销内容进行转发和评论的一些用户的持续观察，其所发微博中各类微博比如表1所示。
发现他们所转发的微博中包含很多广告消息，定义该类转发微博为营销微博；原创微博里大量图文不匹配的内容，定义该类原创微博为伪装微博；原创微博中存在着连续多条以相同时间间隔发布的博文，定义该类原创微博为异常微博，对于真实用户，极少的情况下会间隔相同的时间来连续发布微博，真实用户微博发布的时间一般具有离散性。本文以这三个特征作为依据，定义营销微博的比率R m表达式为：
R m=S m S
wr
×100%
定义伪装微博的比率R p表达式为：
R p=
S p
S wo×100%
定义异常微博的比率R a表达式为：
R a=S a S
wo
×100%
其中S m表示营销微博数，S a表示异常微博数，S wr表示转发微博的总数，S wo表示原创微博的总数。
当R m、R p或者R a的数值有一个超过20%，就判定该用户为水军。利用这三个特征可以对水军种子账号进行确定，同时可以对一个账号集合中的水军比进行检测和统计。3.2网络关系
操纵者控制的这些水军账号具有极强的伪装性，他们的很多特征和真实用户没有显著差别，水军账号的静态特征都高度模仿真实用户，这就导致通过经典的水军识别算法无法对其进行判别。因此从水军的粉丝组成角度出发，以营销微博、伪装微博、异常微博三个特征确定种子账号，爬取种子账号的粉丝，分析其粉丝组成，其水军比如表2所示。
通过初步的数据探索发现，水军账号的粉丝绝大部分是由水军组成。以表2中的用户作为种子，爬取每一层的粉丝，爬取相同数量的账号后统计发现其中有部分账号重复出现，结果如表3所示。
为了使账号有粉丝，达到伪装的目的，只有属于同一水军操纵者的账号才有可能去互相关注（并非直接互
账号用户1用户2用户3用户4广告
25.0
15.6
53.0
图文不匹配
34.3
25.9
46.0
同时间间隔
38.8
74.1
31.3
44.0
%
表1各类微博比
账号
水军用户1
水军用户2
水军用户3
水军用户4
粉丝数
95
48
87
93
水军比/%
97.9
95.8
96.5
97.8
表2水军账号粉丝组成
账号
水军用户1
水军用户2
水军用户3
水军用户4
爬取数
10000
10000
10000
10000
重复数
1400
1584
1754
991
表3账号重复出现情况
粉），这就会使得某些账号重复出现，导致在扩展粉丝的过程中发现这些账号是数据记录中已存在的。其中考虑到存在用户误操作的情况，有极少数的真实用户可能会粉水军账号。水军粉丝背包的网络关系如图1所示。
其中虚线代表水军用户，实线代表真实用户，a是种子用户，b、c、d是a的粉丝，e、d、c是b的粉丝，b、a、f是e 的粉丝。由于水军间的互相关注，水军间的关系和真实用户相比会更为紧密，随着水军账号数量的增多，水军账号将会形成一个内聚性的集合，和真实账号隔绝开来，如图2所示。
4水军集团发现
4.1水军账号的优先搜索
本文的研究策略是通过水军粉丝背包搜索间接的粉丝，对于真实用户，其粉丝背包通常会无限增长，而对于水军而言，理论上其粉丝背包局限于水军集团。在实际情况中，由于微博平台存在赠送粉丝的现象以及用户误操作情况，在搜索粉丝背包的过程中可能会遇到真实用户，并通过真实用户的粉丝扩散到无限的真实世界中。为了避免这一扩散的发生，采用的方法是对待扩展的账号，按照其已经成为粉丝的次数，即已经出现过的次数这个指标进行排序，这样最有可能成为水军的账号得到了优先搜索，而扩散到
真实世界的账号搜索的机会最小。
算法步骤如下：
步骤1设定所要爬取的账号的数量count，选取一个典型的水军账号作为种子，将数量count和账号id作为输入。
步骤2探索所选取的账号的粉丝，记录每个粉丝的账号以及其成为粉丝的次数。如果数据库中已经存在该账号，表示该账号已被探索完毕，使其次数加1；否则，在数据库中新增该账号，并记录其次数为1。
步骤3对待搜索的账号的已出现次数进行排序，选取最大值所对应的账号来探索其粉丝。
步骤4迭代算法步骤2，步骤3；将所探索账号的粉丝id作为输出；当现有账号数大于步骤1中的数量值时算法结束。
考虑到账号数量较大，所以排序过程采用快速排序的方法，由于每个账号的粉丝数是不固定的，每次探索后待排序列表的数量是变化的，为了便于表示，算法的时间复杂度为O(mn lb n)，实际情况中，时间复杂度是小于该值的，空间复杂度为O(lb n)，其中，m为算法结束时已探索完毕的账号个数，n为算法结束时所爬取的账号记录中去除重复行后所包含的账号数。
4.2水军集团检测
通过以种子账号为入口，对粉丝关系的不断探索，将会得到一个包含大量疑似水军账号的集合。为了在这些数据中出用户集团，采用对帐号间形成的网络关系进行研究，将关系紧密的账号划分到同一社区中，基于数据规模和运行时间等多方面的考虑，选用Fast Unfolding 算法来发现水军集团。
Fast Unfolding是一种基于模块度优化的启发式算法，它主要可以分为两个阶段：第一阶段用于设定各个节点的归属社区，直到不再发生变化；第二阶段用于构建新图，并重新执行第一阶段的操作，直到模块度值不再增加。其计算公式为：
Q=12m∑
i,j
[A ij-
k i k j
2m]δ(c i,c j)
其中，A ij表示节点i和节点j之间的边的权重；k i表示所有连接到节点i的所有边的权重之和；c i表示节点i 所属的社区；δ(c i,c j)表示节点i和节点j是否在同一个社区中，如果在同一个社区中，取值为1，否则为0；m表示形成的整个网络的所有连接权重之和。该公式可以化简为：
Q=
∑
in
2m-
æ
è
ç
ö
ø
÷
∑
tot
2m
2
其中，∑in表示一个社区内部的连接权重之和，∑tot表示所有与该社区相连的边的权重之和。
图1水军粉丝背包的网络关系
图2水军账号形成集合
算法的基本步骤如下：
初始状态，将每个节点都分配一个社区编号，使得每个节点在不同的社区中。
逐一选择各个节点，考虑该节点的邻居节点，计算将它划分到它的邻居节点所属社区中得到的模块度增益，如果所得的最大增益为正数，则接受这个社区变动，将它划分到对应的邻居社区；否则，保持节点归属于原社区。
重复步骤2，当每个节点所归属的社区不再发生变化时结束。
在前面步骤所构建的新的网络图基础上，重复步骤2，直到获得最大的模块度值，其中新网络图中的每个节点代表上一阶段形成的不同社区，边的权重值为两个社区中所有节点对的边的权重之和。
步骤2中计算增益的公式为：
ΔQ=é
ë
êê
ù
û
úú
∑
in
+k i,in
2m-
æ
è
ç
ö
ø
÷
∑
tot
+k i
2m
2
-
é
ë
ê
ê
ù
û
ú
ú
∑
in
2m-
æ
è
ç
ö
ø
÷
∑
tot
2m
2
-æ
è
ç
ö
ø
÷
k i
2m
2
其中，k i,in表示节点i到社区内部节点的边的权重之和。
5实验结果及分析
由于微博API的限制，获取用户粉丝的接口只能授权给当前登录的用户，所以采取的方法是使用Python编写网页爬虫程序对用户的粉丝数据进行采集，并将所获取的数据存储到MySQL数据库中。以一个真实用户作为种子和以营销微博、异常微博和伪装微博这三个特征选定某一汽车营销账号的粉丝作为种子，分别按照水军账号优先探索的方法爬取用户账号1858968个，账号中包含的节点数和重复率如表4所示。
采用Fast Unfolding算法进行社区检测，其中算法的resolution参数主要用来调节社区的大小。采用不同参数值会导致所划分的社区规模不同。为了到一个参数值使得所发现的社区规模尽可能准确，使其和真实规模相符合，对同一个参数值进行多次社区发现，它们所得结果的相关性越小，则表示该resolution参数所划分的社区结果不是真实规模的可能性就越大[14-15]。在（0，1]区间中，对于同一resolution参数值进行2次社区划分，其结果所对应的相关性值如图3所示。
其中水军用户数据中相关性值最大为0.933，对应resolution参数为0.5，真实用户数据中相关性值最大为0.968，对应resolution参数为0.8，因此算法的参数分别设为0.5和0.8，得到的社区数和模块度值如表5所示。
从每个社区中随机抽取20个账号，以营销微博、异常微博和伪装微博三个特征作为衡量标准来判断是否为水军。以水军作为种子所发现的社区中水军比如图4，以真实用户作为种子所发现的社区中水军比如图5所示，不同水军比值所对应社区数如表6所示。
对比以两种用户作为种子所爬取的账号数据集，可以看到水军用户作为种子的数据集中账号重复率较高，
种子水军用户真实用户
节点数
630496
1504353
重复率/%
66.1
19.1
表4爬取账号集合中节点数
种子
水军用户
真实用户
社区数
142
231
模块度值
0.71
0.79
表5
社区数和模块度值
100
80
60
40
20
水
军
比
/
%
社区
131
118
105
14274053667992
1
图4
水军作为种子社区抽样数据水军比100
80
60
40
20
水
军
比
/
%
社区
211
190
169
22436485
1148
127
106
图5真实用户作为种子社区抽样数据水军比
水军比值区间
[90%，100%]
[80%，90%）
[70%，80%）
[60%，70%）
[50%，60%）
[40%，50%）
[30%，40%）
[20%，30%）
[10%，20%）
[0，10%）
水军用户作为
种子社区数
24
24
21
14
15
23
5
6
8
2
真实用户作为
种子社区数
1
5
7
9
20
26
44
61
58
表6
水军比值对应社区数
1.0
0.8
0.6
0.4
0.2
相
关
性
值
0.20.40.60.8 1.0
参数值
水军用户真实用户
图3不同的参数值对应的相关性值
66.1%的账号多次重复出现。从两个数据集的社区检测对比结果可以看出，以水军用户作为种子数据集中水军的比例明显高于真实用户数据集，其中，因为存在垃圾用户或者水军粉真实用户的情况，在以真实用户作为种子进行粉丝搜索的时候存在一定的可能性会搜索到水军用户，所以真实用户数据集中有部分社区和其他社区相比水军比例较高。
6结束语
随着微博平台的发展，水军集团的发现研究引起了众多学者的关注，由于当前水军账号的高伪装性，识别水军具有很大的困难，本文通过分析水军账号的粉丝组成情况，提出了一种基于网络关系的方法来发
现水军集团，以水军种子账号作为入口，采用水军优先搜索的方法，由于正常用户和水军都会在各自领域形成一定的网络结构，水军之间的联系比水军与正常用户的联系紧密，按照这个特点用Fast Unfolding算法进行社区检测。通过实验发现该方法在水军集团发现的研究中具有良好的效果，相信本文的研究能够给网络管理者和政府部门提供有力的帮助，掌握去除水军言论后的真实舆情，识别和预防不法行为。
参考文献：
[1]周合强.微博营销现状与发展态势初探[J].新闻世界，2011（4）：
100-101.
[2]张筱筠，连娜.网络水军：微博营销中的“灰阴影”[J].新
权施文闻界，2012（1）：10-12.
[3]莫倩，杨珂.网络水军识别研究[J].软件学报，2014（7）：
1505-1526.
[4]Mukherjee A，Liu B，Glance N.Spotting fake reviewer
groups in consumer reviews[C]//WWW’12-Proceedings of the21st Annual Conference on World Wide Web，2012：191-200.
[5]Liu H，Zhao Y，Qin B，et al.Comment target extraction and
sentiment classification[J].Journal of Chinese Information Processing，2010，24（1）：84-88.
[6]Niu Yuan，Wang Yimin，Chen Hao，et al.A quantitative
study of forum spamming using context based analysis[C]//
Proc Network and Distributed System Security（NDSS）Symposium，2007：1-14.
[7]Husna H，Phithakkitnukoon S，Palla S，et al.Behavior analysis
of spam botnets[C]//Proc of the3rd Int’l Conf on Commu-nication Systems Software and Middleware and Workshops （COMSWARE2008）.Washington：IEEE Computer Society，2008：246-253.
[8]Lim E P，Nguyen V A，Jindal N，et al.Detecting product
review spammers using rating behaviors[C]//Proceedings of the19th ACM International Conference on
Information and Knowledge Management，2010：939-948.
[9]Qiu Y F，Wang J K，Shao L S，et al.Research on product
review spammer detection based on users’behavior[J].Com-puter Engineering，2012，38（11）.
[10]Mukherjee A，Kumar A，Liu B，et al.Spotting opinion
spammers using behavioral footprints[C]//Proceedings of
the19th ACM SIGKDD International Conference on
Knowledge Discovery and Data Mining，2013：632-640.
[11]Song J，Lee S，Kim J.Spam filtering in twitter using sender-
receiver relationship[C]//Proceedings of the14th Interna-tional Conference on Recent Advances in Intrusion De-tection，2011：301-317.
[12]Bhat S Y，Abulaish M.Community-based features for
identifying spammers in online social networks[C]//2013
International Conference on Advances in Social Networks
Analysis and Mining（ASONAM），2013：100-107.
[13]Xu C，Zhang J，Chang K，et al.Uncovering collusive
spammers in Chinese review websites[C]//Proceedings of
the22nd ACM International Conference on Information&
Knowledge Management，2013：979-988.
[14]Lambiotte R，Delvenne J C，Barahona M.Laplacian dynamics
and multiscale modular structure in networks[EB/OL].
[2015-06-10].http：//xueshu.baidu/s?wd=paperuri%3A%
285dabcec3a13f4421a23f097d6cd71f7b%29&filter=sc_long_
sign&tn=SE_xueshusource_2kduw22v&sc_vurl=http%3A%
%2Fabs%2F0812.1770&ie=utf-8&sc_us= 7513086524586485027.
[15]Nooy W D，Mrvar A，Batagelj V.Exploratory social net-
work analysis with Pajek[M].[S.l.]：Cambridge University
Press，2005：191-193.
发布评论