童文利，邵劍飛，李　平

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

?

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

童文利，邵劍飛，李平

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

摘要：目前，已存在的輿情檢測算法主要基于網(wǎng)絡(luò)文本的數(shù)據(jù)信息，而未考慮網(wǎng)絡(luò)時間因素對信息元素權(quán)重的影響。針對輿情檢測算法中網(wǎng)頁爬取時間同步問題，提出了基于復(fù)雜網(wǎng)絡(luò)理論的輿情檢測算法，構(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算法，使得輿情檢測的結(jié)果更加準(zhǔn)確。

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

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

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

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

復(fù)雜網(wǎng)絡(luò)理論是構(gòu)建在系統(tǒng)的基礎(chǔ)上的，它將某類具有相似特性的系統(tǒng)以圖論中的邊、度和點等形式構(gòu)建成一個相互關(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)頁看作是網(wǎng)絡(luò)中的節(jié)點，將超鏈接看作是節(jié)點的相互關(guān)系，即復(fù)雜網(wǎng)絡(luò)中的邊。節(jié)點的邊越多，表示該節(jié)點在網(wǎng)絡(luò)中的權(quán)重越大，也就是該網(wǎng)頁受關(guān)注程度較高，也就有較大概率出現(xiàn)熱點信息元素。

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

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

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

1.3TPSN算法改進(jìn)

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

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

(1)

由式1可得：

(2)

式中，T1、T3和T4是本地時鐘時間。

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

(3)

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

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

(4)

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

yi=αxi+σ

(5)

估計值與實際值的離差為：

(6)

離差平方和為：

(7)

(8)

(9)

即：

(10)

(11)

(12)

(13)

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

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

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

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

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

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

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

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

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

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

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

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

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

3結(jié)語

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

參考文獻(xiàn)

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

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

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

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

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

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

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

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

[9] 方路平，劉世華，陳盼，等．NS2網(wǎng)路模擬基礎(chǔ)與應(yīng)用[M].北京：國防工業(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

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

中圖分類號：TP 301.6

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