江玲，夏婷婷，蔣藝，范琳

（1.武夷學院數(shù)學與計算機學院，福建武夷山354300；2.綿陽天眼激光科技有限公司，四川綿陽621000）

基于粒子群的微博用戶影響力評價算法研究

江玲1，夏婷婷1，蔣藝1，范琳2

（1.武夷學院數(shù)學與計算機學院，福建武夷山354300；2.綿陽天眼激光科技有限公司，四川綿陽621000）

針對群體智能與微博社交網(wǎng)絡(luò)用戶行為之間的相似性，對基于粒子群的微博用戶影響力的評價算法展開研究。對微博用戶數(shù)據(jù)進行必要的預處理，旨在消除冗余數(shù)據(jù)和無功數(shù)據(jù)對影響力評價的消極影響。介紹了適應(yīng)微博社交網(wǎng)絡(luò)背景的粒子群算法的速度和位移更新公式。完成微博社交網(wǎng)絡(luò)中用戶相互影響力的評價，該評價算法將微博社交網(wǎng)絡(luò)中用戶群體表現(xiàn)出的自組織性和納入評價體系中，在消除少量數(shù)據(jù)引起的評價偏差方面取得一定成效。

粒子群算法；微博社交網(wǎng)絡(luò)；用戶相互影響力

用戶影響力是微博社交網(wǎng)絡(luò)研究中的熱點問題，合理的用戶影響力評價方法是提高用戶推薦[1-2]準確性、用戶使用粘度等微博應(yīng)用的關(guān)鍵技術(shù)。早期研究多以粉絲為中心度量用戶影響力，以經(jīng)典的PageRank算法為代表[3]。不同研究人員對影響力的評價方法也不盡相同，如基于傳播模型[4]、以關(guān)注者為主的評價方式等[5]。但大多只根據(jù)用戶自身的少量微博數(shù)據(jù)，可參考依據(jù)單一，影響力評價體系中考慮的因素不夠全面，從而導致評價效果不佳。

基于上述分析，將群體智能的經(jīng)典算法粒子群[6]融合到微博社交網(wǎng)絡(luò)用戶相互影響力的評價中，一方面可將相關(guān)的用戶群體聯(lián)系起來避免評價指標過于單一，另一方面充分將微博群體在宏觀上表現(xiàn)出分布式和自組織性納入考慮范圍。同時闡述了當前應(yīng)用背景下粒子群的速度和位移更新方法，以增強算法在微博用戶相對影響力評價上的可用性。

1 相關(guān)工作

1.1 標準粒子群算法

粒子群憑借原理簡單、易實現(xiàn)等優(yōu)點，成為群體智能中經(jīng)典的搜索優(yōu)化算法。標準粒子群算法的工作流程如圖1所示，粒子的速度由個體經(jīng)驗和群體經(jīng)驗共同決定，粒子的運動方向則根據(jù)粒子與群體的最佳位置確定，最終實現(xiàn)最優(yōu)搜索。設(shè)t代種群由N個粒子組成，粒子的位置和速度更新方式見公式（1）。

νt和xt分別表示粒子i在t次迭代的速度和位置。pbestt和gbestt分別表示粒子與群體的最佳位置[6]。α，β1，β2分別慣性權(quán)重、個體認知加速因子和社會認知加速因子。r1和r2為[0,1]之間均勻分布的隨機數(shù)。

圖1 標準PSO算法流程圖Figure 1 Flow chartof standard PSO algorithm

1.2 粒子群與微博社交網(wǎng)絡(luò)

粒子在群體沒有控制中心的環(huán)境下，完全依照自身判斷與其他個體交互，從而對整體產(chǎn)生影響。與群體智能相似，微博社交網(wǎng)絡(luò)中任一用戶均可享受發(fā)布微博、關(guān)注互動、搜索等功能，同時用戶間的交互也會對個體的行為產(chǎn)生影響。

在微博應(yīng)用中用戶的行為主要受自身認知水平和網(wǎng)絡(luò)環(huán)境這兩大因素影響。在復雜的微博社交從微博群體在宏觀上表現(xiàn)出分布式和自組織性，不難發(fā)現(xiàn)微博用戶行為與粒子群應(yīng)用的群體智能的五大基本原則上都保持著一致性。

基于微博用戶互動交流與群體智能信息交流的相似性，將粒子群算法融入到微博用戶影響力評價算法中，關(guān)鍵在于粒子進化過程中要靈活結(jié)合用戶微博數(shù)、互動數(shù)等參數(shù)。

2 基于粒子群的微博用戶影響力評價算法

2.1 數(shù)據(jù)與處理

微博數(shù)據(jù)預處理可通過回避冗余和無用數(shù)據(jù)為數(shù)據(jù)采集減負，這對于從海量的微博網(wǎng)絡(luò)數(shù)據(jù)中獲取有利于用戶影響力評價的少量數(shù)據(jù)是極其重要的。

根據(jù)應(yīng)用需求分析，將數(shù)據(jù)歸納為User_Info、Status_Info和Relation_Info三大類，分別表示用戶基本信息、用戶狀態(tài)信息和用戶關(guān)系信息，表1為具體參數(shù)列表。

2.2 基于粒子群算法的微博用戶影響力評價

針對微博社交網(wǎng)絡(luò)的特點，研究的用戶影響力可理解為用戶發(fā)布信息在微博網(wǎng)絡(luò)中引起互動的能力[7]。結(jié)合微博用戶影響力評價的應(yīng)用背景，下文對標準的粒子群算法做適當?shù)母倪M。

2.2.1 影響力公式

依照微博應(yīng)用的特點，用戶影響力可綜合以下參數(shù)進行表：用戶的微博數(shù)U4和粉絲數(shù)U5、轉(zhuǎn)發(fā)微博、微博互動、評論、點贊以及收藏等行為。設(shè)用戶集U=｛A｝+UR，其中UR=｛u1，u2，u3，…，un｝表示相關(guān)用戶集合，A為中心用戶。A與u1發(fā)生互動行為b時，A的影響力的變化量可由公式(5)表示：

式(9)是相關(guān)用戶集合UR對A的影響力因子向量，可以用來表征A在UR的n維用戶空間中的位置，即IA=，…］。

表1 微博數(shù)據(jù)集Table 1 The table ofmicroblog data set

2.2.2 速度公式

根據(jù)微博用戶群體的互動方式，將用戶影響力的表現(xiàn)形式融入到粒子群算法中，對A在t+1時刻速度公式重新定義，如公式(10)。

T1、T2和T3分別為慣性部分，個體因素部分，和社會因素部分。A在該時間粒度下所獲得的個體經(jīng)驗值和社會經(jīng)驗值分別由PA（t）和SA（t）表征。個體經(jīng)驗值和社會經(jīng)驗值的最佳值分別由PA_M（t）和SA_M（t）表征。

個人經(jīng)驗是通過用戶主動行為獲得，主要考察主動對其他用戶微博的轉(zhuǎn)發(fā)行為。一方面是因為微博數(shù)目在數(shù)據(jù)采集階段突顯不出差異性，故不具參考意義。另一方面是考慮到相對評論和點贊對自身的低貢獻的特點，轉(zhuǎn)發(fā)行為才是信息傳播的重要途徑。故A在一定時間粒度下通過轉(zhuǎn)發(fā)u1的微博獲得的個體經(jīng)驗由公式(11)表示。

NFAu1為本次迭代中A轉(zhuǎn)發(fā)用戶u1的微博數(shù)目，NFA為本次迭代過程中A轉(zhuǎn)發(fā)微博的總數(shù)，若本次迭代的15條微博均為A的原創(chuàng)微博，則本次迭代A的個人經(jīng)驗置零。擴展到相關(guān)用戶空間UR=｛u1，u2，u3，…，un｝，用戶A通過本次迭代得到的N維個體經(jīng)驗為

社會經(jīng)驗由其他用戶對A的微博進行互動產(chǎn)生。A通過u1積累的社會經(jīng)驗取值如式(12)。

第一個加數(shù)部分表示轉(zhuǎn)發(fā)因子和轉(zhuǎn)發(fā)經(jīng)驗，第二個加數(shù)部分為其它互動因子和互動經(jīng)驗。NFu1A為u1在本次迭代過程中轉(zhuǎn)發(fā)A的微博總數(shù)，ΣS5（A）為本次迭代過程中A的所有微博被轉(zhuǎn)發(fā)的總數(shù)。為本次迭代過程中A被u1轉(zhuǎn)發(fā)過的微博評論和點贊數(shù)之和，NCPA表示A本次迭代微博評論和贊之和。擴展到UR=｛u1，u2，u3，…，un｝，得到

3 用戶影響力評價實驗

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

為了檢驗改進粒子群算法在用戶影響力評價中的有效性，通過基于模擬登陸的微博爬蟲系統(tǒng)[7]完成數(shù)據(jù)采集工作。本次數(shù)據(jù)采集以用戶UID=2530487345為中心，根據(jù)表1收集56 461個用戶信息。其中一度人脈、二度人脈和三度人脈的用戶數(shù)分別為29、1 026、55 406。采集的數(shù)據(jù)中還包含每個用戶約300條微博狀態(tài)信息作為評價實驗的數(shù)據(jù)集。

3.2 實驗參數(shù)設(shè)置

（1）慣性因子：α=0.8。

考慮用戶影響力度的記憶性因素，實驗中將慣性因子設(shè)為經(jīng)驗值0.8。

（2）認知因子：β1=β2=2。

按照經(jīng)驗設(shè)置，保持個體認知與社會認知的同等重要性。

（3）社會認知中行為權(quán)重：φ1=0.6，φ2=0.4。

由于在信息傳播等實際應(yīng)用中，轉(zhuǎn)發(fā)行為的貢獻往往高于其他互動行為，故二者按照6∶4比重劃分，降低了粉絲數(shù)過高帶來的偏差，同時保留住粉絲數(shù)對用戶影響力的表征能力。

（4）用戶初始速度：0。

（5）用戶初始位置：由總用戶數(shù)確定。

（6）用戶初始影響力：

用戶初始影響力根據(jù)粉絲數(shù)與微博總數(shù)歸一化數(shù)值進行設(shè)置。

3.3 實驗結(jié)果分析

根據(jù)20組的Status_Info對用戶進行20次粒子群迭代算法評估相互影響力，圖2記錄了前2 000位用戶第1次迭代結(jié)果(a圖)和第5次迭代結(jié)果（b圖）。圖中數(shù)據(jù)表明經(jīng)過第1次迭代，用戶影響力度分布比較集中且擴散性不高，產(chǎn)生這一現(xiàn)象與影響力度初始值設(shè)置有關(guān)。為此第1次迭代后，只有極少數(shù)用戶的影響力得以提高。但迭代進行到第五代，隨著用戶間的互動行為，影響力的擴散度顯然高于第一次迭代的效果。

圖2 用戶影響力評價（第1、5次迭代）Figure 2 Evaluation on user influence based on PSO(the first time and fifth time)

圖3記錄了第10次迭代結(jié)果(a圖)和第20次迭代結(jié)果(b圖)。對比圖2和圖3容易發(fā)現(xiàn)，隨著迭代次數(shù)增加，用戶影響力逐步分散。用戶影響力變化趨勢可歸納為以下比較有代表性的三類。

(1)影響力始終偏低：少量用戶始終保持偏低的影響力，究其原因在于該類用戶一方面鮮少參與微博互動，另一方面該類用戶所發(fā)布的微博引發(fā)的互動情況的甚少。

(2)影響力變化趨勢先高后低：部分用戶隨著迭代過程，影響力由早先的優(yōu)勢逐步成下降趨勢。這類用戶多由微博應(yīng)用的早期使用者構(gòu)成，他們通過微博總數(shù)和粉絲數(shù)上的優(yōu)勢獲得較高的初始影響值。但隨著后期微博使用粘度下降，微博質(zhì)量欠佳，影響力度也隨之降低。

(3)影響力逐步提高：這類用戶大多由目前微博應(yīng)用的活躍分子們構(gòu)成，他們憑借少而優(yōu)的微博獲取大量關(guān)注和互動，憑借微博應(yīng)用的熱度，消除在粉絲數(shù)和微博總數(shù)上的劣勢。

圖3 用戶影響力評價（第10、20次迭代）Figure 3 Evaluation on user influence based on PSO(the 10th time and 20th time)

圖4 用戶影響力排行Figure 4 Rank of user influence

將全部用戶按最后一次迭代獲得的影響力度降序排列，并截取影響力相對偏高的用戶（In f(u)＞1），如圖4所示。根據(jù)圖4結(jié)果顯示，經(jīng)過20次迭代，影響力度偏高的用戶共2 483人，其中只有118位用戶的最終影響力大于4，而影響力度較高的人數(shù)則更少，這也與復雜網(wǎng)絡(luò)的冪律特性相符。

4 結(jié)論

尋找有效的用戶影響力評價算法是改進微博用戶推薦策略等應(yīng)用的難題。研究的基于粒子群的微博用戶相互影響力的評價算法，可將相關(guān)的用戶群體聯(lián)系起來，在避免評價指標過于單一的問題上取得一定成效。此外充分將微博群體在宏觀上表現(xiàn)出分布式和自組織性納入考慮范圍。這些研究成果將對微博用戶推薦等應(yīng)用提高參考。

[1]范波，程久軍．用戶間多相似度協(xié)同過濾推薦算法[J]．計算機科學，2012，39(1)：23-26.

[2]HANNON J,CARTHY K,SMYTH B.Finding useful users on twitter:twittomender the followee recommender[C].Ad vances in Information Retrieval,2011,784-787.

[3]LAWRENCE P.The PageRank citation ranking:Bringing order to the web[J].Stanford Digital Libraries Working Paper,1998,9(1):1-14.

[4]GOYAL A,BONCHI F,LAKSHMANAN LVS.Learning influence probabilities in social networks[C].International Conference on Web Search&Web Data Mining,2010:241-250.

[5]CHA M,HADDAD H,Benevenuto F,et al.Measuring userinfluence in twitter:the million follower fallacy[C].InternationalConferenceonWeblogs&SocialMedia,2010：10-17.

[6]KENNEDY J,EBERHART R.Particle swarm optimization[C].Proc.ICNN.1995：1942-1948.

[7]江玲．基于粒子群算法的微博用戶推薦系統(tǒng)[D]．綿陽：西南科技大學，2015.

（責任編輯：葉麗娜）

The Calculate Algorithm Study for M icroblog User Influence Based on Particle Swarm Optim ization

JIANG Ling1,XIA Tingting1,JIANG Yi1,FAN Lin2
(1.School of Mathematics Science and Computer,WuyiUniversity,Wuyishan,Fujian 354300；2.Mianyang Skyeye Laser Technology Co.Ltd,Mianyang,Sichuan 621010)

According to the fact that the user’s behaviors ofmicroblog social network match the five principles of Swarm intelligence,a novel algorithm based on particle swarm optimazation is studyed in this paper to calculate the influence bewteen microblog users.First,in order to avoid the negative effect from redundant and uselessmicroblog data,data preprocessing is necessary.Second,the variable is defined as the velocity hange in the proposed algorithm.Finally,the process to calculate the influence between users is introduced.The experiment results show that the novel algorithm is effective in avoiding the negative influence from signal index.

particle swarm optimazation;microblog social network;user influence

TP393

：A

：1674－2109(2017)06－0063－05

2017-02-23

武夷學院?？蒲谢鹳Y助項目(XL201708)。

江玲（1990-），女，漢族，助教，主要從事信息網(wǎng)絡(luò)、用戶行為研究。