基于复杂网络理论的舆情检测算法研究

童文利，邵剑飞，李　平

(昆明理工大学 信息工程与自动化学院，云南 昆明 650500 )



基于复杂网络理论的舆情检测算法研究

童文利，邵剑飞，李平

(昆明理工大学 信息工程与自动化学院，云南 昆明 650500 )

摘要：目前，已存在的舆情检测算法主要基于网络文本的数据信息，而未考虑网络时间因素对信息元素权重的影响。针对舆情检测算法中网页爬取时间同步问题，提出了基于复杂网络理论的舆情检测算法，构建了复杂网络模型，提出了改进TPSN算法(即TPSN-LS算法)，并应用NS2进行了仿真分析。由仿真结果可知，TPSN-LS算法在网络爬取负载、同步精度和同步次数等方面的性能都明显优于TPSN算法，使得舆情检测的结果更加准确。

关键词：舆情检测；复杂网络理论；信息节点；网络延时

舆情检测是政府部门掌握社会价值体系和保障网络整体安全的重要手段。加强对网络话题热点信息和传播规律的检测是非常有必要的。目前，对于网络话题检测技术的研究主要集中在2个方面：1)侧重于网络内容，即对网络结构、内容和传播规律的检测，以此建立预测模型来推理话题趋势[1]；2)侧重于话题关键字，即网络文本信息的检测，这类研究主要是通过数据挖掘算法的特征提取、聚类来实现的[2]。这2类话题检测技术研究都是以网络数据信息为基础的，而未考虑因特网自身的特性。

本文针对上述问题，结合复杂网络理论，提出基于改进最小二乘估计法的时间同步网络舆情检测算法。

1基于复杂网络模型的舆情检测算法改进

复杂网络理论是构建在系统的基础上的，它将某类具有相似特性的系统以图论中的边、度和点等形式构建成一个相互关联并依赖的网络系统[3]。

1.1网络模型构建

因特网的复杂网络构建可以将网页看作是网络中的节点，将超链接看作是节点的相互关系，即复杂网络中的边。节点的边越多，表示该节点在网络中的权重越大，也就是该网页受关注程度较高，也就有较大概率出现热点信息元素。

本文将因特网构建成由节点和边作为元素的二元数据模型〈V,R〉，V是网络中所有网页的集合，R是集合V上节点关系的集合。在集合V中，采集的最基本信息点是话题信息条目，不同的话题信息条目对应着模型中的实体对象，集合R是集合V中所有节点的关系集合。

1.2因特网复杂网络模型时间同步

时间同步机制主要基于R-R、P-W和S-R等3类，基于P-W的时间同步机制是指具有本地独立时钟的节点成对地保持独立时钟的相对时间一致，且存储所有节点与其本身的时间偏差信息。对于节点数量较大且变化频率较高的网络结构，通常采用基于P-W的机制来解决网络的时间同步问题。基于P-W同步机制的优势在于其同步精度较高，且同步精度不会因为网络规模的扩大而降低，这也正符合因特网复杂网络模型的网络特性；因此，本文选取基于P-W的TPSN时间同步算法来研究因特网复杂网络模型的时间同步问题[4-5]。

1.3TPSN算法改进

结合因特网复杂网络时间同步需求和TPSN算法的时间同步特性可以看出，现有的TPSN虽然具有同步精度高的特点，但是由于在因特网复杂的网络中，网络节点数量过大，网络层级较多[6]；因此，逐层之间产生的同步误差会不断叠加，会对同步精度造成较大的影响。

复杂网络节点在任意时刻都会由于自身的差异性产生时钟偏移，导致这些网页节点产生时钟漂移的主要原因是大部分的网页是基于服务器搭建的，各地服务器的系统时间是存在差异性的，因此，导致了网页节点间本地时钟不一致。TPSN算法中的误差由确定性部分传输延迟和不确定性部分时间偏差所组成，所以TPSN算法中非确定性部分包括时间偏差和时钟漂移[7]。为了提高同步精度，下述采用最小二乘估计法和自适应周期同步法对TPSN算法进行改进，以减小不确定部分引起的同步误差。为了表达方便，本文将改进后的TPSN算法称为TPSN-LS。

(1)

由式1可得：

(2)

式中，T1、T3和T4是本地时钟时间。

为了求时间偏差和时间漂移，建立数学模型：

(3)

式中，α是2节点相应的时间漂移；σ是时间偏差。

令i(i=1,2,…,n)为第i次同步，那么式3可整理为：

(4)

上述方程有2个参数：α和σ。这里用最小二乘估计求未知参数。

yi=αxi+σ

(5)

估计值与实际值的离差为：

(6)

离差平方和为：

(7)

(8)

(9)

即：

(10)

(11)

(12)

(13)

节点2可以利用计算出来的时间偏差值σ和时间漂移α来修正自身的本地时间，达到与节点1同步。

根据参数估计模型，选择同步100次的时间统计值，即100组时间标记的值，每组数据中都包含一组T1、T2、T3和T4的值，每次同步都会产生一个同步误差，采用最小二乘估计前后TPSN算法在不同同步次数时的同步误差比较图如图1所示。

图1　不同同步次数下的时间同步误差

由图1可以看出，改进后算法的同步误差在前20次波动较大，其均值约为20 μs，在同步20次后，其时间偏差趋于10 μs，基本不再波动；因此，TPSN-LS算法时间偏差为10 μs，小于TPSN算法的同步误差(16 μs)。采用改进后的最小二乘估计法，提高了算法精度。

2数据仿真分析

本文采用NS2的仿真平台，针对舆情检测时网页爬取所产生的时间同步误差，TPSN-LS算法的性能进行试验[8-9]。

2.1改进前后算法的时间漂移对比

通过提取NS2的trace文件数据，得到了改进前后算法的时间漂移比较图(见图2)。由图2可以看出，当迭代次数达到100时，TPSN的时间偏差几乎仍然处于波动较大状态，并没有随着迭代次数的增大而降低，TPSN-LS算法在迭代次数达到20以后，其时间偏差保持在约为10 μs。

图2　时间偏差算法仿真结果

2.2不同节点个数时同步次数和网页爬取负载的比较

当网络中的节点个数不一致时，可以看出改进后的算法在同步的次数和负载消耗上都有所减少，具体如图3所示。

图3　不同节点个数时同步次数和网页爬取负载消耗的比较

从上述仿真结果可以看出，在不同仿真条件下，TPSN-LS算法的同步次数和同步精度都远远优于TPSN算法，因此，对于TPSN-LS算法的改进方案是可行的；同时可以看出，TPSN-LS算法在网络爬取负载、同步精度和次数等方面的性能都明显优于TPSN算法，缩小了复杂网络节点间的时间偏差，TPSN-LS算法使得舆情检测的结果更加准确。

3结语

本文舆情检测算法研究的目的是在网络抽象成复杂网络的模型中，降低网络时延的影响。以TPSN算法为基础，结合复杂网络模型，改进得到了TPSN-LS算法，并在不同条件下进行了仿真分析，结果说明了其在性能方面的优越性和良好的应用前景。

参考文献

[1] 阳韬．无线传感网络时间同步协议现状研究[J].电脑知识与技术，2011,7(28):6859-6861.

[2] 陈伊卿．无线传感器网络时间同步算法研究[D].西安：西安电子科技大学，2011．

[3] 董勐．云服务聚合中的访问控制中访问控制策略分解与策略分解与实施[D].武汉：华中科技大学，2012.

[4] 邹乐强.最小二乘法原理及其简单应用[J].科技信息，2010(23):282-283.

[5] 王秋鹏.无线传感器网络能量优化技术[J]. 新技术新工艺, 2014(8): 84-86.

[6] 曾雪．海量数据的快速查询算法研究[D].南京：南京邮电大学，2012.

[7] 戚龙飞．分布式无线网络时间同步协议设计与建模优化[D].南京：南京航空航天大学，2013．

[8] 李飞，白凤山，张春梅，等．基于NS2的TPSN协议的移植[J].内蒙古大学学报，2014，45(1):60-62．

[9] 方路平，刘世华，陈盼，等．NS2网路模拟基础与应用[M].北京：国防工业出版社,2008．

责任编辑郑练

Public Opinion Detection Algorithm based on the Complex Network Theory

TONG Wenli, SHAO Jianfei, LI Ping

(Faculty of Information and Automation, Kunming University of Science and Technology, Kunming 650500, China)

Abstract：At present, the public opinion detection algorithms is almost based on data of the web text, and never considered the time factor of network, which impacts the information element weights. Public opinion detection algorithm based on the complex network is proposed, based on the time synchronization problem of web crawling in public opinion detection algorithm, construct a complex network model, and improve the TPNS algorithm, which is TPNS-LS algorithm. Finally, analyze the simulation on NS2. The simulation results show that, the improved TPSN-LS algorithm is much better than TPSN algorithm, on the performance of crawling load on the network, synchronization accuracy and synchronization times and other aspects. The research makes public opinion detection more accurate.

Key words:public opinion testing, complex network theory, information node, network delay

收稿日期：2015-08-11

作者简介：童文利(1989-)，男，硕士研究生，主要从事通信与信息系统等方面的研究。

中图分类号：TP 301.6

文献标志码:A