蟻群算法在網絡輿情中的信息傳播路徑預測研究＊

張俊豪 鐵道警察學院

引言

本文以社交網絡為例，在蟻群算法的基礎上，研究分析用戶行為，找出消息從源頭流轉到特定人群的最優傳播路徑，以期為公安輿情管控提供技術支持。

社交網絡是由用戶及用戶關系組成的，消息通過用戶之間的關系實現流轉，實際的交通網絡是由實體及實體之間的道路組成的，車輛通過實體之間的道路實現運轉。兩者的拓撲結構較為相似，比如消息類似于車輛，用戶關系類似于道路，因此研究預測輿情消息傳播的最優路徑可以借鑒實際生活中的道路尋優算法蟻群算法[1]。但是社交網絡不同于實際的交通網絡，應進行實際的改進，加以應用，找出消息的最佳傳播路徑。

一、蟻群算法簡介

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

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

二、基于用戶行為及蟻群算法的最優路徑選擇

在道路交通網絡中，使用蟻群算法需要考慮到影響道路交通的諸多因素，比如道路交通事故、交通信號燈等，以此進行更新信息素分配機制以及啟發式函數[3]。在社交網絡中，使用蟻群算法應根據用戶行為以及用戶之間的關系進行更新信息素分配機制以及啟發式函數。

（一）改進信息素初始濃度分配機制

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

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

對于微博用戶u和v，可通過一個向量A(u)和A(v)進行表示個人的基本信息，向量的取值過程為：若為同性，sex(u)=1，sex(v)=1，否則sex(u)=1,sex(v)=0，若無信息，默認值為sex(u)=1，sex(v)=0；若年齡相差不到5歲，則age(u)=1，age(v)=1，否則age(u)=1，age(v)=0，若無信息，默認值為age(u)=1，age(v)=0；若地區相同，則location(u)=1，location(v)=1，否則location(u)=1，location(v)=0，若無信息，默認值為location(u)=1，location(v)=0；若職業相同，則work(u)=1，work(v)=1，否則work(u)=1，work(v)=0，若無信息，默認值為work(u)=1，work(v)=0。由于標簽信息以及個人主頁微博內容不可能相同，而且涉及大量的文本信息，所以不能通過簡單的賦值計算，在這里用余弦相似度獲取標簽信息的相似度Tag-Similarity(u,v)，其中Tag(u)=1，Tag(v)=Tag-Similarity(u,v)，若無信息，默認取值為Tag(u)=1，Tag(v)=0；個人主頁微博內容的取值可參考標簽信息。

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

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

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

（二）改進啟發式函數

在蟻群算法中，啟發式函數是由蟻群的搜索路徑長度決定，但未從道路交通網絡全局出發，容易陷入局部最優的情況。在社交網絡中，用戶之間的關系并不能由長度決定，而是由用戶之間的行為關系決定的，用戶之間的互動越頻繁，消息被傳播的概率就越大。因此，可根據用戶之間的行為關系量化用戶之間的關系距離，再從全局的角度出發，綜合考量啟發式函數。

用戶之間的關系距離需要用戶之間的交互信息去量化，因用戶之間的交互信息主要包含評論、轉發、提及，所以本文采用傳統加權融合的方式求得用戶之間的交互量IV（Interactive Volume），如式（4）所示：

式（4）中，IV(v,u)表示用戶v對用戶U的交互量，R(v,u) 表示用戶v轉發用戶U微博的數量，M(v,u)表示用戶v評論用戶U微博的數量，@(v,u)表示用戶v提及用戶U微博的數量，α，β，γ表示相應因素的權值，很顯然，用戶之間的交互量具有有向性。

得到用戶的交互量后，以duv=p*IV-1（v,u）表示用戶v對u的關系距離，即該值越小，用戶之間的關系就越近，反之，就越遠，其中p表示調和參數。

設u表示當前消息的位置，v表示消息的下一傳播目標，s表示消息的最終受眾位置，Dvs表示采用Dijkstra得到的節點u到終點s的最短路徑[5]。故啟發式函數η(u,v)如式（5）計算所得：

式（5）中，Q表示第K只螞蟻在本次遍歷中所產生的信息素常量，δ和ε為相應的權值。此時，啟發式函數既能夠根據局部關系duv考 慮局部的用戶關系強度，又可以根據Dvs考慮下一選擇位置v在全局網絡中的位置信息，這樣在選擇下一傳播對象時能夠從全局和局部的雙重角度衡量路徑的優良程度，避免陷入局部最優的狀況。

（三）改進信息素更新機制

信息素的更新機制直接決定了蟻群算法的性能，傳統的信息素更新機制主要有上一節提到的三種模型，但是這三種模型并不適用于社交網絡的路徑尋優問題，而且這三種模型都未從全局和局部的雙重角度更新信息素，所以本文以動力學為依據，從全局和局部的雙重角度改進信息素更新機制。

在網絡輿情中，決定消息傳播范圍的主要用戶行為就是轉發、評論和收藏[6]，決定輿情發展的關鍵人物往往是利益的相關人，即在某一輿論中，消息的局部傳播路徑一般情況下會相對穩定，如圖2（某一微博社交圈）所示。

在圖2中，假設用戶1為消息源，如果消息從1傳到用戶10，用戶2轉發用戶1的消息越多，那么在輿情中，消息的傳播路徑就會穩定在1→2這條路徑上，即越關注越轉發。本文加入時間因子，信息素局部更新函數如式（6）所示：

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

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

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

（四）路徑評價函數

在對道路的尋優路徑進行評價時，沒有嚴格意義的標準，但是在對消息的傳播路徑進行評價時，考慮的因素較少，主要有在單位時間內用戶B接受用戶A的信息量，以及用戶A到用戶B的路徑實際長度兩個因素，前一個因素主要衡量的是信息的傳播質量以及傳播速度，后一個因素主要考慮的是信息傳播的穩定性。故引入式（9）作為路徑的評價函數：

在式（9）中，S表示用戶B接受用戶A的信息量，S/t表示在單位時間內用戶B接受用戶A的信息量，d表示用戶A到用戶B的關系距離，f(d,t)則表示任意兩個節點之間在單位時間內傳播的信息量，即衡量整個路徑在傳播信息時的效率，該值越大，路徑越優。

（五）改進信息素揮發機制

在蟻群算法中，螞蟻所產生的信息素會揮發，在實際的社交網絡中，消息傳播所遺留的信息素同樣也會“揮發”，本文根據單位時間內消息經過該路徑的信息量T衡量信息揮發因子ρ，如式（10）所示。

三、實驗及結果分析

本算法根據圖2模擬社交網絡進行仿真實驗，實驗以經典的蟻群算法和Dijkstra算法為對比模型，驗證本算法的有效性。根據層次分析法以及傳統的蟻群算法要求，本算法的主要參數詳見表1。

?

根據微博網絡中實際發生的網絡輿情情況，以圖2的微博社交圈進行模擬仿真，在該圖中，每個節點代表的可能是一個網民，也有可能代表的是較小的一個社交圈，部分用戶具有相似的工作背景，輿情周期設定為半個月，微博數據為8000條。

本實驗根據微博數據測試集的不同，設置三組對比實驗，以此進行對比分析。三組實驗中，測試集分別設置為總微博數據的60%、70%、80%。出發節點為1，接收節點為10。

第一組實驗：設置測試微博數據為4800條，驗證微博數據為3200條，根據用戶行為及蟻群算法得到的最優路徑為1→3→5→7→9→10；根據經典蟻群算法得到的最優路徑為1→3→6→7→10；根據Dijkstra算法得到的最優路徑為1→3→5→7→10。

三種算法得到最優路徑長度以及f(d,t)結果詳見表2。

?

根據測試集中每條微博的轉發路徑，三種算法得到準確率詳見表3。

?

第二組實驗：設置測試微博數據為5600條，驗證微博數據為2400條，根據用戶行為及蟻群算法得到的最優路徑為1→2→5→7→9→10；根據經典蟻群算法得到的最優路徑為1→3→6→7→10，沒有產生變化；基于Dijkstra算法的最優路徑選擇結果也不變，最優路徑仍為1→3→5→7→10。

三種算法得到最優路徑長度以及f(d,t)結果詳見表4。

?

根據測試集中每條微博的轉發路徑，三種算法得到準確率如表5所示。

?

第三組實驗：設置測試微博數據為6400條，驗證微博數據為1600條，根據用戶行為以及蟻群算法得到的最優路徑為1→2→5→7→9→10沒有產生變化；根據經典蟻群算法得到的最優路徑為1→3→6→7→9→10；基于Dijkstra算法的最優路徑選擇結果不變，最優路徑仍為1→3→5→7→10。

三種算法得到最優路徑長度以及f(d,t)結果詳見表6。

?

根據測試集中每條微博的轉發路徑，三種算法得到準確

?

對三組實驗結果進行橫向比較，隨著測試集的增加，基于用戶行為及蟻群算法的最優路徑選擇算法趨于穩定，單位時間內傳播的信息量都有所增加，算法的準確性也在逐步增加。對于蟻群算法而言，路徑隨著測試集的增加，路徑會產生相應的變化，單位時間內傳播的信息量在測試集增加到6400條時反倒有所下降，算法準確率隨之也下降。對于Dijkstra 算法而言，隨著測試集的增加，雖然路徑沒有產生變化，但是單位時間內傳播的信息量和算法的準確率都在下降。

對三組實驗進行縱向比較，在每組實驗中，基于用戶行為及蟻群算法的最優路徑選擇算法在單位時間內傳播的信息量和算法的準確性都要高于其他兩種算法，而且隨著測試集的增加，這種對比結果更加明顯。

在第一組實驗中，基于用戶行為及蟻群算法的最優路徑選擇算法的路徑長度是要多于其他兩種算法的，這主要是因為本算法會充分地考慮用戶之間的行為關系，改進了信息素的更新機制以及概率選擇函數的緣故，并不以路徑長度作為唯一的追求目標。另外本算法的收斂速度要明顯優于經典的蟻群算法，這主要是因為改變了信息素的初始分配機制以及信息素的全局更新機制。

四、結語

基于用戶行為及蟻群算法的最優路徑選擇算法充分衡量了用戶行為以及用戶關系的特點，能夠從全局和局部的雙重角度更新信息素以及概率選擇函數，明顯的提升了蟻群算法的收斂速度，進而得到消息的最優傳播路徑，借此，可以為公安機關準確預測網絡輿情中的信息傳播路徑以及判斷輿情發展態勢提供技術支持。