96 2017，53（6） Computer Engineering and Applications 计算机工程与应用 基于网络关系的微博水军集团发现方法 叶施仁，叶仁明，朱明峰 YE Shiren, YE Renming, ZHU Mingfeng 常州大学 信息科学与工程学院，江苏 常州 213164 School of Information Science & Engineering, Changzhou University, Changzhou, Jiangsu 213164, 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 中图分类号：TP391 doi：10.3778/j.issn.1002-8331.1508-0118 1 引言 随着微博的迅猛发展，微博已经成为重要的网络媒 体，在人们的生活中起着不可或缺的作用。由于微博的 用户数量大、发布信息便捷、传播速度快，微博营销越来 越得到重视。和传统营销相比，微博营销所需的成本 低、覆盖广、针对性强，目前已应用于各行各业[1]。微博 平台的这些特点使得它成为水军肆虐的新阵地，并由此 产生了谋取利益的灰色产业。以水军密集交互形成虚 假热点是当今微博营销的重要手段，这类发帖在中文微 博社会中所占的比重也不断提升。为了给客户的发帖 造势，公关公司会使用大批通过软件注册的账号对目标 帖子进行转发或者评论，从而在营销上制造出一种泡沫 式的虚假繁荣[2]。 与传统的单个水军相比，现阶段的水军已经形成了 一定的规模，并在水军之间形成了一定的网络关系 [3]。 微博社会中普遍存在着提供水军服务的组织，如何从这 些数据中发现危害极高的水军集团，是网络水军识别研 究中一个极其重要的方向[4]。这些水军集团之间具有密 切的联系，识别水军团体能够从源头上最大程度地遏制 微博中水军的泛滥和蔓延。 本文的研究重点是水军集团的发现，以一个典型的 水军账号作为种子，逐层探索其粉丝。通过水军之间的 间接互粉，将会发现属于同一水军集团的水军，从而更 好地从整体上研究这些水军的活动和行为。 基金项目：国家自然科学基金（No.61272367）。 作者简介：叶施仁（1970—），男，博士，高级工程师，主要研究方向为数据挖掘；叶仁明（1990—），男，硕士研究生，主要研究方向为 数据挖掘，E-mail：310289194@qq.com；朱明峰（1990—），男，硕士研究生，主要研究方向为数据挖掘。 收稿日期：2015-08-12 修回日期：2015-10-16 文章编号：1002-8331（2017）06-0096-05 

叶施仁，叶仁明，朱明峰：基于网络关系的微博水军集团发现方法 2017，53（6） 97 2 问题的提出 在互联网技术的影响下，社会媒体蓬勃发展，越来 越多的人开始使用微博。由于微博平台的优势，为了谋 取利益，微博社会中存在着大量扰乱公众舆论或者进行 虚假宣传的水军。当前，在对网络水军的检测和发现的 研究主要集中在邮件领域、电子商务领域、社交网络领 域以及论坛领域。研究的方法一般是基于内容特征、用 户行为特征、用户关系特征。文献[5-6]都是对水军所发 布的内容进行文本分析，通过其情感或内容的倾向来找 出水军的分布特点。文献[7]通过对邮件水军所发的邮 件进行分析，以邮件特征作为出发点发现邮件水军的行 为特征，然后在此基础上使用聚类算法，将具有相似特 征的水军聚类成为水军集团。文献[8-10]也都是对水军 的行为特征进行了研究。文献[11]认为利用用户行为的 特征来进行水军识别具有一定的延时性，而且行为特征 易于模仿和伪造，这就导致识别变得尤为困难，但是与 行为特征相比，用户形成的整个网络关系具有一定的稳 定性，而且不容易受用户行为的影响，使用网络关系特 征进行网络水军识别具有更好的效果。文献[12]发现 在社交领域，水军用户与普通用户相似，也可以形成一 定程度的网络水军社区。文献[13]利用网络水军之间 形成的组织关系，发现网络水军会形成网络水军团体。 本文在借鉴已有研究成果的基础上，对微博社会中 的水军集团的发现进行了两个方面的研究： （1）水军粉丝背包中的网络关系。 （2）水军集团发现。 3 水军粉丝背包中的网络关系 3.1 确定水军账号 为了防止垃圾消息和恶意营销在微博上的传播，新 浪专门成立了微博反垃圾部门。由于微博的打击力度 加强，控制着一大批水军账号的公关公司为了继续生存 获得利益，开始对水军账号进行高度伪装，其特征和正 常用户十分接近，从而躲避微博的封杀，这就使得利用 算法从账号是否有头像，是否有原创微博，是否有粉丝 以及粉丝关注比等特征上很难判别该用户是否为水 军。通过对营销内容进行转发和评论的一些用户的持 续观察，其所发微博中各类微博比如表 1 所示。 表 1 各类微博比 账号 用户 1 用户 2 用户 3 用户 4 广告 25.0 0 15.6 53.0 图文不匹配 34.3 25.9 46.0 0 % 同时间间隔 38.8 74.1 31.3 44.0 发现他们所转发的微博中包含很多广告消息，定义 该类转发微博为营销微博；原创微博里大量图文不匹配 的内容，定义该类原创微博为伪装微博；原创微博中存 在着连续多条以相同时间间隔发布的博文，定义该类原 创微博为异常微博，对于真实用户，极少的情况下会间 隔相同的时间来连续发布微博，真实用户微博发布的时 间一般具有离散性。本文以这三个特征作为依据，定义 营销微博的比率 Rm 表达式为： × 100% Rm = Sm Swr 定义伪装微博的比率 Rp 表达式为： Sp Swo × 100% × 100% Rp = 定义异常微博的比率 Ra 表达式为： Ra = Sa Swo 其中 Sm 表示营销微博数，Sa 表示异常微博数，Swr 表 示转发微博的总数，Swo 表示原创微博的总数。当 Rm、 Rp 或者 Ra 的数值有一个超过 20%，就判定该用户为水 军。利用这三个特征可以对水军种子账号进行确定，同 时可以对一个账号集合中的水军比进行检测和统计。 3.2 网络关系 操纵者控制的这些水军账号具有极强的伪装性，他 们的很多特征和真实用户没有显著差别，水军账号的静 态特征都高度模仿真实用户，这就导致通过经典的水军 识别算法无法对其进行判别。因此从水军的粉丝组成 角度出发，以营销微博、伪装微博、异常微博三个特征确 定种子账号，爬取种子账号的粉丝，分析其粉丝组成，其 水军比如表 2 所示。 表 2 水军账号粉丝组成 账号 粉丝数 水军比/% 水军用户 1 水军用户 2 水军用户 3 水军用户 4 95 48 87 93 97.9 95.8 96.5 97.8 通过初步的数据探索发现，水军账号的粉丝绝大部 分是由水军组成。以表 2 中的用户作为种子，爬取每一 层的粉丝，爬取相同数量的账号后统计发现其中有部分 账号重复出现，结果如表 3 所示。 表 3 账号重复出现情况 账号 水军用户 1 水军用户 2 水军用户 3 水军用户 4 爬取数 10 000 10 000 10 000 10 000 重复数 1 400 1 584 1 754 991 为了使账号有粉丝，达到伪装的目的，只有属于同 一水军操纵者的账号才有可能去互相关注（并非直接互 

98 2017，53（6） Computer Engineering and Applications 计算机工程与应用 粉），这就会使得某些账号重复出现，导致在扩展粉丝的 过程中发现这些账号是数据记录中已存在的。其中考 虑到存在用户误操作的情况，有极少数的真实用户可能 会粉水军账号。水军粉丝背包的网络关系如图 1 所示。 算法步骤如下： 步骤 1 设定所要爬取的账号的数量 count ，选取一 个典型的水军账号作为种子，将数量 count 和账号 id 作 为输入。 b a f e d c a b c d 图 1 水军粉丝背包的网络关系 其中虚线代表水军用户，实线代表真实用户，a 是种 子用户，b、c、d 是 a 的粉丝，e、d、c 是 b 的粉丝，b、a、f 是 e 的粉丝。由于水军间的互相关注，水军间的关系和真实 用户相比会更为紧密，随着水军账号数量的增多，水军 账号将会形成一个内聚性的集合，和真实账号隔绝开 来，如图 2 所示。 a b c d f e 图 2 水军账号形成集合 4 水军集团发现 4.1 水军账号的优先搜索 本文的研究策略是通过水军粉丝背包搜索间接的 粉丝，对于真实用户，其粉丝背包通常会无限增长，而对 于水军而言，理论上其粉丝背包局限于水军集团。在实 际情况中，由于微博平台存在赠送粉丝的现象以及用户 误操作情况，在搜索粉丝背包的过程中可能会遇到真实 用户，并通过真实用户的粉丝扩散到无限的真实世界 中。为了避免这一扩散的发生，采用的方法是对待扩展 的账号，按照其已经成为粉丝的次数，即已经出现过的 次数这个指标进行排序，这样最有可能成为水军的账号 得到了优先搜索，而扩散到真实世界的账号搜索的机会 最小。 步骤 2 探索所选取的账号的粉丝，记录每个粉丝的 账号以及其成为粉丝的次数。如果数据库中已经存在 该账号，表示该账号已被探索完毕，使其次数加 1；否则， 在数据库中新增该账号，并记录其次数为 1。 步骤 3 对待搜索的账号的已出现次数进行排序，选 取最大值所对应的账号来探索其粉丝。 步骤 4 迭代算法步骤 2，步骤 3；将所探索账号的粉 丝 id 作为输出；当现有账号数大于步骤 1 中的数量值时 算法结束。 考虑到账号数量较大，所以排序过程采用快速排序 的方法，由于每个账号的粉丝数是不固定的，每次探索 后待排序列表的数量是变化的，为了便于表示，算法的 时间复杂度为 O(mn lb n) ，实际情况中，时间复杂度是小 于该值的，空间复杂度为 O(lb n) ，其中，m 为算法结束 时已探索完毕的账号个数，n 为算法结束时所爬取的账 号记录中去除重复行后所包含的账号数。 4.2 水军集团检测 通过以种子账号为入口，对粉丝关系的不断探索，将 会得到一个包含大量疑似水军账号的集合。为了在这些 数据中找出用户集团，采用对帐号间形成的网络关系进 行研究，将关系紧密的账号划分到同一社区中，基于数据 规模和运行时间等多方面的考虑，选用 Fast Unfolding 算法来发现水军集团。 Fast Unfolding 是一种基于模块度优化的启发式算 法，它主要可以分为两个阶段：第一阶段用于设定各个 节点的归属社区，直到不再发生变化；第二阶段用于构 建新图，并重新执行第一阶段的操作，直到模块度值不 再增加。其计算公式为： kikj 2m ]δ(ci,cj) 2m ∑ Q = 1 [Aij - i,j 其中，Aij 表示节点 i 和节点 j 之间的边的权重；ki 表示 所有连接到节点 i 的所有边的权重之和；ci 表示节点 i 所属的社区；δ(ci,cj) 表示节点 i 和节点 j 是否在同一个 社区中，如果在同一个社区中，取值为 1，否则为 0；m 表 示形成的整个网络的所有连接权重之和。该公式可以 化简为： æ çç è ∑ tot 2m ∑ 2m - 表示一个社区内部的连接权重之和，∑ Q = 其 中 ，∑ 示所有与该社区相连的边的权重之和。 2 ö ÷÷ ø in in 表 tot 

叶施仁，叶仁明，朱明峰：基于网络关系的微博水军集团发现方法 2017，53（6） 99 算法的基本步骤如下： 初始状态，将每个节点都分配一个社区编号，使得 每个节点在不同的社区中。 逐一选择各个节点，考虑该节点的邻居节点，计算 将它划分到它的邻居节点所属社区中得到的模块度增 益，如果所得的最大增益为正数，则接受这个社区变动， 将它划分到对应的邻居社区；否则，保持节点归属于原 社区。 重复步骤 2，当每个节点所归属的社区不再发生变 化时结束。 在前面步骤所构建的新的网络图基础上，重复步 骤 2，直到获得最大的模块度值，其中新网络图中的每个 节点代表上一阶段形成的不同社区，边的权重值为两个 社区中所有节点对的边的权重之和。 步骤 2 中计算增益的公式为： ∑ ∑ é é êê ê 2m - ê ë ë ù 2 ö ú ú ø÷ û 其中，ki,in 表示节点 i 到社区内部节点的边的权重之和。 + ki,in in 2m ki 2m - æ èç ù 2 ö úú ÷÷ ø û ∑ tot 2m æ çç è 2 ö ÷÷ ø - æ çç è - in ΔQ = ∑ + ki tot 2m 5 实验结果及分析 由于微博 API 的限制，获取用户粉丝的接口只能授 权给当前登录的用户，所以采取的方法是使用 Python 编 写网页爬虫程序对用户的粉丝数据进行采集，并将所获 取的数据存储到 MySQL 数据库中。以一个真实用户作 为种子和以营销微博、异常微博和伪装微博这三个特征 选定某一汽车营销账号的粉丝作为种子，分别按照水军 账号优先探索的方法爬取用户账号 1 858 968 个，账号 中包含的节点数和重复率如表 4 所示。 表 4 爬取账号集合中节点数 种子 水军用户 真实用户 节点数 630 496 1 504 353 重复率/% 66.1 19.1 采用 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 所示。 1.0 0.8 值 0.6 性 0.4 关 0.2相 0 水军用户 真实用户 0.2 0.4 0.6 0.8 1.0 参数值 图 3 不同的参数值对应的相关性值 表 5 社区数和模块度值 种子 水军用户 真实用户 社区数 模块度值 142 231 0.71 0.79 从每个社区中随机抽取 20 个账号，以营销微博、异 常微博和伪装微博三个特征作为衡量标准来判断是否 为水军。以水军作为种子所发现的社区中水军比如图 4， 以真实用户作为种子所发现的社区中水军比如图 5 所 示，不同水军比值所对应社区数如表 6 所示。 / % 比 军 水 100 80 60 40 20 0 1 14 27 40 53 66 79 92 105 118 131 社区 图 4 水军作为种子社区抽样数据水军比 100 80 60 40 20 / % 比 军 水 0 1 22 43 64 85 127 148 169 190 211 106 社区 图 5 真实用户作为种子社区抽样数据水军比 表 6 水军比值对应社区数 水军比值区间 [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 0 1 5 7 9 20 26 44 61 58 对比以两种用户作为种子所爬取的账号数据集，可 以看到水军用户作为种子的数据集中账号重复率较高， 

100 2017，53（6） Computer Engineering and Applications 计算机工程与应用 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 reviews[C]//WWW’12- Proceedings groups in consumer of the 21st 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 the 3rd Int’l Conf on Commu- nication Systems Software and Middleware and Workshops （COMSWARE 2008）.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 the 19th 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 the 19th 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 the 14th 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 the 22nd 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.com/s?wd=paperuri%3A% 285dabcec3a13f4421a23f097d6cd71f7b%29&filter=sc_long_ sign&tn=SE_xueshusource_2kduw22v&sc_vurl=http%3A% 2F%2Farxiv.org%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.