張俊豪 鐵道警察學(xué)院

引言

本文以社交網(wǎng)絡(luò)為例，在蟻群算法的基礎(chǔ)上，研究分析用戶(hù)行為，找出消息從源頭流轉(zhuǎn)到特定人群的最優(yōu)傳播路徑，以期為公安輿情管控提供技術(shù)支持。

社交網(wǎng)絡(luò)是由用戶(hù)及用戶(hù)關(guān)系組成的，消息通過(guò)用戶(hù)之間的關(guān)系實(shí)現(xiàn)流轉(zhuǎn)，實(shí)際的交通網(wǎng)絡(luò)是由實(shí)體及實(shí)體之間的道路組成的，車(chē)輛通過(guò)實(shí)體之間的道路實(shí)現(xiàn)運(yùn)轉(zhuǎn)。兩者的拓?fù)浣Y(jié)構(gòu)較為相似，比如消息類(lèi)似于車(chē)輛，用戶(hù)關(guān)系類(lèi)似于道路，因此研究預(yù)測(cè)輿情消息傳播的最優(yōu)路徑可以借鑒實(shí)際生活中的道路尋優(yōu)算法蟻群算法[1]。但是社交網(wǎng)絡(luò)不同于實(shí)際的交通網(wǎng)絡(luò)，應(yīng)進(jìn)行實(shí)際的改進(jìn)，加以應(yīng)用，找出消息的最佳傳播路徑。

一、蟻群算法簡(jiǎn)介

蟻群算法是基于蟻群覓食行為的路徑尋優(yōu)算法，該算法是一種啟發(fā)式的全局優(yōu)化算法。在蟻群算法中，螞蟻之間通過(guò)信息素分享經(jīng)驗(yàn)，而且螞蟻會(huì)根據(jù)一定的概率pk(i,j)選擇下一條路徑，并在此路徑上釋放信息素[2]。pk(i,j)的確定是整個(gè)算法的核心，pk(i,j)的計(jì)算如式（1）所示：

式（1）中，τ(i,j)表示路徑(i,j)上的信息素濃度，其更新機(jī)制主要對(duì)應(yīng)三種模型：蟻密系統(tǒng)、蟻周系統(tǒng)和蟻量系統(tǒng)，η(i,j)表示第k只螞蟻的啟發(fā)式函數(shù)，其確定一般和路徑的長(zhǎng)度有關(guān)。α為信息素的相對(duì)重要程度，β為啟發(fā)式因子的相對(duì)重要程度，allowedk表示螞蟻下一步可以前往的節(jié)點(diǎn)集合。

二、基于用戶(hù)行為及蟻群算法的最優(yōu)路徑選擇

在道路交通網(wǎng)絡(luò)中，使用蟻群算法需要考慮到影響道路交通的諸多因素，比如道路交通事故、交通信號(hào)燈等，以此進(jìn)行更新信息素分配機(jī)制以及啟發(fā)式函數(shù)[3]。在社交網(wǎng)絡(luò)中，使用蟻群算法應(yīng)根據(jù)用戶(hù)行為以及用戶(hù)之間的關(guān)系進(jìn)行更新信息素分配機(jī)制以及啟發(fā)式函數(shù)。

（一）改進(jìn)信息素初始濃度分配機(jī)制

在蟻群算法中，每一條路徑上的初始信息素濃度是一樣的，主要是為了蟻群在初始能夠以均等的概率搜索每一條路徑，但是在社交網(wǎng)絡(luò)中，消息的傳播具有“被動(dòng)性”，即消息的傳播是由用戶(hù)選擇的，而不是由消息決定的，這一點(diǎn)不同于蟻群覓食的“主動(dòng)性”，用戶(hù)選擇消息一般情況下會(huì)受用戶(hù)之間的背景影響，比如工作性質(zhì)相似的人群、具有相同教育背景的人群更容易轉(zhuǎn)發(fā)內(nèi)容相似的消息。所以改變蟻群算法的信息素初始濃度分配機(jī)制，既能夠提升計(jì)算效率，而且避免算法陷入局部最優(yōu)。

本算法在進(jìn)行信息素的初始濃度分配時(shí)主要考慮網(wǎng)絡(luò)用戶(hù)的背景相似度[4]。本文將提取出6個(gè)屬性衡量用戶(hù)的個(gè)人基本信息：性別、年齡、地理位置、職業(yè)（可通過(guò)工作信息獲取）、標(biāo)簽（包含百度人物介紹、簡(jiǎn)介等信息），個(gè)人主頁(yè)微博內(nèi)容，即PI(u)={sex(u),age(u),location(u),work(u),tag(u),blog(u)}。部分信息如圖1所示。

對(duì)于微博用戶(hù)u和v，可通過(guò)一個(gè)向量A(u)和A(v)進(jìn)行表示個(gè)人的基本信息，向量的取值過(guò)程為：若為同性，sex(u)=1，sex(v)=1，否則sex(u)=1,sex(v)=0，若無(wú)信息，默認(rèn)值為sex(u)=1，sex(v)=0；若年齡相差不到5歲，則age(u)=1，age(v)=1，否則age(u)=1，age(v)=0，若無(wú)信息，默認(rèn)值為age(u)=1，age(v)=0；若地區(qū)相同，則location(u)=1，location(v)=1，否則location(u)=1，location(v)=0，若無(wú)信息，默認(rèn)值為location(u)=1，location(v)=0；若職業(yè)相同，則work(u)=1，work(v)=1，否則work(u)=1，work(v)=0，若無(wú)信息，默認(rèn)值為work(u)=1，work(v)=0。由于標(biāo)簽信息以及個(gè)人主頁(yè)微博內(nèi)容不可能相同，而且涉及大量的文本信息，所以不能通過(guò)簡(jiǎn)單的賦值計(jì)算，在這里用余弦相似度獲取標(biāo)簽信息的相似度Tag-Similarity(u,v)，其中Tag(u)=1，Tag(v)=Tag-Similarity(u,v)，若無(wú)信息，默認(rèn)取值為T(mén)ag(u)=1，Tag(v)=0；個(gè)人主頁(yè)微博內(nèi)容的取值可參考標(biāo)簽信息。

對(duì)用戶(hù)基本信息的向量賦值后，采用余弦相似度Similarity(u,v)評(píng)估用戶(hù)之間的相似度，即用戶(hù)之間的個(gè)人基本信息相似性，計(jì)算如式（2）所示：

根據(jù)用戶(hù)的相似度，信息素的初始分配機(jī)制可如式（3）所示：

式（3）中，τuv(0)表示在初始時(shí)刻用戶(hù)關(guān)系(u,v)的信息素濃度。M表示消息在每次傳播時(shí)的初始信息素濃度，為一常數(shù)，k為調(diào)和參數(shù)。在上式中，用戶(hù)的背景相似度能夠衡量社交網(wǎng)絡(luò)的初始人物關(guān)系，該值越大，則該傳播路徑上的初始信息素濃度就越大。

（二）改進(jìn)啟發(fā)式函數(shù)

在蟻群算法中，啟發(fā)式函數(shù)是由蟻群的搜索路徑長(zhǎng)度決定，但未從道路交通網(wǎng)絡(luò)全局出發(fā)，容易陷入局部最優(yōu)的情況。在社交網(wǎng)絡(luò)中，用戶(hù)之間的關(guān)系并不能由長(zhǎng)度決定，而是由用戶(hù)之間的行為關(guān)系決定的，用戶(hù)之間的互動(dòng)越頻繁，消息被傳播的概率就越大。因此，可根據(jù)用戶(hù)之間的行為關(guān)系量化用戶(hù)之間的關(guān)系距離，再?gòu)娜值慕嵌瘸霭l(fā)，綜合考量啟發(fā)式函數(shù)。

用戶(hù)之間的關(guān)系距離需要用戶(hù)之間的交互信息去量化，因用戶(hù)之間的交互信息主要包含評(píng)論、轉(zhuǎn)發(fā)、提及，所以本文采用傳統(tǒng)加權(quán)融合的方式求得用戶(hù)之間的交互量IV（Interactive Volume），如式（4）所示：

式（4）中，IV(v,u)表示用戶(hù)v對(duì)用戶(hù)U的交互量，R(v,u) 表示用戶(hù)v轉(zhuǎn)發(fā)用戶(hù)U微博的數(shù)量，M(v,u)表示用戶(hù)v評(píng)論用戶(hù)U微博的數(shù)量，@(v,u)表示用戶(hù)v提及用戶(hù)U微博的數(shù)量，α，β，γ表示相應(yīng)因素的權(quán)值，很顯然，用戶(hù)之間的交互量具有有向性。

得到用戶(hù)的交互量后，以duv=p*IV-1（v,u）表示用戶(hù)v對(duì)u的關(guān)系距離，即該值越小，用戶(hù)之間的關(guān)系就越近，反之，就越遠(yuǎn)，其中p表示調(diào)和參數(shù)。

設(shè)u表示當(dāng)前消息的位置，v表示消息的下一傳播目標(biāo)，s表示消息的最終受眾位置，Dvs表示采用Dijkstra得到的節(jié)點(diǎn)u到終點(diǎn)s的最短路徑[5]。故啟發(fā)式函數(shù)η(u,v)如式（5）計(jì)算所得：

式（5）中，Q表示第K只螞蟻在本次遍歷中所產(chǎn)生的信息素常量，δ和ε為相應(yīng)的權(quán)值。此時(shí)，啟發(fā)式函數(shù)既能夠根據(jù)局部關(guān)系duv考 慮局部的用戶(hù)關(guān)系強(qiáng)度，又可以根據(jù)Dvs考慮下一選擇位置v在全局網(wǎng)絡(luò)中的位置信息，這樣在選擇下一傳播對(duì)象時(shí)能夠從全局和局部的雙重角度衡量路徑的優(yōu)良程度，避免陷入局部最優(yōu)的狀況。

（三）改進(jìn)信息素更新機(jī)制

信息素的更新機(jī)制直接決定了蟻群算法的性能，傳統(tǒng)的信息素更新機(jī)制主要有上一節(jié)提到的三種模型，但是這三種模型并不適用于社交網(wǎng)絡(luò)的路徑尋優(yōu)問(wèn)題，而且這三種模型都未從全局和局部的雙重角度更新信息素，所以本文以動(dòng)力學(xué)為依據(jù)，從全局和局部的雙重角度改進(jìn)信息素更新機(jī)制。

在網(wǎng)絡(luò)輿情中，決定消息傳播范圍的主要用戶(hù)行為就是轉(zhuǎn)發(fā)、評(píng)論和收藏[6]，決定輿情發(fā)展的關(guān)鍵人物往往是利益的相關(guān)人，即在某一輿論中，消息的局部傳播路徑一般情況下會(huì)相對(duì)穩(wěn)定，如圖2（某一微博社交圈）所示。

在圖2中，假設(shè)用戶(hù)1為消息源，如果消息從1傳到用戶(hù)10，用戶(hù)2轉(zhuǎn)發(fā)用戶(hù)1的消息越多，那么在輿情中，消息的傳播路徑就會(huì)穩(wěn)定在1→2這條路徑上，即越關(guān)注越轉(zhuǎn)發(fā)。本文加入時(shí)間因子，信息素局部更新函數(shù)如式（6）所示：

如果僅僅通過(guò)局部信息素更新機(jī)制，算法往往容易陷入局部最優(yōu)的狀態(tài)，比如根據(jù)上面的信息素更新機(jī)制選定了一條路徑1→2→5→7→10，在該路徑上，由于用戶(hù)2和用戶(hù)1的背景較為相似，用戶(hù)2在單位時(shí)間內(nèi)轉(zhuǎn)發(fā)用戶(hù)1的信息量也較大，那么1→2這個(gè)局部路徑就會(huì)越多的被選擇，但是在實(shí)際的消息傳播過(guò)程中，有可能出現(xiàn)其他情況，比如用戶(hù)5和用戶(hù)4在單位時(shí)間內(nèi)轉(zhuǎn)發(fā)（評(píng)論）用戶(hù)2的信息較少，那么信息從用戶(hù)1到用戶(hù)2之后，消息的傳播基本上就處于停滯狀態(tài)了，這時(shí)根據(jù)局部的信息素更新機(jī)制，算法達(dá)不到全局最優(yōu)。因此設(shè)Lk表示第k條信息本次遍歷完所走的所有路徑和。全局信息素更新如式（7）所示：

借鑒最優(yōu)最差蟻群算法，本算法的信息素更新如式（8）所示：

當(dāng)路徑(i,j)屬于最優(yōu)路徑p*時(shí)，采用對(duì)其進(jìn)行獎(jiǎng)勵(lì)，反之采用對(duì)其進(jìn)行懲罰。比如在圖2中，如果1→2路徑被大量選擇后，但是在用戶(hù)2之后，沒(méi)有消息被傳播，相反，用戶(hù)1→3在初始狀態(tài)傳播信息量有限，但是用戶(hù)5和用戶(hù)6卻會(huì)大量的轉(zhuǎn)發(fā)用戶(hù)3的信息，那么最優(yōu)路徑1→3→6→7→10可能就被發(fā)現(xiàn)選擇，這樣本算法不僅從全局的角度更新了信息素，也從局部的角度更新了信息素，避免算法陷入局部最優(yōu)，同時(shí)也增加算法的執(zhí)行效率。

（四）路徑評(píng)價(jià)函數(shù)

在對(duì)道路的尋優(yōu)路徑進(jìn)行評(píng)價(jià)時(shí)，沒(méi)有嚴(yán)格意義的標(biāo)準(zhǔn)，但是在對(duì)消息的傳播路徑進(jìn)行評(píng)價(jià)時(shí)，考慮的因素較少，主要有在單位時(shí)間內(nèi)用戶(hù)B接受用戶(hù)A的信息量，以及用戶(hù)A到用戶(hù)B的路徑實(shí)際長(zhǎng)度兩個(gè)因素，前一個(gè)因素主要衡量的是信息的傳播質(zhì)量以及傳播速度，后一個(gè)因素主要考慮的是信息傳播的穩(wěn)定性。故引入式（9）作為路徑的評(píng)價(jià)函數(shù)：

在式（9）中，S表示用戶(hù)B接受用戶(hù)A的信息量，S/t表示在單位時(shí)間內(nèi)用戶(hù)B接受用戶(hù)A的信息量，d表示用戶(hù)A到用戶(hù)B的關(guān)系距離，f(d,t)則表示任意兩個(gè)節(jié)點(diǎn)之間在單位時(shí)間內(nèi)傳播的信息量，即衡量整個(gè)路徑在傳播信息時(shí)的效率，該值越大，路徑越優(yōu)。

（五）改進(jìn)信息素?fù)]發(fā)機(jī)制

在蟻群算法中，螞蟻所產(chǎn)生的信息素會(huì)揮發(fā)，在實(shí)際的社交網(wǎng)絡(luò)中，消息傳播所遺留的信息素同樣也會(huì)“揮發(fā)”，本文根據(jù)單位時(shí)間內(nèi)消息經(jīng)過(guò)該路徑的信息量T衡量信息揮發(fā)因子ρ，如式（10）所示。

三、實(shí)驗(yàn)及結(jié)果分析

本算法根據(jù)圖2模擬社交網(wǎng)絡(luò)進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)以經(jīng)典的蟻群算法和Dijkstra算法為對(duì)比模型，驗(yàn)證本算法的有效性。根據(jù)層次分析法以及傳統(tǒng)的蟻群算法要求，本算法的主要參數(shù)詳見(jiàn)表1。

?

根據(jù)微博網(wǎng)絡(luò)中實(shí)際發(fā)生的網(wǎng)絡(luò)輿情情況，以圖2的微博社交圈進(jìn)行模擬仿真，在該圖中，每個(gè)節(jié)點(diǎn)代表的可能是一個(gè)網(wǎng)民，也有可能代表的是較小的一個(gè)社交圈，部分用戶(hù)具有相似的工作背景，輿情周期設(shè)定為半個(gè)月，微博數(shù)據(jù)為8000條。

本實(shí)驗(yàn)根據(jù)微博數(shù)據(jù)測(cè)試集的不同，設(shè)置三組對(duì)比實(shí)驗(yàn)，以此進(jìn)行對(duì)比分析。三組實(shí)驗(yàn)中，測(cè)試集分別設(shè)置為總微博數(shù)據(jù)的60%、70%、80%。出發(fā)節(jié)點(diǎn)為1，接收節(jié)點(diǎn)為10。

第一組實(shí)驗(yàn)：設(shè)置測(cè)試微博數(shù)據(jù)為4800條，驗(yàn)證微博數(shù)據(jù)為3200條，根據(jù)用戶(hù)行為及蟻群算法得到的最優(yōu)路徑為1→3→5→7→9→10；根據(jù)經(jīng)典蟻群算法得到的最優(yōu)路徑為1→3→6→7→10；根據(jù)Dijkstra算法得到的最優(yōu)路徑為1→3→5→7→10。

三種算法得到最優(yōu)路徑長(zhǎng)度以及f(d,t)結(jié)果詳見(jiàn)表2。

?

根據(jù)測(cè)試集中每條微博的轉(zhuǎn)發(fā)路徑，三種算法得到準(zhǔn)確率詳見(jiàn)表3。

?

第二組實(shí)驗(yàn)：設(shè)置測(cè)試微博數(shù)據(jù)為5600條，驗(yàn)證微博數(shù)據(jù)為2400條，根據(jù)用戶(hù)行為及蟻群算法得到的最優(yōu)路徑為1→2→5→7→9→10；根據(jù)經(jīng)典蟻群算法得到的最優(yōu)路徑為1→3→6→7→10，沒(méi)有產(chǎn)生變化；基于Dijkstra算法的最優(yōu)路徑選擇結(jié)果也不變，最優(yōu)路徑仍為1→3→5→7→10。

三種算法得到最優(yōu)路徑長(zhǎng)度以及f(d,t)結(jié)果詳見(jiàn)表4。

?

根據(jù)測(cè)試集中每條微博的轉(zhuǎn)發(fā)路徑，三種算法得到準(zhǔn)確率如表5所示。

?

第三組實(shí)驗(yàn)：設(shè)置測(cè)試微博數(shù)據(jù)為6400條，驗(yàn)證微博數(shù)據(jù)為1600條，根據(jù)用戶(hù)行為以及蟻群算法得到的最優(yōu)路徑為1→2→5→7→9→10沒(méi)有產(chǎn)生變化；根據(jù)經(jīng)典蟻群算法得到的最優(yōu)路徑為1→3→6→7→9→10；基于Dijkstra算法的最優(yōu)路徑選擇結(jié)果不變，最優(yōu)路徑仍為1→3→5→7→10。

三種算法得到最優(yōu)路徑長(zhǎng)度以及f(d,t)結(jié)果詳見(jiàn)表6。

?

根據(jù)測(cè)試集中每條微博的轉(zhuǎn)發(fā)路徑，三種算法得到準(zhǔn)確

?

對(duì)三組實(shí)驗(yàn)結(jié)果進(jìn)行橫向比較，隨著測(cè)試集的增加，基于用戶(hù)行為及蟻群算法的最優(yōu)路徑選擇算法趨于穩(wěn)定，單位時(shí)間內(nèi)傳播的信息量都有所增加，算法的準(zhǔn)確性也在逐步增加。對(duì)于蟻群算法而言，路徑隨著測(cè)試集的增加，路徑會(huì)產(chǎn)生相應(yīng)的變化，單位時(shí)間內(nèi)傳播的信息量在測(cè)試集增加到6400條時(shí)反倒有所下降，算法準(zhǔn)確率隨之也下降。對(duì)于Dijkstra 算法而言，隨著測(cè)試集的增加，雖然路徑?jīng)]有產(chǎn)生變化，但是單位時(shí)間內(nèi)傳播的信息量和算法的準(zhǔn)確率都在下降。

對(duì)三組實(shí)驗(yàn)進(jìn)行縱向比較，在每組實(shí)驗(yàn)中，基于用戶(hù)行為及蟻群算法的最優(yōu)路徑選擇算法在單位時(shí)間內(nèi)傳播的信息量和算法的準(zhǔn)確性都要高于其他兩種算法，而且隨著測(cè)試集的增加，這種對(duì)比結(jié)果更加明顯。

在第一組實(shí)驗(yàn)中，基于用戶(hù)行為及蟻群算法的最優(yōu)路徑選擇算法的路徑長(zhǎng)度是要多于其他兩種算法的，這主要是因?yàn)楸舅惴〞?huì)充分地考慮用戶(hù)之間的行為關(guān)系，改進(jìn)了信息素的更新機(jī)制以及概率選擇函數(shù)的緣故，并不以路徑長(zhǎng)度作為唯一的追求目標(biāo)。另外本算法的收斂速度要明顯優(yōu)于經(jīng)典的蟻群算法，這主要是因?yàn)楦淖兞诵畔⑺氐某跏挤峙錂C(jī)制以及信息素的全局更新機(jī)制。

四、結(jié)語(yǔ)

基于用戶(hù)行為及蟻群算法的最優(yōu)路徑選擇算法充分衡量了用戶(hù)行為以及用戶(hù)關(guān)系的特點(diǎn)，能夠從全局和局部的雙重角度更新信息素以及概率選擇函數(shù)，明顯的提升了蟻群算法的收斂速度，進(jìn)而得到消息的最優(yōu)傳播路徑，借此，可以為公安機(jī)關(guān)準(zhǔn)確預(yù)測(cè)網(wǎng)絡(luò)輿情中的信息傳播路徑以及判斷輿情發(fā)展態(tài)勢(shì)提供技術(shù)支持。