基于改進(jìn)Floyd算法的網(wǎng)絡(luò)輿情監(jiān)測(cè)

李金澤,武文豪,李開(kāi)航

(1.中國(guó)人民警察大學(xué),河北 廊坊 065000； 2.濟(jì)南大學(xué),山東 濟(jì)南 250000； 3.山東青年政治學(xué)院,山東 濟(jì)南 250000)

0 引 言

隨著互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，人們獲取信息的方式已經(jīng)突破了時(shí)間空間的限制，在網(wǎng)絡(luò)大環(huán)境中，任何信息都可以在電腦上被查詢到[1-3]?；ヂ?lián)網(wǎng)信息具有多樣化與全球性的特點(diǎn)，并且擁有著前所未有的獨(dú)特環(huán)境[4]。在這個(gè)獨(dú)特的環(huán)境中，人們逐漸適應(yīng)了這種新型的傳播介質(zhì)，開(kāi)始愿意在互聯(lián)網(wǎng)中表達(dá)自己的意愿，網(wǎng)絡(luò)輿情已經(jīng)逐步開(kāi)始替代傳統(tǒng)的社會(huì)輿情[5]。網(wǎng)絡(luò)輿情反映了互聯(lián)網(wǎng)時(shí)代的獨(dú)特輿論，其反映的是人們?cè)诨ヂ?lián)網(wǎng)的意愿，屬于輿情的一種表現(xiàn)形式，也是輿情在特殊渠道上的表達(dá)[6]。因?yàn)榫W(wǎng)絡(luò)輿情是建立在互聯(lián)網(wǎng)的互動(dòng)性與開(kāi)放性的基礎(chǔ)上，所以網(wǎng)絡(luò)輿情不僅擁有自身的獨(dú)特性，同時(shí)也具有傳統(tǒng)輿情的特征。輿情通常被理解為民意的綜合表達(dá)，有時(shí)也會(huì)被描述為輿論的綜合表現(xiàn)[7]。無(wú)論怎樣對(duì)輿情進(jìn)行理解，其大致的含義都不會(huì)有偏差，即群眾的意見(jiàn)與態(tài)度?；ヂ?lián)網(wǎng)發(fā)展至今，仍然有較多的政府工作人員還不適應(yīng)互聯(lián)網(wǎng)的應(yīng)用，并不重視網(wǎng)絡(luò)輿論，以致在網(wǎng)絡(luò)輿情檢測(cè)與收集上的體制不完善，并不能及時(shí)應(yīng)對(duì)網(wǎng)絡(luò)輿情危機(jī)，這些都阻礙了政府管理能力和辦公效率的提升[8]。網(wǎng)絡(luò)輿情監(jiān)測(cè)工作的革新與發(fā)展已經(jīng)上升至對(duì)負(fù)面輿情信息載體類型分布及輿情內(nèi)容構(gòu)成的研究,進(jìn)而對(duì)我國(guó)政府輿情工作存在的不足提出建議[9]。為了使我國(guó)政府機(jī)關(guān)在互聯(lián)網(wǎng)環(huán)境中的輿情管理能力得到提升，國(guó)內(nèi)學(xué)者通過(guò)應(yīng)用先進(jìn)的監(jiān)控技術(shù)與分析方法，以達(dá)到掌握群眾思想動(dòng)態(tài)的目的[10]。國(guó)外對(duì)網(wǎng)絡(luò)輿情監(jiān)測(cè)方面的研究起步較早，輿情分析技術(shù)與熱點(diǎn)發(fā)現(xiàn)，目前國(guó)外對(duì)話題的跟蹤與檢測(cè)，以及文本傾向性分析技術(shù)是當(dāng)前最為常見(jiàn)的2大內(nèi)容。因此，本文探討基于改進(jìn)Floyd算法的網(wǎng)絡(luò)輿情監(jiān)測(cè)，重點(diǎn)加強(qiáng)對(duì)網(wǎng)絡(luò)輿論的分析，達(dá)到能夠應(yīng)對(duì)社會(huì)突發(fā)事件的能力，保證社會(huì)的穩(wěn)定發(fā)展。

1 Floyd算法的內(nèi)涵

由于本文主要是針對(duì)URL參數(shù)和鏈路的耗時(shí)進(jìn)行優(yōu)化，從而達(dá)到全局優(yōu)化的目的，該方式與Floyd算法根據(jù)某一節(jié)點(diǎn)求取另一節(jié)點(diǎn)最短路徑的方式不謀而合。對(duì)于Floyd算法的基本思想而言，應(yīng)該從單源最短路徑和任意定點(diǎn)間的最短路徑入手進(jìn)行探討[11]。若存在賦權(quán)有向圖G=(V,E)，將G中的弧aij=(vi,vj)上的權(quán)定義為W(aij)=Wij，將s和t分別定義為G的起點(diǎn)和終點(diǎn)，設(shè)G中s到達(dá)t的路程為p，定義p內(nèi)有弧的權(quán)之和為p的權(quán)，記作W(p)，那么:

(1)

再設(shè)G中s到達(dá)t的一條最短路程為p*，那么

W(p*)=min{W(p)|p為s到t的路程}

(2)

其中，取p值的最小值，即s到t的最短路程為p*，那么W(p*)則表示s到t的最短距離。在賦權(quán)有向圖G中，求s到t的最短路程就是在求解最短路徑問(wèn)題。

Floyd算法的計(jì)算開(kāi)始于D0，通過(guò)D0對(duì)D1進(jìn)行計(jì)算，再通過(guò)D1對(duì)D2進(jìn)行計(jì)算，以此類推，最終通過(guò)DN-1計(jì)算出DN。計(jì)算方式如下：

(3)

2 基于改進(jìn)Floyd算法的模型構(gòu)建

2.1 基于改進(jìn)Floyd算法的控制策略

在分析網(wǎng)絡(luò)輿情時(shí)，首先要對(duì)網(wǎng)絡(luò)文本進(jìn)行抓取，并對(duì)行為特征進(jìn)行分析，將不同的行為特征進(jìn)行分類，以根據(jù)不同的行為類型進(jìn)行網(wǎng)絡(luò)輿情檢測(cè)[15]。標(biāo)準(zhǔn)Floyd算法是將節(jié)點(diǎn)之間的權(quán)值作為運(yùn)算變量，對(duì)抓取相應(yīng)文本并進(jìn)行分析的這種較為復(fù)雜的網(wǎng)絡(luò)輿情檢測(cè)似乎有些不合時(shí)宜[16]。所以，本文對(duì)Floyd算法進(jìn)行改進(jìn)。標(biāo)準(zhǔn)Floyd算法的變量具有單一性，以路徑作為計(jì)算結(jié)果，并在準(zhǔn)確的數(shù)據(jù)源中提取出數(shù)據(jù)中的熱門(mén)主題，分析其潛在輿情[17]。本文的改進(jìn)算法將權(quán)值設(shè)定為可變的，依據(jù)系統(tǒng)的實(shí)時(shí)變化對(duì)權(quán)值進(jìn)行動(dòng)態(tài)調(diào)整，同時(shí)節(jié)點(diǎn)有一定的靈動(dòng)性，并附帶節(jié)點(diǎn)信息。Floyd算法對(duì)最短路徑進(jìn)行計(jì)算時(shí)，主要是運(yùn)用每個(gè)節(jié)點(diǎn)的弧度值。但在進(jìn)行網(wǎng)絡(luò)輿情的檢測(cè)時(shí)，要依據(jù)每個(gè)節(jié)點(diǎn)信息和網(wǎng)絡(luò)的實(shí)時(shí)延遲信息對(duì)最小耗時(shí)進(jìn)行獲取，使得媒體信息匹配與搜索的效率進(jìn)一步提高[18]。網(wǎng)絡(luò)輿情檢測(cè)系統(tǒng)可以較好地統(tǒng)籌協(xié)調(diào)子系統(tǒng)和整體系統(tǒng)，進(jìn)而優(yōu)化系統(tǒng)的性能，有效的早期監(jiān)測(cè)預(yù)警是防范突發(fā)事件網(wǎng)絡(luò)輿情蔓延擴(kuò)散的前提條件[19]。

(4)

對(duì)子系統(tǒng)進(jìn)行實(shí)時(shí)定位時(shí)，要根據(jù)當(dāng)前網(wǎng)段與單元智能體的反饋信息進(jìn)行確定，相鄰子系統(tǒng)會(huì)接收到子系統(tǒng)的實(shí)時(shí)定位信息，其他相鄰的子系統(tǒng)也會(huì)根據(jù)這個(gè)原理評(píng)估子系統(tǒng)之間的相互關(guān)聯(lián)性，以對(duì)數(shù)據(jù)信息進(jìn)行構(gòu)建，提高數(shù)據(jù)查詢的效率[21]。具體的表達(dá)式如式(5)：

IS=h(UNS,NNL,CCS,Γi,j)

(5)

其中，IS表示網(wǎng)段智能體定位信息；CCS表示內(nèi)容主題集；NNL表示網(wǎng)絡(luò)延遲值；UNS表示網(wǎng)絡(luò)穩(wěn)定值。網(wǎng)段相鄰的智能體可以協(xié)調(diào)控制相鄰的網(wǎng)段，可以在宏觀上將網(wǎng)段智能體看作是單個(gè)的節(jié)點(diǎn)，而相鄰節(jié)點(diǎn)可以用相鄰網(wǎng)段智能體來(lái)表示[22]。如式(6)所示，對(duì)每個(gè)弧度的耗時(shí)進(jìn)行計(jì)算后，以對(duì)搜索方案進(jìn)行合理的制定。

(6)

系統(tǒng)整體協(xié)調(diào)策略主要是在獲取子系統(tǒng)信息后，先對(duì)子系統(tǒng)的定位信息進(jìn)行獲取，并對(duì)比子系統(tǒng)之前的定位信息。根據(jù)定位信息的差距大小，分別作出相應(yīng)的標(biāo)記。由于每個(gè)子系統(tǒng)在全局智能體中，都可以看出是節(jié)點(diǎn)，因此各個(gè)子系統(tǒng)的耗時(shí)計(jì)算方法如式(7)：

(7)

2.2 Floyd改進(jìn)算法在網(wǎng)絡(luò)輿情中的應(yīng)用

如圖1所示，網(wǎng)絡(luò)輿情圖是由多個(gè)節(jié)點(diǎn)組成，圖1中共有9個(gè)URL節(jié)點(diǎn)。

圖1 網(wǎng)絡(luò)輿情圖

節(jié)點(diǎn)Ui到Uj所需要的時(shí)間可以用單權(quán)值βi表示，單權(quán)值βi又由2個(gè)節(jié)點(diǎn)間的差異所決定，如式(8)所示：

(8)

一般情況下，采用相鄰URL地址的弧度來(lái)表示相鄰節(jié)點(diǎn)間的Γi,j。對(duì)于節(jié)點(diǎn)1、節(jié)點(diǎn)2，Γi,j為節(jié)點(diǎn)1與節(jié)點(diǎn)2間的弧度大小，并且在不停地進(jìn)行變化，主要由β1、β2的取值來(lái)決定，如式(9)所示：

(9)

若采用ΓA,B表示搜索起點(diǎn)A到終點(diǎn)B的耗時(shí)，那么由Floyd算法推導(dǎo)出Γi,j的幾何形式如式(10)所示：

ΓA,B=f(Γ1,2,…,Γi,j)

(10)

在某些情況下，αi,j和ΓA,B也會(huì)有對(duì)應(yīng)的關(guān)聯(lián)，如式(11)所示：

ΓA,B=k×αi,j

(11)

對(duì)于Floyd算法在改進(jìn)后的文本分析，若存在字符串“你在哪里where”，將字符串看作是5個(gè)線性的節(jié)點(diǎn)，分別為“你”“在”“哪”“里”“where”5個(gè)節(jié)點(diǎn)，如圖2所示。

圖2 網(wǎng)絡(luò)輿情文本分析圖

圖2中，節(jié)點(diǎn)1、節(jié)點(diǎn)2不能構(gòu)成詞語(yǔ)，因此相關(guān)性較低，α取值較??；節(jié)點(diǎn)3、節(jié)點(diǎn)4則構(gòu)成詞語(yǔ)的可能性較高，因此相關(guān)性也較高，α取值較大。所以，節(jié)點(diǎn)路徑存在3種可能性，分別為1→2→5、1→2→3→5、1→2→3→4→5。1→2→5路徑雖然比較簡(jiǎn)單，但是具有較高的擴(kuò)展性；1→2→3→5要應(yīng)用算法的記憶功能，尤其是要預(yù)先知道節(jié)點(diǎn)3、節(jié)點(diǎn)4屬于詞語(yǔ)的情況；1→2→3→4→5是耗時(shí)最長(zhǎng)的算法，但是路徑卻最為可靠。

影響網(wǎng)絡(luò)輿情監(jiān)測(cè)技術(shù)的因素主要包括URL文本重用率、文本的正確率以及文本的有效率[23]。URL的有效率可以體現(xiàn)抓取URL地址時(shí)的效率和準(zhǔn)確率，反映了算法的有效性，表達(dá)式如式(12)所示：

(12)

對(duì)URL文本進(jìn)行分析衡量的一個(gè)重要指標(biāo)就是URL文本的準(zhǔn)確率，其表達(dá)式如式(13)所示：

(13)

URL文本重用率反映了各個(gè)URL之間的文本耦合度，若重用率低，則耦合度也低，表現(xiàn)出的性能就越好。其表達(dá)式如式(14)所示：

(14)

對(duì)于網(wǎng)絡(luò)輿情系統(tǒng)的評(píng)價(jià)而言，不但要評(píng)價(jià)不同實(shí)例間表現(xiàn)出的不同性能，也要對(duì)不同算法的時(shí)效性進(jìn)行對(duì)比[24]。

時(shí)效性主要對(duì)系統(tǒng)的便捷系數(shù)進(jìn)行衡量，以及體現(xiàn)算法的時(shí)空復(fù)雜度情況，其表達(dá)式如式(15)：

(15)

3 實(shí)驗(yàn)與分析

本文將本地實(shí)驗(yàn)機(jī)房的主機(jī)作為實(shí)驗(yàn)環(huán)境，并采用VLAN對(duì)子網(wǎng)進(jìn)行劃分，賦予各個(gè)主機(jī)不同的子網(wǎng)號(hào)與IP。創(chuàng)建測(cè)試網(wǎng)頁(yè)在不同的IP和網(wǎng)段上，其中包括了鏈接、視頻、音頻、圖片以及文本各種媒體信息。結(jié)合本文建立的模型，將模型參數(shù)定義為各種媒體信息。

圖3 網(wǎng)絡(luò)輿情監(jiān)測(cè)系統(tǒng)建模圖

如圖3所示，實(shí)驗(yàn)機(jī)房中包含了16臺(tái)主機(jī)，應(yīng)用VLAN將其劃分成4個(gè)子網(wǎng)，網(wǎng)段U1包括了A1和A5主機(jī)，網(wǎng)段U2包括了A4、A8和A12主機(jī)，網(wǎng)段U3包括了A6、A7、A10和A11主機(jī)，網(wǎng)段U4包括了A14、A15和A16主機(jī)。利用以上實(shí)驗(yàn)條件對(duì)本文提出的算法模型進(jìn)行驗(yàn)證。首先，應(yīng)用Floyd改進(jìn)算法對(duì)URL網(wǎng)頁(yè)中的文本進(jìn)行提取，并預(yù)處理獲取到的文本信息，最后通過(guò)Floyd改進(jìn)算法計(jì)算出實(shí)驗(yàn)結(jié)果。

表1 對(duì)比Floyd算法改進(jìn)前后的時(shí)效性

如表1所示，改進(jìn)后Floyd算法的時(shí)效性明顯優(yōu)于改進(jìn)前的算法。本文的網(wǎng)絡(luò)輿情相關(guān)數(shù)據(jù)均來(lái)自人民網(wǎng)和正義網(wǎng)正式發(fā)表的相關(guān)資料，以對(duì)提出的模型算法進(jìn)行驗(yàn)證。

表2 傳統(tǒng)single-pass、聚類算法、基于Floyd改進(jìn)算法的分析結(jié)果對(duì)比 單位：%

表2針對(duì)3種不同指標(biāo)對(duì)傳統(tǒng)single-pass算法、聚類算法以及基于Floyd改進(jìn)算法進(jìn)行了對(duì)比，發(fā)現(xiàn)Floyd改進(jìn)算法的各項(xiàng)指標(biāo)均明顯優(yōu)于其他算法。

如圖4所示，若只存在案例1和案例2時(shí)，案例較為精簡(jiǎn)，F(xiàn)loyd算法改進(jìn)前后的差異性較小。但隨著案例的增多，運(yùn)算逐漸趨于復(fù)雜，F(xiàn)loyd算法在改進(jìn)之后的時(shí)效性顯著優(yōu)于改進(jìn)前。

圖4 Floyd算法改進(jìn)前后的時(shí)效性對(duì)比

如圖5、圖6所示，在數(shù)據(jù)組較少時(shí)，F(xiàn)loyd改進(jìn)算法的有效率和準(zhǔn)確率明顯優(yōu)于其他算法；隨著數(shù)據(jù)的增加，F(xiàn)loyd改進(jìn)算法的有效率和準(zhǔn)確率優(yōu)勢(shì)逐漸變?nèi)?，但仍然?yōu)于其他算法。

圖5 各種算法的有效率對(duì)比

圖6 各種算法的準(zhǔn)確率對(duì)比

圖7 各種算法的重用率對(duì)比

如圖7所示，F(xiàn)loyd改進(jìn)算法的重用率明顯優(yōu)于其他算法，但當(dāng)實(shí)驗(yàn)數(shù)組達(dá)到一定上限時(shí)，仍然會(huì)出現(xiàn)重用率極限值。

4 結(jié)束語(yǔ)

本文在政府輿情監(jiān)測(cè)領(lǐng)域提出了基于Floyd改進(jìn)算法的控制策略與輿情監(jiān)測(cè)應(yīng)用模型，并針對(duì)3種不同指標(biāo)對(duì)傳統(tǒng)single-pass算法、聚類算法以及基于Floyd改進(jìn)算法進(jìn)行了對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，F(xiàn)loyd改進(jìn)算法的各項(xiàng)指標(biāo)均明顯優(yōu)于其他算法。其中，若案例數(shù)較少時(shí)，F(xiàn)loyd算法改進(jìn)前后的差異性較小。但隨著案例數(shù)的增多，運(yùn)算逐漸趨于復(fù)雜，F(xiàn)loyd算法在改進(jìn)之后的時(shí)效性顯著優(yōu)于改進(jìn)前；在數(shù)據(jù)組較少時(shí)，F(xiàn)loyd改進(jìn)算法的有效率和準(zhǔn)確率明顯優(yōu)于其他算法。隨著數(shù)據(jù)的增加，F(xiàn)loyd改進(jìn)算法的有效率和準(zhǔn)確率優(yōu)勢(shì)逐漸變?nèi)?，但仍然?yōu)于其他算法；Floyd改進(jìn)算法的重用率明顯優(yōu)于其他算法，但當(dāng)實(shí)驗(yàn)數(shù)組達(dá)到一定上限時(shí)，仍然會(huì)出現(xiàn)重用率極限值。由于Floyd算法自身具有較高的時(shí)間復(fù)雜度，應(yīng)用于大數(shù)據(jù)運(yùn)算時(shí)效果較差，本文對(duì)于Floyd算法關(guān)于數(shù)據(jù)量較大時(shí)的運(yùn)算探討較少，在今后的研究中，會(huì)更關(guān)注Floyd算法在數(shù)據(jù)量較大時(shí)的改進(jìn)優(yōu)化，期望今后在技術(shù)上能夠突破，開(kāi)發(fā)出更加完善的輿情分析系統(tǒng)。