基于和聲算法的微博傳播預測研究

吳 婷

(西南交通大學 經濟管理學院，成都 610031)

基于和聲算法的微博傳播預測研究

吳 婷

(西南交通大學 經濟管理學院，成都 610031)

微博信息傳播預測研究已成為廣大學者研究的重點，而微博轉發是其中一個關鍵機制。本文結合傳統的傳染病模型，融入外來用戶影響因子，得到改進的微博預測SIRE模型。通過對比SISe模型，SIRE模型能夠更好地擬合和預測微博轉發規律。從算法性能上通過對比和聲算法、粒子群算法、遺傳算法，結果表明，采用和聲算法進行微博轉發預測模型參數尋優，其性能最佳，并能很好地表征微博傳播趨勢。

傳染病模型；轉發行為；和聲算法；參數優化

微博作為當前國內社交網絡的一種新興事物，已經成為重要的社交通信工具，并能夠在短期內快速傳播[1]。微博的高效傳播特性，已成為國內外廣大學者研究的焦點[2]。

對于微博的傳播模型研究：Watts 和 Strogatz[3]在提出 SW（small world）網絡模型的開創性工作中指出SW效應會加快傳染病的傳播過程。Chakrabarti D等[4]提出通用流行閥值條件，利用傳染病模型的方法預測微博的轉發規模，但模型只進行仿真驗證，未進行真實數據的模型驗證。Li.Y等[5]利用擴展的傳染病模型對騰訊微博信息的轉發次數進行準確的預測。M.Cha 等[6]假定 Twitter上用戶關注數的數量不是衡量用戶影響力的有效方法，提出了3種不同的測量用戶影響力的方法—用戶的粉絲數、用戶的微博被轉發的次數以及用戶的提及數。Yang J等[7]基于數據挖掘中的“生存分析”理論研究了Twitter中主題的擴散情況和標簽內容的傳播情況。

本文根據微博信息傳播與傳染病傳播的相似性，借鑒經典的SIR傳染病模型，引入微博信息傳播的自發性及不重復性，采用改進微博信息傳播預測模型，通過和聲算法[8]對模型參數進行優化分析，目的在于更好地預測微博信息的轉發數量，并得出微博信息的傳播趨勢。

1 微博傳染病模型

1.1 經典SIR傳染病模型

1927年，Kermack和Mckendrick[9]提出了著名的SIR隔離模型。

SIR（Susceptible Infectious Removed）模型中，此環境中人口總數為N(t)，將總人口分為以下3類：易感染者S(t)，表示t時刻未感染疾病但有可能被傳染疾病的人數；感染者I(t)，表示t時刻已被感染成為病人且具有傳染力的人數；康復者R(t)，表示t時刻不再傳播病毒的康復者人數，則SIR模型可表示為：

其中，β為單位時間內一個感染者能傳染的易感者數與此環境內易感者總數的比值；α為單位時間內從感染者中康復的人數與感染者數量的比值；K為在不考慮人口的出生率和死亡率下，環境中總人口數（常數）。

1.2 改進SIRE傳染病模型

由于SIR模型中假設環境中人口的總數K是常數，而實際每個微博用戶可以在不需要其關注者的同意而即時的閱讀、評論和轉發其關注者的微博信息，傳統的SIR模型未考慮外來用戶影響，因此有必要對SIR模型進行改進。

設外來用戶為E，則模型定義為SIRE（Susceptible Infectious Removed External），外來用戶E是指沒有關注某微博的發布用戶和轉發用戶，而是自主的閱讀并轉發此微博的用戶。外來用戶在實際微博傳播中占一定的比例，并且外來用戶也有轉發閱讀微博的概率，因此將式（1）改寫為：

其中，各參數取值范圍為[0,1]，γ為外來用戶轉發微博的概率， ω為外來用戶占實時轉發者的比例。

由于模型的離散化以及非線性約束關系，給模型的參數尋優帶來一定的困難，本文采用現代智能算法[10]進行參數尋優分析，智能算法采用貪婪算法機制，盡量去逼近模型，且保證模型具有一定的精度。因此智能算法首要任務就是解決其適應度函數（目標函數）問題，本模型中，選擇適應度函數為每個時間點下的逼近誤差絕對值和，適應度值越小越好。即在某組優化參數下，針對所有的數據逐點逼近計算，得到的累計絕對誤差和最小。

適應度函數程序如下：

1.3 對比仿真模型選取

Wang H等[2]提出SISe模型，如下：

其中各參數取值范圍為[0,1]，η為多重轉發率。

式（3）存在的弊端在于，一般情況下，微博用戶不會再次轉發自己已經發表或者轉發過的微博信息，即微博用戶轉發行為的不重復性。因此將式（3）和式（2）進行對比分析。

其適應度函數程序如下：

式（2）和式（3）中S、I、R、E數據是可以直接獲取的，然而對著這種離散的海量數據參數優化分析，并且下一時刻某個變量的取值和上一時刻各變量之間均有非線性約束關系，因此常用的傳統方法根本無法勝任。

考慮到現代智能算法能夠解決傳統算法不能解決的問題，如當尋優目標函數是離散的、含有一些非線性相關參量時。因此本文通過獲取微博實際數據后，采用智能算法[8～10]對SIRE模型、SISe模型進行參數對比優化分析。

2 群智能優化算法

2.1 PSO算法

PSO在搜索域內，粒子以一定的速度更新當前最優粒子和最優種群。每次迭代，更新“個體最優”值、“種群最優”值和粒子速度值，最終得到一組較為合理的結果。PSO簡單易實現，易出現早熟等現象，以致不能全局尋優[10]。

粒子i更新速度和位置：

其中，學習因子c1和c2是非負常數；r1和r2為[0,1]之間的偽隨機數，pi(t)為種群個體最優值， pg(t)為種群全局最優值； c1r1(t)(pi(t)–xi(t))可理解為粒子的認知行為，表示粒子本身的思考能力，c2r2(t)(pg(t)–xi(t))可理解為粒子的社會行為，表示粒子之間的信息共享與相互合作。

2.2 GA算法

GA采用的主要算法包括選擇、交叉、變異，通過區別個體基因變化信息來保留高適應環境的基因特征，消除低適應環境的基因特征，以實現優化目的，然而GA不能有效的使用局部信息，因此需要花很長時間收斂到一個最優點[10]。

GA參數優化步驟如下：

（1）在個體取值范圍[0,1]內隨機初始化種群；

（2）計算適應度函數值，通過選擇、交叉、變異操作找到最優個體及種群；

（3）計算新種群的適應度值，直到迭代終止，否則返回執行步驟（2）。

2.3 HS算法

和聲算法（HS）遵從3條規則：（1）根據和聲記憶庫的考慮概率（harmony memory consideration,HMCR），從HM中選擇個體；（2）根據基音調整概率（pitch adjusting rate,PAR）值來決定是否對所選擇的和聲進行調整；（3）采用隨機擾動的方式尋找新的音符。HS算法是一種全局優化算法，近幾年被用于電力系統、控制器設計、供應鏈模型等[8]。

基于HS優化的微博參數尋優步驟如下：

（1）參數初始化：變量個數、變量取值范圍、和聲記憶庫大小HMS、基音擾動帶寬（步長bw）、HMCR、PAR以及最大迭代次數N等；

（2）初始化個體，并計算器適應度值；

（3）進入迭代循環，

其中，xiU、xiL為第i維和聲變量的上下限，xinew為新產生的第i維和聲變量。

（4）進行適應度值更新，直到迭代終止，否則返回執行步驟（3）。

3 仿真與結果分析

3.1 數據獲取

實驗數據通過某微博提供的開放平臺中的信息轉發API接口獲取。

通過某微博提供的2015年1月～5月的“頭條新聞”用戶的原創微博信息、轉發微博信息，提取出200條持續2天時間的微博轉發數在1 000次～20 000次的微博信息作為本實驗數據集訓練集(1月～3月)和測試集(4月～5月)。

設置程序初始狀態，即微博發布t0時刻，只有一個感染用戶I(t0)=1，E(t0)=0，S(t0)=K，K為微博發布者的粉絲數量。

個體（待尋優參數）取值范圍為0～1，設定種群大小HMS為100，基音擾動帶寬bw=2e-3，和聲記憶庫的考慮概率HMCR=0.95，基音調整概率PAR=0.3，迭代次數為500，交叉概率為0.8，變異概率為0.05，粒子最大速度vmax=1。

3.2 模型擬合分析

分別采用和聲算法、粒子群算法、遺傳算法對式（2）、式（3）進行優化分析，取樣本訓練集進行擬合操作。

如圖1所示，各算法下的模型SIRE和SISe優化均能反應微博轉發趨勢，經統計HS-SIRE算法擬合絕對誤差和為709.1，GA-SIRE為766.0，PSOSIRE為988.1，HS-SISe為764.2，GA-SISe為1 836.7，PSO-SISe為777.1。由此可得HS算法性能最佳，且較之于SISe模型，HS算法也是更優的。GA對于SIRE模型擬合較好，而SISe擬合較差，PSO對于SIRE模型擬合性能次之，然而對于SISe模型的求解較之于GA算法更優。因此HS算法對于微博轉發擬合具有有效性和優越性。

圖1 算法擬合對比圖

3.3 模型預測分析

微博信息傳播建模的目的是預測，為了客觀衡量模型預測的效果， 采用測試集數據對模型進行驗證，采用擬合分析中的最優參數值進行測試樣本預測分析，得到如圖2所示的對比圖。

圖2 算法預測對比圖

如圖2所示，各算法均能反映微博趨勢，然而各算法預測是有差異的，經統計，HS-SIRE算法預測絕對誤差和為1 552.0，GA-SIRE為1 630.2，PSOSIRE為5 046.5，HS-SISe為4 512.9，GA-SISe為4 336.5，PSO-SISe為4 051.0。由此可得，采用和聲HS算法對于微博轉發趨勢預測也具有極高的精度，原因是：（1）HS算法具有強的全局尋優能力；（2）模型SIRE改進的有效性。

圖1和圖2驗證了SIRE模型的有效性以及HS算法的穩定性。

4 結束語

本文研究了微博傳播預測模型，通過和聲算法、粒子群算法以及遺傳算法對比參數優化分析，得到采用和聲算法進行微博擬合預測分析，能夠更好地預測微博傳播特性。因此，合理改進微博模型以及優化算法選擇是微博研究的一個重要方向。

[1]易成岐，鮑媛媛，薛一波，等.新浪微博的大規模信息傳播規律研究[J].計算機科學與探索，2013，7(6)：551-560.

[2]Wang H,Li Y,Feng Z,et.al.ReTweeting Analysis and Prediction in Microblogs:An Epidemic Inspired Approach[J].China Communication,2013,10 (3):13-24.

[3]Watts D J,Strogatz S H.Collective dynamics of‘small-world’networks[J].Nature,1998,393(6684):440-442.

[4]Chakrabarti D,Wang Y,Wang C,et al.Epidemic thresholds in real networks.ACM Trans[J].2008,10 (4).

[5]Li Y,Feng Z,Wang H,et al,ReTweetp:Modeling and Predicting Tweets Spread Using an Extended Susceptible-Infected-Susceptible Epidemic Model[J].2013(2):454-457.

[6]M.Cha,H.Haddadi,F.Benevenuto,et al.Measuring User Influence in Twitter: The Million Follower Fallacy[C].In Fourth International AAAI Conference on Weblogs and Social Media,2010.

[7]Yang J,Counts S.Predicting the speed,scale and range of information diffusion in Twitter[C].Association for the Advancement of Artifcial Intelligence,2010:355-358.

[8]歐陽海濱，高立群，鄒德旋，等.和聲搜索算法探索能力研究及其修正[J].控制理論與應用，2014，31（1）：57-65.

[9]KERMACK W O,MCKENDRICK A G.Contributions to the Mathematical Theory of Epidemics.II.The Problem of Endemicity[J].Bulletin of Mathematical Biology,1991,53(1/2):57-87.

[10]余勝威，曹中清.基于人群搜索算法的PID控制器參數優化[J].計算機仿真，2014，31（9）：347-350.

責任編輯 陳 蓉

Micro blog communication prediction based on Harmony Search Algorithm

WU Ting
( School of Economics and Management,Southwest Jiaotong University,Chengdu 610031,China)

The research on micro blog communication prediction was a hot spot.Micro blog forwarding was one of the key mechanisms.On the basis of traditional infectious diseases model,an improved SIRE model was proposed through integrating into the foreign user impact factor.Comparing with the SISe model,SIRE model could be used to ft well and forecast the micro blog forwarding rule.Comparing with Harmony Algorithm,the Particle Swarm Algorithm and Genetic Algorithm, Harmony Algorithm was used for parameters optimization of micro blog forwarding prediction model,its performance was the best,it could characterize the tread of micro blog communication.

infectious disease model;forwarding behavior;Harmony Algorithm; parameters optimization

TP39

A

1005-8451（2016）02-0012-04

2015-06-09

吳 婷，在讀碩士研究生。