王恩贤， 陶宏才

(西南交通大学信息科学与技术学院，四川成都611756)

0 引言

随着互联网应用的快速发展和移动终端的大规模普及，以微博为代表，国内外微博用户数量急剧增长，微博已经逐渐成为人们进行社交的工具。与此同时，微博的炒作现象严重影响用户体验及用户安全，“网络水军”、“网络推手”等利用微博散布谣言和虚假信息，操控网络舆论，严重干扰了网络秩序，也影响了社会的安定［1］。微博炒作的基本方式是通过微博营销公司，雇佣名人微博、草根大号及水军团等广泛评论、转发微博，在短时间内造成热门微博的假象，以此向世界各地传播信息。

目前，在对微博炒作的研究方面，主要集中在微博问政、微博传播伦理研究和少量的微博炒作［2］。大部分研究停留在理论层面上，还没有在技术层面上进行深层次的探讨。随着Web的发展，社交类网站的影响能力和辐射人群日益壮大，消息的真伪以及是否存在人为的操控言论的走向，逐渐成为网络舆情研究的新热点。结合理论和技术研究，对炒作微博的特征进行分析，构建特征集，基于SVM(support vector machine)算法，加入粒子群PSO(particle swarm optimization)算法对SVM模型中的误差惩罚因子参数和核函数参数进行优化，分析对比得到最佳分类模型，对炒作微博进行有效的识别和检测。研究开发高效的炒作微博的识别方法，对微博的健康发展具有重要的意义和应用价值。

1 SVM概述及PSO算法

1．1 SVM 概述

支持向量机根据有限的样本信息，在模型的学习能力和复杂性之间寻求最佳结合［3］，通过选择适当的函数使学习机的期望风险达到最小，保证通过有限训练样本得到小误差分类器对独立测试集的测试误差比较小，从而得到一个具有最优分类能力和推广泛化能力的学习机［4］，通过利用Lagrange优化方法可以把支持向量机最优分类面问题转化为对偶问题［5］。

对于非线性可分的情况，SVM利用核函数将低维输入空间映射到高维特征空间使线性可分，在低维、高维、小样本和大样本等情况下，RBF核函数都表现出了很好的学习能力，得到了广泛的应用［6］。，文中选择RBF函数作为SVM的核函数，最优化问题就取决于核参数g和惩罚因子c的选择，这样选择较佳的参数可使分类模型具有较优的性能和推广能力。

1．2 粒子群算法

1995 年，Kennedy 和 Eberhart［7］提出了基于种群的粒子群算法(particle swarm optimization，PSO)。其基本思想［8］是模拟鸟群飞行过程中的群体协作避免迷失方向，由此实现群体目的最优。PSO算法中所有的粒子都拥有一个由被优化函数产生的适应值(fitness)，以及决定飞行方向和距离的速度。PSO首先初始化一群随机粒子，粒子追随最优粒子在解空间中不断更新自己的位置、速度和适应度值，从而产生下一代粒子。粒子飞行经过的最好位置为局部最优值，整个群体所经历过的最好位置为群体的最优值。

文中将利用粒子群算法，优化SVM中的核参数g和误差惩罚因子c。首先，根据种群数量的设置，为参数c和g分别初始化一组粒子群，并随机生成种群中粒子的速度和位置。然后，使用目标函数计算种群中粒子的适应度值，并根据计算出的适应度值更新粒子种群的局部最优的和全局最优的c和g。最终，利用得到的较优c和g参数对，构造出PSO-SVM模型以识别炒作微博。

2 炒作微博特征分析与提取

2．1 社团模块度

热门微博榜是通过微博的转发、评论数量及频率等进行综合排名的，为达到炒作的目的，炒作用户一般聚集一群用户，操作微博的舆论传播。提取微博传播网络中的节点信息，通过网络分析工具Pajek作网络信息传播，其传播结构如图1、图2所示。从图1可见，热门微博信息传播方式是逐层扩散出去的，并且传播力度逐层减弱，呈现出核爆式的传播。图2为一条典型的炒作微博的信息传播结构图，此微博的传播完全围绕着几个大V(粉丝数10万以上)关键用户进行传播，很少有离散的节点传播路径，具有典型的群体策划现象。

图1 热门微博信息传播结构

图2 炒作微博信息传播结构

为能够衡量网络社团结构的划分程度和聚集程度，Girvan和 Newman［9］定义了模块性函数，定量地描述网络社团的划分和紧密程度。所谓模块性，即网络中连接社团结构内部节点的边所占的比例与另外一个随机网络中连接社团结构内部节点的边所占比例的期望值相减得到的差值。随机网络的构造，通过保持每个节点的社团属性不变，节点的边根据节点的度随机连接来进行。如果随机网络的稠密程度期望值低于现实的社团内部连接稠密程度值，说明得到较好的社团结构划分。通常用Q函数对社团模块度水平进行描述。

假设已划分出网络社团结构，节点vi所属的社团编号为σi，则网络中社团内部的连边所占比例为

在式(1)中，aij表示网络邻接矩阵中的元素，若vi和vj2节点无边相连，aij=0，否则aij=1;若vi和vj是同一社团的节点，即 σi= σj时，δ(σi，σj)=1 ，否则为0。网络中边的数目M=0．5∑ aij。在社团结构固定时，构建出随机连接边的网络，节点vi和vj之间存在连接边的可能性为kikj/2M，其中ki和kj分别为节点vi和vj的度。由此，Q函数可以定义为

若社团内部节点间的边数小于随机连接得到的边数，则Q小于0。若Q函数值接近1，表明社团结构内部连接高度紧密。在实际应用中，Q一般在0.3～0.7。

2．2 平均最短路径

网络信息传播不仅依赖于小世界网络中的最短路径，还与网络行为的多次社会性强化相关［10］。最短路径是指2个节点间最小值的路径，平均最短路径是指社团网络中任意两节点最短路径的均值。若2条微博的传播数相同，而传播节点间的平均最短路径相差较大，则认为平均最短路径大的微博，其传播层数多，影响力大;而平均最短路径小的微博，传播多集中在某个或某几个转发者的粉丝之间，以至于传播层数少，影响力小。利用平均最短路径来判断微博的扩散范围，通过计算微博传播中节点平均最短路径，判断节点间的紧密程度，以此识别出炒作微博。

文中采用Floyd算法计算最短路径，基本思想是从任意节点i到任意节点j的最短路径存在2种可能，一是直接从节点i到j，二是从节点i经过若干个节点k到j。设dpv表示节点p到节点v的最短路径距离，对于网络中的每一个节点k，检查dik+dkj＜dij是否成立。如果成立，说明从节点i经过k到节点j的路径比i直接到j的路径更短，便设置dij=dik+dkj。循环遍历完所有的节点k，dij存储的值就是节点i到节点j的最短路径距离。具体算法描述为:

(1)从任意一条单边的路径开始。设2点之间的距离是边的权值，若2点之间没有直接的边相连，则权值设为无穷大。

(2)对每一对顶点p和v，查看是否存在一个顶点w使从顶点p到w再到v的路径比己知的路径更短。

(3)如果路径更短，则更新。若存在未搜索节点，继续步骤(2)，否则结束。

2．3 关键用户属性

在微博的传播过程中，存在一些大V用户，其转发、评论等行为对微博的传播起到至关重要的影响，这些重要的传播节点称为关键用户。相关研究［11］发现，账户关注好友的质量和账户状态特征最能体现正常账户和炒作账户之间的区别。为了能够衡量账户及其关注好友的质量，定义声望值FM反映账户的影响力。FM定义为

其中，Nf(u)和Ng(u)分别表示账户u的粉丝数和关注数。

提取炒作微博传播过程中的关键用户的属性信息并作累积分布函数曲线(CDF)如图3～6所示。

图3 关键用户平均关注数

图4 关键用户平均声望值

图5 关键用户关注好友的平均声望值

图6 关键用户关注好友的平均粉丝数

由图3可以看出，正常微博中绝大部分的关键用户平均关注数高于550，炒作微博中绝大部分的关键用户平均关注数不足450。由图4和图5可以看出，绝大多数正常微博中关键用户和关注好友的平均声望值高于炒作微博的关键用户和关注好友的平均声望值。

由图6可以看出，炒作微博中85%以上的关键用户关注好友的平均粉丝数数量级为105，而正常微博中85%以上的关键用户关注好友的平均粉丝数数量级为106。

炒作微博中的节点用户质量与正常微博中的节点用户质量有着明显的区别，可以用反映账户质量的相关特征加以区分炒作微博和正常微博。关键用户关注好友的质量通过好友平均粉丝数和平均声望值反映，而关键用户的状态特征通过用户平均声望值和平均关注数体现。

3 基于SVM优化算法的炒作微博识别方法

炒作微博识别框架基本流程图如图7所示，识别框架主要包括数据预处理、特征提取、模型建立及训练测试和决策分类等几个主要步骤组成。数据预处理主要是对原始数据进行分类、节点关系提取以及节点粉丝和关注数的计算。特征是通过微博的节点传播途径和节点信息来提取，提取出的特征包括社团模块度、平均最短路径、关键用户关注好友的平均声望值和平均粉丝数以及关键用户的平均声望值和平均关注数。

在模型的建立过程中，通过粒子群算法PSO对SVM中的核参数g和惩罚因子c进行优化，PSO优化SVM参数流程图如图8所示。Vapnike等［12］研究表明，核参数g和惩罚因子c是影响SVM性能的关键因素，设置c的取值范围为［0.1，100］，g的取值范围为［0.01，1000］。由于需要优化的参数较少，所以种群粒子数目设为20，迭代步数为200。加速度因子c1和c2表示向局部最优和全局最优推进的加速度权值，c1一般等于 c2，取值范围在［0，4］［13］，文中都取 2。为能够提高算法的搜索能力和分类能力，针对PSO算法容易早熟和后期容易在全局最优解附近振荡的现象，采用线性递减权重法对惯性权重ω进行调整，ωmax取值0.9，ωmin取值0.4。

图7 识别框架流程图

图8 PSO优化SVM参数流程图

炒作微博的识别分为训练阶段和测试阶段，首先使用训练数据训练模型，分析训练结果和准确率。然后使用模型测试数据，得出测试数据对应的分类结果，最后通过对比预先人工标注的测试数据分类标签得出最终的分类准确率。

4 实验结果与分析

4．1 数据集的获取及分析

基于新浪微博实验平台，利用API接口和网络爬虫工具相结合，提取微博的传播路径和节点信息，计算每条微博关键节点的属性信息和传播节点之间的紧密程度，以判断是否有社团存在的可能性。从热门微博中选择饮品、娱乐等话题获取实验数据集，剔除变量缺失的样本数据，共获得610个样本。数据主要包括微博用户的属性信息(关注、粉丝和微博等)，好友属性信息，转发用户属性信息。

由于目前没有标准的炒作微博数据集，所以需要以人工标注的形式对微博进行标注。在标注过程中，选择房价、饮品和娱乐等话题数据标注，以使数据集的标注具有多样性。每条热门微博同时由2个人标注，只有标注结果一致才加入到数据集中，尽可能避免标注时的人为主观性因素。

使用SVM模型对数据进行分类，发现2类数据具有明显的区别。由图9可见，炒作微博的社团模块度集中于0.8～0.9，超出了正常社团的范围［0.3，0.7］，并且平均最短路径值集中于3～5，明显背离了六度分隔理论，传播层次少，传播主要集中在某几个转发者的粉丝之间，体现出了节点间具有较强的紧密程度。对于炒作微博和正常微博，用户的平均声望值、平均关注数以及好友的平均声望值和平均声望值有着较为明显的区别，反映出炒作微博的关键节点用户及其好友的质量与正常微博的账户质量之间有着明显的区别。

图9 炒作微博与正常微博的分类

4．2 评价指标

通过模型预测微博分类，为了能够反映出分类结果的优劣，定义以下几个评价指标衡量分类的质量。

表1 炒作微博识别结果

表1所示为炒作微博识别结果。常用的评价指标有准确率(P)，召回率(R)是正确识别出的炒作微博数量占总炒作微博数量的比例，误报率(FP)是正常微博被识别为炒作微博的数量占总正常微博数量的比例，F1度量值是对P和R的加权调和平均，F1较高时说明实验方法比较理想，计算公式如下:

准确率

4．3 结果对比与分析

为验证模型的识别准确率，基于Matlab R2012a和LibSVM实验平台进行实验。每条微博提取出了6个特征，即:社团模块度、平均最短路径、关键用户关注好友平均粉丝数、关键用户关注好友平均声望值、关键用户平均声望值、关键用户平均关注数。提取社团模块度和平均最短路径构成2维特征向量Fcls2，微博的6个特征构成6维特征向量Fall。

实验使用PRO算法对支持向量机的模型的核参数和惩罚因子进行优化，为衡量PRO算法优化SVM的有效性，采用基于网格搜索法优化的SVM作为参比模型进行比较，然后以特征向量Fcls2和Fall作为2种模型的输入，采用十折交叉验证的方式进行评估，并依据3个评价指标比较分类结果的优劣，得到结果见表2和表3。

表2 采用不同的特征组合对炒作微博的SVM分类结果

表3 采用不同的特征组合对炒作微博的PSO-SVM分类结果

由表2和表3可以看出，使用6维组合特征向量的分类效果要优于2维特征向量。主要原因在于，一些明星粉丝之间的口水战和娱乐明星为了突出微博重要性而重复转发，造成微博在传播过程中的参与人群相对单一，传播层次少，从而使社团模块度较大和平均最短路径较小，最终被误识别为炒作微博，因此使用2维特征向量Fcls2分类效果较差。炒作微博中的节点用户质量与正常微博中的节点用户质量有着明显的区别，因此提取传播网络中的关键用户属性信息，组成6维特征向量Fall，用于衡量传播网络中用户和好友的质量，区分被误识别为炒作微博的正常微博，从而使分类准确率有较大提高。实验说明社团模块度和平均最短路径与关键用户属性特征具有优势互补的特性，两者结合更能体现炒作微博的特性，提高分类准确率。

对比SVM，使用PSO-SVM分类模型可以使炒作微博的分类准确率达到90%以上，并且误报率不到1%，F1度量值达到90%以上，说明PSO对SVM的参数优化具有明显的效果，PSO-SVM分类模型比较理想，能够高效地解决炒作微博的识别问题，为微博的健康发展提供支持。

5 结束语

对炒作微博的传播网络节点进行分析，基于社团模块度、平均最短路径和关键用户属性等特征，得出识别准确率较高的PSO-SVM分类模型，该模型使用PSO对SVM中的参数进行优化，避免了人为选择的随机性，使参数选择更合理。实验结果表明，文中方法能有效地识别出炒作微博，准确率达到90%以上，具有一定的合理性和适用性，并且对明星或官方微博的影响因子进行了深度细化，能够较好克服微博名人效应对识别准确率的干扰。

［1］ 任一其，王雅雷，王国华，等.微博谣言的演化机理研究［J］.情报杂志，2012，31(5)：50-54.

［2］ 齐海凤.网络舆情热点发现与事件跟踪技术研究［D］.哈尔滨：哈尔滨工程大学，2008.

［3］ Dimitrios C，Takis K.Wavelet-based rotational invariant roughness features for texture classification and segmentation［J］.IEEE Transactions on Image Processing a Publication of the IEEE Signal Processing Society，2002，11(8)：825-837.

［4］ Cortes C，Vapnik V.Support-Vector Networks［J］.Machine Learning，1995，20(3)：273-297.

［5］ Burges C J C.A Tutorial on Support Vector Machines for Pattern Recognition［J］.Data Mining ＆Knowledge Discovery，1998，2(2)：121-167.

［6］ 高锦.基于SVM的图像分类［D］.西安：西北大学，2010.

［7］ KENNEDY J，EBERHART R.Particle swarm optimization［C］.Proc of IEEE International Conference on Neural Networks.Piscataway：IEEE Press，1995：1942-1948.

［8］ MATLAB中文论坛.MATLAB神经网络30个案例分析［M］.北京：北京航空航天大学出版社，2010.

［9］ Newman M E J，Girvan M.Finding and evaluating community structure in networks［J］.Physical Review E Statistical Nonlinear＆Soft Matter Physics，2004，69：026-113.

［10］ LüL，Chen D B，Zhou T.Small world yields the most effective information spreading ［J］.New Journal of Physics，2011，(9-10)：825-834.

［11］ 张进，刘琰，罗军勇，等.基于特征分析的微博炒作账户识别方法［J］.计算机工程，2015，(4)：48-54.

［12］ 邓乃扬.数据挖掘中的新方法［M］.北京：科学出版社，2004.

［13］ 周辉仁，郑丕谔，王嵩，等.基于粒子群优化算法LS-SVM财务预警［J］.计算机工程，2009，35(10)：280-282.

［14］ Girvan M，Newman M E J.Community structure in social and biological networks［J］.Proceedings of the National Academy of Sciences of the United States of America，2001，99(12)：7821-7826.

［15］ Newman M E J，Watts D J.Renormalization group analysis of the small-world network model［J］.Physics Letters A，1999，263(4)：341-346.

［16］ Bu Z，Xia Z，Wang J.A sock puppet detection algorithm on virtual spaces［J］.Knowledge-Based Systems，2013，37(2)：366-377.

［17］ 袁立庠.微博的传播模式与传播效果［J］.安徽师范大学学报：人文社会科学版，2011，39(6)：678-683.

［18］ 汪小帆，刘亚冰.复杂网络中的社团结构算法综述［J］.电子科技大学学报，2009，38(5)：537-543.