基于粒子群的微博用戶影響力評(píng)價(jià)算法研究

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

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

基于粒子群的微博用戶影響力評(píng)價(jià)算法研究

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

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

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

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

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

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

1 相關(guān)工作

1.1 標(biāo)準(zhǔn)粒子群算法

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

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

圖1 標(biāo)準(zhǔn)PSO算法流程圖Figure 1 Flow chartof standard PSO algorithm

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

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

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

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

2 基于粒子群的微博用戶影響力評(píng)價(jià)算法

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

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

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

2.2 基于粒子群算法的微博用戶影響力評(píng)價(jià)

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

2.2.1 影響力公式

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

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

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

2.2.2 速度公式

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

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

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

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

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

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

3 用戶影響力評(píng)價(jià)實(shí)驗(yàn)

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

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

3.2 實(shí)驗(yàn)參數(shù)設(shè)置

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

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

（2）認(rèn)知因子：β1=β2=2。

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

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

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

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

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

（6）用戶初始影響力：

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

3.3 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

[1]范波，程久軍．用戶間多相似度協(xié)同過濾推薦算法[J]．計(jì)算機(jī)科學(xué)，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]．綿陽：西南科技大學(xué)，2015.

（責(zé)任編輯：葉麗娜）

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

武夷學(xué)院校科研基金資助項(xiàng)目(XL201708)。

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