基于復(fù)雜網(wǎng)絡(luò)理論的輿情檢測(cè)算法研究

童文利，邵劍飛，李　平

(昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院，云南 昆明 650500 )

?

基于復(fù)雜網(wǎng)絡(luò)理論的輿情檢測(cè)算法研究

童文利，邵劍飛，李平

(昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院，云南 昆明 650500 )

摘要：目前，已存在的輿情檢測(cè)算法主要基于網(wǎng)絡(luò)文本的數(shù)據(jù)信息，而未考慮網(wǎng)絡(luò)時(shí)間因素對(duì)信息元素權(quán)重的影響。針對(duì)輿情檢測(cè)算法中網(wǎng)頁(yè)爬取時(shí)間同步問題，提出了基于復(fù)雜網(wǎng)絡(luò)理論的輿情檢測(cè)算法，構(gòu)建了復(fù)雜網(wǎng)絡(luò)模型，提出了改進(jìn)TPSN算法(即TPSN-LS算法)，并應(yīng)用NS2進(jìn)行了仿真分析。由仿真結(jié)果可知，TPSN-LS算法在網(wǎng)絡(luò)爬取負(fù)載、同步精度和同步次數(shù)等方面的性能都明顯優(yōu)于TPSN算法，使得輿情檢測(cè)的結(jié)果更加準(zhǔn)確。

關(guān)鍵詞：輿情檢測(cè)；復(fù)雜網(wǎng)絡(luò)理論；信息節(jié)點(diǎn)；網(wǎng)絡(luò)延時(shí)

輿情檢測(cè)是政府部門掌握社會(huì)價(jià)值體系和保障網(wǎng)絡(luò)整體安全的重要手段。加強(qiáng)對(duì)網(wǎng)絡(luò)話題熱點(diǎn)信息和傳播規(guī)律的檢測(cè)是非常有必要的。目前，對(duì)于網(wǎng)絡(luò)話題檢測(cè)技術(shù)的研究主要集中在2個(gè)方面：1)側(cè)重于網(wǎng)絡(luò)內(nèi)容，即對(duì)網(wǎng)絡(luò)結(jié)構(gòu)、內(nèi)容和傳播規(guī)律的檢測(cè)，以此建立預(yù)測(cè)模型來推理話題趨勢(shì)[1]；2)側(cè)重于話題關(guān)鍵字，即網(wǎng)絡(luò)文本信息的檢測(cè)，這類研究主要是通過數(shù)據(jù)挖掘算法的特征提取、聚類來實(shí)現(xiàn)的[2]。這2類話題檢測(cè)技術(shù)研究都是以網(wǎng)絡(luò)數(shù)據(jù)信息為基礎(chǔ)的，而未考慮因特網(wǎng)自身的特性。

本文針對(duì)上述問題，結(jié)合復(fù)雜網(wǎng)絡(luò)理論，提出基于改進(jìn)最小二乘估計(jì)法的時(shí)間同步網(wǎng)絡(luò)輿情檢測(cè)算法。

1基于復(fù)雜網(wǎng)絡(luò)模型的輿情檢測(cè)算法改進(jìn)

復(fù)雜網(wǎng)絡(luò)理論是構(gòu)建在系統(tǒng)的基礎(chǔ)上的，它將某類具有相似特性的系統(tǒng)以圖論中的邊、度和點(diǎn)等形式構(gòu)建成一個(gè)相互關(guān)聯(lián)并依賴的網(wǎng)絡(luò)系統(tǒng)[3]。

1.1網(wǎng)絡(luò)模型構(gòu)建

因特網(wǎng)的復(fù)雜網(wǎng)絡(luò)構(gòu)建可以將網(wǎng)頁(yè)看作是網(wǎng)絡(luò)中的節(jié)點(diǎn)，將超鏈接看作是節(jié)點(diǎn)的相互關(guān)系，即復(fù)雜網(wǎng)絡(luò)中的邊。節(jié)點(diǎn)的邊越多，表示該節(jié)點(diǎn)在網(wǎng)絡(luò)中的權(quán)重越大，也就是該網(wǎng)頁(yè)受關(guān)注程度較高，也就有較大概率出現(xiàn)熱點(diǎn)信息元素。

本文將因特網(wǎng)構(gòu)建成由節(jié)點(diǎn)和邊作為元素的二元數(shù)據(jù)模型〈V,R〉，V是網(wǎng)絡(luò)中所有網(wǎng)頁(yè)的集合，R是集合V上節(jié)點(diǎn)關(guān)系的集合。在集合V中，采集的最基本信息點(diǎn)是話題信息條目，不同的話題信息條目對(duì)應(yīng)著模型中的實(shí)體對(duì)象，集合R是集合V中所有節(jié)點(diǎn)的關(guān)系集合。

1.2因特網(wǎng)復(fù)雜網(wǎng)絡(luò)模型時(shí)間同步

時(shí)間同步機(jī)制主要基于R-R、P-W和S-R等3類，基于P-W的時(shí)間同步機(jī)制是指具有本地獨(dú)立時(shí)鐘的節(jié)點(diǎn)成對(duì)地保持獨(dú)立時(shí)鐘的相對(duì)時(shí)間一致，且存儲(chǔ)所有節(jié)點(diǎn)與其本身的時(shí)間偏差信息。對(duì)于節(jié)點(diǎn)數(shù)量較大且變化頻率較高的網(wǎng)絡(luò)結(jié)構(gòu)，通常采用基于P-W的機(jī)制來解決網(wǎng)絡(luò)的時(shí)間同步問題?；赑-W同步機(jī)制的優(yōu)勢(shì)在于其同步精度較高，且同步精度不會(huì)因?yàn)榫W(wǎng)絡(luò)規(guī)模的擴(kuò)大而降低，這也正符合因特網(wǎng)復(fù)雜網(wǎng)絡(luò)模型的網(wǎng)絡(luò)特性；因此，本文選取基于P-W的TPSN時(shí)間同步算法來研究因特網(wǎng)復(fù)雜網(wǎng)絡(luò)模型的時(shí)間同步問題[4-5]。

1.3TPSN算法改進(jìn)

結(jié)合因特網(wǎng)復(fù)雜網(wǎng)絡(luò)時(shí)間同步需求和TPSN算法的時(shí)間同步特性可以看出，現(xiàn)有的TPSN雖然具有同步精度高的特點(diǎn)，但是由于在因特網(wǎng)復(fù)雜的網(wǎng)絡(luò)中，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量過大，網(wǎng)絡(luò)層級(jí)較多[6]；因此，逐層之間產(chǎn)生的同步誤差會(huì)不斷疊加，會(huì)對(duì)同步精度造成較大的影響。

復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)在任意時(shí)刻都會(huì)由于自身的差異性產(chǎn)生時(shí)鐘偏移，導(dǎo)致這些網(wǎng)頁(yè)節(jié)點(diǎn)產(chǎn)生時(shí)鐘漂移的主要原因是大部分的網(wǎng)頁(yè)是基于服務(wù)器搭建的，各地服務(wù)器的系統(tǒng)時(shí)間是存在差異性的，因此，導(dǎo)致了網(wǎng)頁(yè)節(jié)點(diǎn)間本地時(shí)鐘不一致。TPSN算法中的誤差由確定性部分傳輸延遲和不確定性部分時(shí)間偏差所組成，所以TPSN算法中非確定性部分包括時(shí)間偏差和時(shí)鐘漂移[7]。為了提高同步精度，下述采用最小二乘估計(jì)法和自適應(yīng)周期同步法對(duì)TPSN算法進(jìn)行改進(jìn)，以減小不確定部分引起的同步誤差。為了表達(dá)方便，本文將改進(jìn)后的TPSN算法稱為TPSN-LS。

(1)

由式1可得：

(2)

式中，T1、T3和T4是本地時(shí)鐘時(shí)間。

為了求時(shí)間偏差和時(shí)間漂移，建立數(shù)學(xué)模型：

(3)

式中，α是2節(jié)點(diǎn)相應(yīng)的時(shí)間漂移；σ是時(shí)間偏差。

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

(4)

上述方程有2個(gè)參數(shù)：α和σ。這里用最小二乘估計(jì)求未知參數(shù)。

yi=αxi+σ

(5)

估計(jì)值與實(shí)際值的離差為：

(6)

離差平方和為：

(7)

(8)

(9)

即：

(10)

(11)

(12)

(13)

節(jié)點(diǎn)2可以利用計(jì)算出來的時(shí)間偏差值σ和時(shí)間漂移α來修正自身的本地時(shí)間，達(dá)到與節(jié)點(diǎn)1同步。

根據(jù)參數(shù)估計(jì)模型，選擇同步100次的時(shí)間統(tǒng)計(jì)值，即100組時(shí)間標(biāo)記的值，每組數(shù)據(jù)中都包含一組T1、T2、T3和T4的值，每次同步都會(huì)產(chǎn)生一個(gè)同步誤差，采用最小二乘估計(jì)前后TPSN算法在不同同步次數(shù)時(shí)的同步誤差比較圖如圖1所示。

圖1　不同同步次數(shù)下的時(shí)間同步誤差

由圖1可以看出，改進(jìn)后算法的同步誤差在前20次波動(dòng)較大，其均值約為20 μs，在同步20次后，其時(shí)間偏差趨于10 μs，基本不再波動(dòng)；因此，TPSN-LS算法時(shí)間偏差為10 μs，小于TPSN算法的同步誤差(16 μs)。采用改進(jìn)后的最小二乘估計(jì)法，提高了算法精度。

2數(shù)據(jù)仿真分析

本文采用NS2的仿真平臺(tái)，針對(duì)輿情檢測(cè)時(shí)網(wǎng)頁(yè)爬取所產(chǎn)生的時(shí)間同步誤差，TPSN-LS算法的性能進(jìn)行試驗(yàn)[8-9]。

2.1改進(jìn)前后算法的時(shí)間漂移對(duì)比

通過提取NS2的trace文件數(shù)據(jù)，得到了改進(jìn)前后算法的時(shí)間漂移比較圖(見圖2)。由圖2可以看出，當(dāng)?shù)螖?shù)達(dá)到100時(shí)，TPSN的時(shí)間偏差幾乎仍然處于波動(dòng)較大狀態(tài)，并沒有隨著迭代次數(shù)的增大而降低，TPSN-LS算法在迭代次數(shù)達(dá)到20以后，其時(shí)間偏差保持在約為10 μs。

圖2　時(shí)間偏差算法仿真結(jié)果

2.2不同節(jié)點(diǎn)個(gè)數(shù)時(shí)同步次數(shù)和網(wǎng)頁(yè)爬取負(fù)載的比較

當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)個(gè)數(shù)不一致時(shí)，可以看出改進(jìn)后的算法在同步的次數(shù)和負(fù)載消耗上都有所減少，具體如圖3所示。

圖3　不同節(jié)點(diǎn)個(gè)數(shù)時(shí)同步次數(shù)和網(wǎng)頁(yè)爬取負(fù)載消耗的比較

從上述仿真結(jié)果可以看出，在不同仿真條件下，TPSN-LS算法的同步次數(shù)和同步精度都遠(yuǎn)遠(yuǎn)優(yōu)于TPSN算法，因此，對(duì)于TPSN-LS算法的改進(jìn)方案是可行的；同時(shí)可以看出，TPSN-LS算法在網(wǎng)絡(luò)爬取負(fù)載、同步精度和次數(shù)等方面的性能都明顯優(yōu)于TPSN算法，縮小了復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)間的時(shí)間偏差，TPSN-LS算法使得輿情檢測(cè)的結(jié)果更加準(zhǔn)確。

3結(jié)語(yǔ)

本文輿情檢測(cè)算法研究的目的是在網(wǎng)絡(luò)抽象成復(fù)雜網(wǎng)絡(luò)的模型中，降低網(wǎng)絡(luò)時(shí)延的影響。以TPSN算法為基礎(chǔ)，結(jié)合復(fù)雜網(wǎng)絡(luò)模型，改進(jìn)得到了TPSN-LS算法，并在不同條件下進(jìn)行了仿真分析，結(jié)果說明了其在性能方面的優(yōu)越性和良好的應(yīng)用前景。

參考文獻(xiàn)

[1] 陽(yáng)韜．無(wú)線傳感網(wǎng)絡(luò)時(shí)間同步協(xié)議現(xiàn)狀研究[J].電腦知識(shí)與技術(shù)，2011,7(28):6859-6861.

[2] 陳伊卿．無(wú)線傳感器網(wǎng)絡(luò)時(shí)間同步算法研究[D].西安：西安電子科技大學(xué)，2011．

[3] 董勐．云服務(wù)聚合中的訪問控制中訪問控制策略分解與策略分解與實(shí)施[D].武漢：華中科技大學(xué)，2012.

[4] 鄒樂強(qiáng).最小二乘法原理及其簡(jiǎn)單應(yīng)用[J].科技信息，2010(23):282-283.

[5] 王秋鵬.無(wú)線傳感器網(wǎng)絡(luò)能量?jī)?yōu)化技術(shù)[J]. 新技術(shù)新工藝, 2014(8): 84-86.

[6] 曾雪．海量數(shù)據(jù)的快速查詢算法研究[D].南京：南京郵電大學(xué)，2012.

[7] 戚龍飛．分布式無(wú)線網(wǎng)絡(luò)時(shí)間同步協(xié)議設(shè)計(jì)與建模優(yōu)化[D].南京：南京航空航天大學(xué)，2013．

[8] 李飛，白鳳山，張春梅，等．基于NS2的TPSN協(xié)議的移植[J].內(nèi)蒙古大學(xué)學(xué)報(bào)，2014，45(1):60-62．

[9] 方路平，劉世華，陳盼，等．NS2網(wǎng)路模擬基礎(chǔ)與應(yīng)用[M].北京：國(guó)防工業(yè)出版社,2008．

責(zé)任編輯鄭練

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

作者簡(jiǎn)介：童文利(1989-)，男，碩士研究生，主要從事通信與信息系統(tǒng)等方面的研究。

中圖分類號(hào)：TP 301.6

文獻(xiàn)標(biāo)志碼:A