基于PageRank改進(jìn)算法的微博影響力排名

王東升

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

基于PageRank改進(jìn)算法的微博影響力排名

王東升

（上海海事大學(xué)信息工程學(xué)院，上海201306）

0　引言

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

1　算法原型

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

2　改進(jìn)UI-Rank算法設(shè)計(jì)

綜合用戶(hù)j的影響力值為：

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

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

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

2.1粉絲參與度

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

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

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

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

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

F（i）表示用戶(hù)i的關(guān)注者集合，即全部好友集合，

其中H（i，j）為用戶(hù)i與其關(guān)注者j互動(dòng)程度。h1，h2，h3為對(duì)應(yīng)參數(shù)的權(quán)重。

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

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

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

2.2用戶(hù)活客觀躍度

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

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

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

用戶(hù)j的客觀活躍度為：

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

基于用戶(hù)活客觀躍度時(shí)用戶(hù)i分配給其關(guān)注者j的比例為：

其中F（i）表示用戶(hù)i的關(guān)注者集合，即全部好友集合，v，j F（i）。

2.2微博影響度

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

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

則基于微博影響度時(shí)用戶(hù)i分配給其關(guān)注者j的比例為：

其中F（i）表示用戶(hù)i的關(guān)注者集合，即全部好友集合，v，j∈F（i）。

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

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

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

4　結(jié)語(yǔ)

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

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

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

［2］王琛，陳庶櫵．一種改進(jìn)的微博用戶(hù)影響力評(píng)估算法［J］．信息工程大學(xué)學(xué)報(bào)，2013，14（3）:380-384.

［3］鄧雪，李家銘，曾浩健等.層次分析權(quán)重計(jì)算方法分析及應(yīng)用研究［J］．?dāng)?shù)學(xué)的實(shí)踐與認(rèn)識(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-），男，江蘇淮安人，碩士研究生，研究方向?yàn)檐浖_(kāi)發(fā)方法與軟件項(xiàng)目管理

2015-08-11

2015-09-15

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

微博；PageRank；用戶(hù)影響力；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.