王東升

（上海海事大學信息工程學院，上?！?01306）

基于PageRank改進算法的微博影響力排名

王東升

（上海海事大學信息工程學院，上海201306）

0　引言

PageRank算法是在微博用戶影響力研究領域相對普遍及重要的算法。近年來，對基于PageRank算法提出的微博用戶影響力改進算法日漸得到完善：①馮典等人利用微博用戶關系結(jié)構提出來基于相對權威度（根據(jù)粉絲的質(zhì)量和用戶本身權威度為評價依據(jù)）和用戶活力（用戶發(fā)布和評論微博的次數(shù)為評價依據(jù)）兩個方面改進了PageRank算法，迭代求出微博用戶影響力［1］。盡管能夠快速實現(xiàn)算法收斂，減少迭代次數(shù)，但是這種宏觀的根據(jù)重要粉絲和用戶活躍度來分配權值會改變原有的用戶互動行為。②王琛等人基于PageRank算法，根據(jù)用戶活力和粉絲參與活力（粉絲轉(zhuǎn)發(fā)、評論關注者微博的比例）提出了user influence rank用戶影響力排名算法［2］。這個算法本質(zhì)上基本體現(xiàn)微觀粉絲和關注用戶之間的互動。但用戶活力這個因素基本有作用，相反還會改變用戶之間的互動關系，考慮不完善。

1　算法原型

PageRank由Google創(chuàng)始人拉里·佩奇和謝爾蓋·布林提出，其基本思想是利用網(wǎng)頁的超鏈接結(jié)構判定網(wǎng)頁重要性，即網(wǎng)頁a有個只向網(wǎng)頁b的鏈接，則認為a投了網(wǎng)頁b一票，算法根據(jù)網(wǎng)頁收到的投票數(shù)量來衡量該網(wǎng)頁的重要性。這種網(wǎng)頁鏈接和微博中的關注和被關注用戶關系式相似的，但是忽略了用戶與用戶本身的互動關系及客觀的作用域。

2　改進UI-Rank算法設計

綜合用戶j的影響力值為：

其中I（j）表示用戶j的粉絲集合；UA（i）表示用戶i的影響力；d為阻尼系；

OUT（i，j）=a×HUA（i，j）+b×FUA（i，j）+c×IUA（i，j）

OUT（i，j）用戶i的用戶影響力分配給其關注者j的權值比例，HUA（i，j）表示基于粉絲參與度的粉絲i分配給其關注者j的權值比例，F(xiàn)UA（i，j）則基于微博影響度時用戶i分配給其關注者j的權值比例，IUA（i，j）表示基于用戶活客觀躍度時用戶i分配給其關注者j的權值比例。a，b，c為對應的權重。

2.1粉絲參與度

一個粉絲轉(zhuǎn)發(fā)和評論關注者微博的多少，直接反映了被關注者所發(fā)微博對其粉絲的吸引力。粉絲轉(zhuǎn)發(fā)和評論其微博的次數(shù)越多，粉絲和關注者直接的互動越多，說明粉絲對其關注的用戶越感興趣。

一個用戶的微博總體上分為原創(chuàng)微博和轉(zhuǎn)發(fā)微博。粉絲轉(zhuǎn)發(fā)關注者的原創(chuàng)微博，說明粉絲對其關注者自己的思想和態(tài)度的肯定；而粉絲轉(zhuǎn)發(fā)其關注者的轉(zhuǎn)發(fā)微博，說明粉絲對關注者轉(zhuǎn)發(fā)的微博原主人態(tài)度或者思想的肯定，并不是被關注者本人所吸引。

粉絲對關注者的評論，同樣體現(xiàn)了其對關注者互動的程度，表現(xiàn)了對其所發(fā)微博的興趣，評論越多，程度越深。但粉絲對關注者的評論并不能被粉絲自己的粉絲所看到，即評論的態(tài)度和思想不能傳播給自己的粉絲。

所以在本算法思想的分配原則來說，粉絲分配給其關注者的權值時，應該更加看重粉絲是否轉(zhuǎn)發(fā)關注者的微博，轉(zhuǎn)發(fā)的微博是否是其關注者的原創(chuàng)微博。

基于粉絲參與度的粉絲i分配給其關注者j的比例為：

F（i）表示用戶i的關注者集合，即全部好友集合，

其中H（i，j）為用戶i與其關注者j互動程度。h1，h2，h3為對應參數(shù)的權重。

Y（i，j）表示在統(tǒng)計周期內(nèi)（T=30天）用戶i轉(zhuǎn)發(fā)其關注者j原創(chuàng)微博的數(shù)目（Yn）和用戶i轉(zhuǎn)發(fā)和評論別人微博總數(shù)（Tn）的比值。

Z（i，j）表示統(tǒng)計周期內(nèi)（T=30天）用戶i轉(zhuǎn)發(fā)其關注者J轉(zhuǎn)發(fā)微博的數(shù)目（Zn）和用戶i轉(zhuǎn)發(fā)和評論別人微博總數(shù)（Tn）的比值。

P（i，j）表示統(tǒng)計周期內(nèi)（T=30天）用戶i評論其關注者j的微博數(shù)目（Pn）和用戶i轉(zhuǎn)發(fā)和評論別人微博總數(shù)（Tn）的比值。

2.2用戶活客觀躍度

粉絲參與度在很大程度上表明了粉絲和關注者直接的互動，用戶傳遞給其粉絲的信息狀態(tài)，但是這種互動只是局限的展示了粉絲轉(zhuǎn)發(fā)和評論其關注者的微博上，但事實上一個用戶發(fā)布和轉(zhuǎn)發(fā)的微博給用戶傳遞的信息不僅僅是體現(xiàn)在轉(zhuǎn)發(fā)上，還體現(xiàn)在一個粉絲在閱讀其關注者的微博時不經(jīng)意間產(chǎn)生的信息量。

因為用戶對其關注者或者他人的評論信息無法傳播給自己粉絲，所以這個因素新算法不做考慮。用戶發(fā)布的原創(chuàng)微博和轉(zhuǎn)發(fā)微博是決定的因素。但原創(chuàng)微博和轉(zhuǎn)發(fā)的微博傳遞給其粉絲的思想和態(tài)度的意義是不同的，所以算法對原創(chuàng)微博數(shù)和轉(zhuǎn)發(fā)微博數(shù)同樣有不同的衡量參數(shù)標準i1，i2。

在一個統(tǒng)計周期范圍內(nèi)，用戶發(fā)布原創(chuàng)微博數(shù)以及轉(zhuǎn)發(fā)微博數(shù)越多，越能說明該用戶的活力越高，粉絲閱讀該用戶的微博條數(shù)的可能就越多。更深入地，客觀地，一個用戶發(fā)表的原創(chuàng)微博數(shù)越多，用戶傳遞給其粉絲自己的思想觀念信息就越大。

用戶j的客觀活躍度為：

其中CNj表示用戶j統(tǒng)計周期內(nèi)（T=30天）發(fā)布的原創(chuàng)微博數(shù)，TNj表示統(tǒng)計周期內(nèi)（T=30天）用戶j轉(zhuǎn)發(fā)他人的微博數(shù)。

基于用戶活客觀躍度時用戶i分配給其關注者j的比例為：

其中F（i）表示用戶i的關注者集合，即全部好友集合，v，j F（i）。

2.2微博影響度

微博是一個開放的信息交流平臺，任何人都可以瀏覽、轉(zhuǎn)發(fā)和評論自己感興趣的用戶的微博，這個用戶不一定是自己的關注者（好友），可能是自己隨意瀏覽發(fā)現(xiàn)的，可能是系統(tǒng)推薦，也有可能是某個時間段比較有社會效益的話題等。這些不定因素所造成的不是自己粉絲轉(zhuǎn)發(fā)或者評論的影響，基于粉絲參與度和基于用戶客觀活躍度分配比例值解決不了，針對這種情況，算法提出來基于微博影響度分配方法。

其中WTn是在在統(tǒng)計時間內(nèi)微博w被轉(zhuǎn)發(fā)次數(shù)；WPn是微博w在統(tǒng)計時間內(nèi)被評論的次數(shù)。用戶j在統(tǒng)計時間內(nèi)發(fā)布微博的總影響度，其中f（j）表示用戶j在統(tǒng)計時間內(nèi)發(fā)布的原創(chuàng)微博和轉(zhuǎn)發(fā)微博的集合。

則基于微博影響度時用戶i分配給其關注者j的比例為：

其中F（i）表示用戶i的關注者集合，即全部好友集合，v，j∈F（i）。

3　實驗結(jié)果及分析

利用層次分析法［3］我們可以確定一級權重a，b，c分別為0.45，0.30，0.25；二級權重h1，h2，h3，i1，i2分別0.25，0.2，0.15，0.22，0.18。利用新浪微博API接口獲得真實用戶數(shù)據(jù)，帶入算法得到下表1兩種算法的排名前十的用戶。

根據(jù)實驗結(jié)果可以看出兩種算法的結(jié)果發(fā)生了變化。在上表中我們可以大概看出PageRank算法的排名中基本依靠粉絲的數(shù)量來取決。顯著的特征是在原算法排名第3的郭德綱在新算法中已經(jīng)不在前十中，盡管粉絲數(shù)量很多，但其粉絲的影響力值普遍都不高，所以分配在新算法中分配給他的值不高導致排名落后。而原本排名第八位的李開復在新算法中排名第二，主要原因是李開復雖然粉絲數(shù)量少，但發(fā)的微博基本都是原創(chuàng)微博，且很受粉絲歡迎，轉(zhuǎn)發(fā)，并且粉絲的自身影響力值相對很高。

4　結(jié)語

本文給出了基于PageRank算法改進的新算法的整體算法思路，相比PageRank算法得到的結(jié)果跟為準確客觀，對解決一下實際微博排名問題提供了一些新的思路，具有一定的意義。

表1兩種算法影響力排名前十的用戶

［1］馮典．面向微博的數(shù)據(jù)采集和分析系統(tǒng)的設計與實現(xiàn)［D］．北京：北京郵電大學，2013.

［2］王琛，陳庶櫵．一種改進的微博用戶影響力評估算法［J］．信息工程大學學報，2013，14（3）:380-384.

［3］鄧雪，李家銘，曾浩健等.層次分析權重計算方法分析及應用研究［J］．數(shù)學的實踐與認識，2012.24（7）.

Micro-Blog；PageRank；User Influence；UI-Rank

A Ranking Algorithm Estimating Micro-Blog Influence Based on the Improved PageRank

WANG Dong-sheng
（Department of Information Engineering，Shanghai Maritime University，Shanghai 201306）

1007-1423（2015）29-0027-04

10.3969/j.issn.1007-1423.2015.29.007

王東升（1988-），男，江蘇淮安人，碩士研究生，研究方向為軟件開發(fā)方法與軟件項目管理

2015-08-11

2015-09-15

針對微博用戶影響力排名問題，對微博用戶影響力關聯(lián)要素進行分析，將粉絲與關注者的互動行為納入到影響力評定方法之中，提出一種基于PageRank的微博用戶影響力排名算法（UI-Rank算法）。實驗表明算法的計算結(jié)果反映微博用戶自身影響力的實際效果，能夠提高微博用戶影響力排名的準確度。

微博；PageRank；用戶影響力；UI-Rank算法

Accordance with user influence ranking issue of micro-blog，related factors consists in user influence of micro-blog have get analysis.Interactive behaviors between fans and followers are integrated into method of influence evaluation，presents the user influence ranking algorithm（UI-rank）of micro-blog based on PageRank.Experiment shows that computing result of the algorithm is quite consistent with actual effect of user themselves influence and it can improve accuracy of user influence ranking of micro-blog.