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

吳 婷

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

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

吳 婷

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

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

傳染病模型；轉(zhuǎn)發(fā)行為；和聲算法；參數(shù)優(yōu)化

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

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

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

1 微博傳染病模型

1.1 經(jīng)典SIR傳染病模型

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

SIR（Susceptible Infectious Removed）模型中，此環(huán)境中人口總數(shù)為N(t)，將總?cè)丝诜譃橐韵?類：易感染者S(t)，表示t時刻未感染疾病但有可能被傳染疾病的人數(shù)；感染者I(t)，表示t時刻已被感染成為病人且具有傳染力的人數(shù)；康復者R(t)，表示t時刻不再傳播病毒的康復者人數(shù)，則SIR模型可表示為：

其中，β為單位時間內(nèi)一個感染者能傳染的易感者數(shù)與此環(huán)境內(nèi)易感者總數(shù)的比值；α為單位時間內(nèi)從感染者中康復的人數(shù)與感染者數(shù)量的比值；K為在不考慮人口的出生率和死亡率下，環(huán)境中總?cè)丝跀?shù)（常數(shù)）。

1.2 改進SIRE傳染病模型

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

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

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

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

適應度函數(shù)程序如下：

1.3 對比仿真模型選取

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

其中各參數(shù)取值范圍為[0,1]，η為多重轉(zhuǎn)發(fā)率。

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

其適應度函數(shù)程序如下：

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

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

2 群智能優(yōu)化算法

2.1 PSO算法

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

粒子i更新速度和位置：

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

2.2 GA算法

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

GA參數(shù)優(yōu)化步驟如下：

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

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

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

2.3 HS算法

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

基于HS優(yōu)化的微博參數(shù)尋優(yōu)步驟如下：

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

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

（3）進入迭代循環(huán)，

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

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

3 仿真與結果分析

3.1 數(shù)據(jù)獲取

實驗數(shù)據(jù)通過某微博提供的開放平臺中的信息轉(zhuǎn)發(fā)API接口獲取。

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

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

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

3.2 模型擬合分析

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

如圖1所示，各算法下的模型SIRE和SISe優(yōu)化均能反應微博轉(zhuǎn)發(fā)趨勢，經(jīng)統(tǒng)計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算法也是更優(yōu)的。GA對于SIRE模型擬合較好，而SISe擬合較差，PSO對于SIRE模型擬合性能次之，然而對于SISe模型的求解較之于GA算法更優(yōu)。因此HS算法對于微博轉(zhuǎn)發(fā)擬合具有有效性和優(yōu)越性。

圖1 算法擬合對比圖

3.3 模型預測分析

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

圖2 算法預測對比圖

如圖2所示，各算法均能反映微博趨勢，然而各算法預測是有差異的，經(jīng)統(tǒng)計，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算法對于微博轉(zhuǎn)發(fā)趨勢預測也具有極高的精度，原因是：（1）HS算法具有強的全局尋優(yōu)能力；（2）模型SIRE改進的有效性。

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

4 結束語

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

[1]易成岐，鮑媛媛，薛一波，等.新浪微博的大規(guī)模信息傳播規(guī)律研究[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控制器參數(shù)優(yōu)化[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

吳 婷，在讀碩士研究生。