PageRank模型的改進及微博用戶影響力挖掘算法

毛國君 謝松燕 胡殿軍

(中央財經(jīng)大學(xué)信息學(xué)院 北京 100081)

PageRank模型的改進及微博用戶影響力挖掘算法

毛國君 謝松燕 胡殿軍

(中央財經(jīng)大學(xué)信息學(xué)院 北京 100081)

隨著Web技術(shù)的發(fā)展，微博逐漸成為當(dāng)下最流行的社交平臺之一。微博中用戶影響力計算是相關(guān)研究中的焦點問題。通過對PageRank模型的改進，提出一種新的用戶影響力挖掘算法PR4WB(PageRank for MicroBlogs)，解決了傳統(tǒng)的PageRank算法由于頁面權(quán)威值的等分傳遞帶來的潛在誤差過大的問題。PR4WB算法在考慮微博中用戶關(guān)系的同時，利用社會網(wǎng)絡(luò)概念將自身的活躍度、博文質(zhì)量及可信性加以關(guān)聯(lián)，形成動態(tài)的評價模型。基于Twitter數(shù)據(jù)的實驗表明，PR4WB算法能更加準(zhǔn)確、客觀地反映出用戶的實際影響力。

用戶影響力 社會網(wǎng)絡(luò) 微博 推特 PageRank算法

0 引 言

隨著大數(shù)據(jù)時代的到來以及Web2.0技術(shù)的應(yīng)用，在線社會網(wǎng)絡(luò)得到了快速的發(fā)展。微博作為一種重要的社交平臺，已經(jīng)在社會、政治、生活等方面成為不可忽略的輿情傳播載體。國內(nèi)使用最多的微博平臺是新浪微博，而國際上使用較為廣泛的微博服務(wù)則是Twitter。據(jù)統(tǒng)計，截至2014年7月，Twitter的活躍注冊用戶數(shù)已超過6億，而且每日平均新增用戶數(shù)為135 000，平均每日發(fā)表微博數(shù)為5 800萬。因此，微博是一個用戶數(shù)目多、博文帖子多的一個現(xiàn)代社交媒介。然而，微博中的用戶是不對等的，博文也有輕重之分，所以微博中用戶影響力的計算除了簡單地考慮用戶的鏈接關(guān)系外，也應(yīng)該綜合地利用用戶的活躍程度、博文數(shù)量及質(zhì)量和用戶的可信度等因素。

已經(jīng)出現(xiàn)的基于PageRank模型的微博用戶影響力計算和排名方法更多地是考慮用戶的鏈接數(shù)目，對于用戶的博文質(zhì)量及可信程度關(guān)注較少，因此很難客觀地評價用戶的影響力。特別是，由于缺乏對用戶動態(tài)表現(xiàn)(如活躍度)、可信度(如是否認(rèn)證)等的評估，使得計算結(jié)果距離實際用戶的影響力相差較大。本文將分析傳統(tǒng)的PageRank算法在解決微博用戶影響力挖掘中可能出現(xiàn)的問題，在此基礎(chǔ)上通過嵌入用戶活躍度、博文質(zhì)量及可信度等因素的評估結(jié)果，改進傳統(tǒng)的PageRank模型，形成適合于微博中用戶影響力挖掘的動態(tài)評價算法。

1 相關(guān)研究及PageRank模型的發(fā)展

PageRank模型[1]是由Google公司的兩位創(chuàng)始人拉里·佩琪和謝爾蓋·布林共同提出的。該模型的最初動因是實現(xiàn)網(wǎng)絡(luò)上的網(wǎng)頁排名，因此該技術(shù)被廣泛應(yīng)用到網(wǎng)絡(luò)的搜索引擎設(shè)計中。由于PageRank模型本質(zhì)上是對有向圖的節(jié)點等級的計算技術(shù)，所以它也能應(yīng)用到其他的領(lǐng)域。特別地，PageRank算法近年已經(jīng)被應(yīng)用到微博的用戶影響力排名中。

Tunkelang[2]等利用Twitter用戶節(jié)點之間的關(guān)注(Follow)關(guān)系，構(gòu)造了一張基于鏈接關(guān)系的有向圖，并且利用PageRank模型實現(xiàn)了Twitter用戶的影響力排序。Weng[3]等也成功地從Twitter中構(gòu)建了一個好友關(guān)系圖，并且利用PageRank算法思想提出了一個被稱為TwitterRank的算法。之后，Weng[4]等也將用戶興趣加入到評價體系中，改進了TwitterRank算法，可以更好地實現(xiàn)在某一特定話題討論中的用戶影響力分析。

事實上，微博影響力研究已經(jīng)成為一個重要的交叉研究課題。有3個重要的研究視點被關(guān)注：(1) 將微博用戶及其交互行為在社會網(wǎng)絡(luò)的分析框架下進行分析[5-6]；(2) 利用信息傳播理論研究微博中的網(wǎng)絡(luò)傳播動力學(xué)行為規(guī)律，發(fā)現(xiàn)傳播中的關(guān)鍵用戶及其行為[7]；(3) 從數(shù)據(jù)挖掘觀點，進行數(shù)據(jù)的關(guān)聯(lián)性分析，發(fā)現(xiàn)微博中數(shù)據(jù)隱含的規(guī)律性知識[8-9]。這些研究都有一個核心技術(shù)支撐，即有向圖分析。微博中的用戶通過用戶間的交互行為可以構(gòu)成特定的有向圖結(jié)構(gòu)；微博中的用戶就是有向圖的節(jié)點、并且微博中的社會關(guān)系或者博文傳播可以形成有向圖的??；微博中的數(shù)據(jù)可以在有向圖的邏輯結(jié)構(gòu)下實施數(shù)據(jù)挖掘技術(shù)。從這個意義上說，PageRank模型能夠?qū)⒁陨?種視點從技術(shù)層面上加以統(tǒng)一。

原始的PageRank模型是針對網(wǎng)站中的網(wǎng)頁的重要性評估提出來的，通過計算每個頁面的權(quán)威值來實現(xiàn)頁面的等級劃分。簡單地說，一個頁面的權(quán)威值就是所有指向該頁面的各個頁面平均分配給該頁面的權(quán)威值之和[1]。很顯然，基于這樣模型的PageRank算法是一個逐層進行節(jié)點權(quán)威值計算的過程。谷歌公司在實際應(yīng)用中發(fā)現(xiàn)了原始PageRank算法的致命缺點：假如一個頁面節(jié)點沒有出度，特別是入度又很大，就可能造成節(jié)點的權(quán)威值“滯留”，進而使傳遞受阻。解決這個問題的基本方法就是引入隨機沖浪模型，這也成為目前使用的最廣泛的PageRank模型[10]?；陔S機沖浪的PageRank模型的頁面權(quán)威值計算如下：

(1)

其中：PR(x)代表頁面x的權(quán)威值；d(∈[0,1])為阻尼系數(shù)，暗示頁面的隨機跳轉(zhuǎn)概率為1-d；B(x)表示指向頁面x的網(wǎng)頁的集合；N(x)表示頁面x鏈出的網(wǎng)頁集合。

式(1)給出的模型需要轉(zhuǎn)變成可計算的算法來完成。各種版本的PageRank算法都是通過多次迭代計算實現(xiàn)的，其中最流行的迭代方式是通過所謂的轉(zhuǎn)移概率矩陣技術(shù)來實施的[8]。簡單地說，一個轉(zhuǎn)移概率矩陣表示為M=(mi,j)，其中mi,j是頁面j跳轉(zhuǎn)到頁面i的概率。目前使用的PageRank算法大多都是采用等分概率的方法來進行傳遞的。例如：圖1給出了一個4個節(jié)點的有向圖，對應(yīng)著4個不同的頁面及其鏈接關(guān)系。通過傳統(tǒng)的PageRank算法可以獲得對應(yīng)的轉(zhuǎn)移概率矩陣M：

圖1 一個頁面鏈接對應(yīng)有向圖

這樣，設(shè)n是頁面節(jié)點的數(shù)目，R=(r1,r2, …,rn)T表示頁面節(jié)點的權(quán)威值向量，則可以通過多次迭代執(zhí)行下面的式(2)來逐步逼近式(1)的效果：

Ri+1=(1-d)·I+d·M·Ri

(2)

其中：I為全1向量，即(1,1,…,1)T；Ri(i=1,2,…)是第i次迭代得到的權(quán)威值向量；迭代的終止條件可以通過迭代次數(shù)或者最近兩次的迭代結(jié)果的比較來實現(xiàn)。

基于傳統(tǒng)的PageRank模型，本文的技術(shù)解決方案簡單歸納為：首先，利用社會網(wǎng)絡(luò)概念和分析工具構(gòu)建微博數(shù)據(jù)的邏輯分析結(jié)構(gòu)(有向圖)；然后，考慮博文傳播導(dǎo)致的用戶行為的影響力要素，形成節(jié)點級的綜合的行為評測模型；最后，改進傳統(tǒng)的PageRank算法的模式演化過程，形成微博用戶影響力的動態(tài)挖掘算法。

2 PageRank模型的改進及微博用戶影響力挖掘

傳統(tǒng)的PageRank模型和算法的思想可以用在微博用戶影響力評估中，但是要想獲得更準(zhǔn)確的評估結(jié)果，一個關(guān)鍵的問題需要解決：假如采用傳統(tǒng)的PageRank模型來完成平均權(quán)威值傳遞的話，那么實際上是在承認(rèn)所有的用戶是絕對對等的，這和微博中實際用戶的情況相差甚遠。

雖然微博中的用戶關(guān)系并不復(fù)雜，但是作為一種特殊的社交媒體有其特殊性。例如，最常用社會網(wǎng)絡(luò)工具是通過用戶的“關(guān)注(follow)”行為來構(gòu)建有向圖的[8]。然而，微博作為一個公共的開放平臺，其用戶的權(quán)威性或者說重要性差別是很大的。一個大V用戶的關(guān)注數(shù)目遠遠多于一個普通用戶；一個認(rèn)證用戶其傳播信息的可信度要明顯高于非認(rèn)證用戶；一個致力于推銷自己產(chǎn)品的維店用戶，即使是博文再多，可能對于大多數(shù)用戶而言都是當(dāng)作噪音數(shù)據(jù)來看待的。因此，如何更準(zhǔn)確地確定和實施微博中用戶的權(quán)威值的傳遞策略是必須要面對的問題。我們的策略是通過對用戶活躍度、博文質(zhì)量及可信度的評估，按著重要程度形成節(jié)點權(quán)威值的不對等傳遞，以真實地反映微博用戶的影響力。

用戶的活躍度被認(rèn)為是衡量用戶影響力的重要因素之一[10]。典型的微博用戶活躍度通過用戶在微博平臺發(fā)表博文的多少來評價，通常使用式(3)[11-12]來計算：

Activity(i)=ni/N

(3)

其中：Activity(i)代表用戶i的活躍度；ni是用戶i發(fā)表的博文數(shù)目；N為全部用戶發(fā)表的微博總數(shù)。

依據(jù)式(3)，用戶活躍度可以很好地反映用戶發(fā)表博文的數(shù)量。然而，除了尊重博文發(fā)表越多的用戶可能影響力越大這一事實外，至少兩個因素需要在評價一個用戶的影響力時也要加以考慮：(i)用戶發(fā)文的質(zhì)量；(ii)用戶的可信度。

用戶的質(zhì)量表示用戶發(fā)表博文質(zhì)量的高低，博文質(zhì)量值越高，就越多人轉(zhuǎn)發(fā)。當(dāng)高質(zhì)量的博文數(shù)發(fā)表的多時，說明該用戶在這個話題圈內(nèi)擁有的話語權(quán)越高，即權(quán)威值越高。有研究把高質(zhì)量博文定義為轉(zhuǎn)發(fā)量超過一定量的博文，用戶的質(zhì)量值即該用戶所發(fā)的高質(zhì)量博文的占比。遵循這樣的原則，我們把轉(zhuǎn)發(fā)量超過300的博文定義為高質(zhì)量博文，且最簡單的評估用戶質(zhì)量值的方式可以用式(4)給出：

Quality(i)=mi/ni

(4)

其中：Quality(i)代表用戶i的質(zhì)量值；mi是用戶i發(fā)表的高質(zhì)量博文數(shù)目；ni為該用戶發(fā)表的微博總數(shù)。

用戶的可信度可以通過是否被微博平臺認(rèn)證來衡量，同時認(rèn)證用戶的好友粉絲數(shù)也是影響其可信度的重要因素。根據(jù)用戶好友粉絲數(shù)的多少可以衡量該用戶在發(fā)微博時能夠影響到多少人，好友粉絲數(shù)越多就能讓越多的人看到微博消息，也就表示該用戶的影響力越大。最簡單地方法可以通過式(5)完成：

(5)

其中：B(i)和C(i)分別代表用戶i的鏈入和鏈出節(jié)點數(shù)目，即用戶i的好友粉絲數(shù)。

接下來的問題就是如何將用戶活躍度、博文質(zhì)量及用戶可信度整合成一個綜合評價模型，并把它用于PageRank模型的權(quán)威值傳遞過程中。依據(jù)式(3)-式(5)，可以使用式(6)形成一個綜合評價參數(shù)w(i)：

w(i)=Activity(i)+Quality(i)+Confidence(i)

(6)

于是，w(i)可以用來修正PageRank模型，形成加權(quán)轉(zhuǎn)移概率矩陣M=(mi,j)，mi,j表示節(jié)點j傳遞給節(jié)點i的權(quán)威值，可以通過式(7)來計算：

(7)

對于圖1所示的社會網(wǎng)絡(luò)，假如我們已經(jīng)獲得各個節(jié)點的評價參數(shù)：w(A)=0.10、w(B)=0.15、w(C)=0.20、w(D)=0.15，則對應(yīng)的加權(quán)轉(zhuǎn)移概率矩陣M為：

使用加權(quán)概率轉(zhuǎn)移矩陣，利用PageRank算法思想，我們可以設(shè)計一個綜合考慮用戶活躍度、用戶質(zhì)量及可信度的微博社會網(wǎng)絡(luò)挖掘算法，稱為PR4WB算法。該算法以傳統(tǒng)的PageRank算法為技術(shù)構(gòu)架，將影響微博用戶影響力的關(guān)鍵因素整合進來。算法1給出了PR4WB的偽代碼描述：

算法1 微博用戶影響力向量生成算法PR4WB

輸入：微博用戶社會網(wǎng)絡(luò)圖G；阻尼系數(shù)d；迭代終止條件ε；

輸出：用戶節(jié)點的影響力向量R。

過程描述：

2) Fori∈GDo

3) 計算Activity(i),Quality(i),Confidence(i)；

4)w(i) =Activity(i)+Quality(i) +Confidence(i)；

5)Enddo

6)Fori∈GDo

7)Forj∈GDo

9)M=(mi,j)；

10)R0= (1, 1, …, 1)T；I=R0;

11)Repeat

12)R=(1-d) *I+d*M*R0；

13)R0=R；

14)Until‖R-R0‖≤ε；

15) 輸出R作為最終的影響力向量。

算法1中的步驟1根據(jù)傳統(tǒng)的PageRank算法來計算概率轉(zhuǎn)移矩陣；步驟2-步驟5計算用戶的活躍度、博文質(zhì)量和可信度(見式(3)-式(5))；步驟6-步驟9生成加權(quán)概率轉(zhuǎn)移矩陣；步驟10-步驟15完成所有節(jié)點的影響力計算。

3 實驗與分析

實驗數(shù)據(jù)來自于Twitter平臺。我們采用Twitter提供的API接口獲取了近5年的數(shù)據(jù)，選取了其中3 049位微博用戶，利用Gephi社會網(wǎng)絡(luò)生成工具形成了包含7萬多條(關(guān)注)弧的有向圖。當(dāng)然，3 049個用戶只是全部Twitter用戶中的一小部分，但是這些用戶的關(guān)系網(wǎng)絡(luò)是相對完整的，可以用來檢驗本文算法的有效性和效率。

表1和表2分別給出了利用傳統(tǒng)的PageRank算法和本文的PR4WB算法找出的前十名微博用戶及其對應(yīng)的情況。

表1 傳統(tǒng)的PageRank算法找出的前十名用戶信息表

續(xù)表1

表2 PR4WB算法找出的前十名用戶信息表

對照表1和表2，對相同的數(shù)據(jù)，傳統(tǒng)的PageRank算法和本文的PR4WB算法找到的影響力最高的前10名用戶存在差異。當(dāng)然，我們不能主觀地斷定哪個更好，但是表1的一些問題是可以通過分析被發(fā)現(xiàn)的。例如：(1) PageRank算法排名第1位用戶為非認(rèn)證用戶，而且這段時間發(fā)表的博文數(shù)據(jù)也不多，所以算不上是一個很活躍的用戶。通過我們進一步跟蹤傳統(tǒng)PageRank算法的權(quán)威值計算過程發(fā)現(xiàn)，這主要是由于該用戶的關(guān)注者大多具有很高的權(quán)威值、進而使他的權(quán)威值累計起來很高。(2) 表1中排名第4位的也是一個非認(rèn)證用戶，它的關(guān)注數(shù)也不算多，但是他的排名也很高。究其原因，是Fenng一位IT界的知名人物，其關(guān)注者的影響力很高、而且他很少關(guān)注其他的人。

相比較而言，我們根據(jù)PR4WB算法要求進行了用戶的活躍度、博文質(zhì)量及可信度的評估，并且使用它們改進了PageRank成PR4WB算法，得到了表2的結(jié)果。計算出的影響力排名前十位用戶均為認(rèn)證用戶，而且所發(fā)的博文數(shù)、關(guān)注數(shù)及好友數(shù)都相對較高。另外，我們利用微博的轉(zhuǎn)發(fā)功能來評估博文質(zhì)量，我們發(fā)現(xiàn)好友粉絲數(shù)多的認(rèn)證用戶的質(zhì)量值都較高，這是因為認(rèn)證用戶一般都在發(fā)布消息時具有一定的權(quán)威性，并且其眾多的好友粉絲會對其所發(fā)出的博文進行轉(zhuǎn)發(fā)評論，相較于一般用戶，認(rèn)證用戶的影響力更大。實驗結(jié)果中PR4WB算法得到的前十名用戶大多數(shù)為新聞媒體的官方微博，這些從一個側(cè)面上可以說明，PR4WB算法所得到的排名與現(xiàn)實生活中的實際用戶的影響力更接近。

此外，通過跟蹤傳統(tǒng)的PageRank算法和本文的PR4WB算法的運行時間，我們測試了兩個算法隨用戶數(shù)目增加時對應(yīng)的執(zhí)行時間的變化情況。兩個算法是在同樣的數(shù)據(jù)集和實驗環(huán)境下進行的。實驗是在四核 CPU、4 GB內(nèi)存、Windows 7操作環(huán)境下的計算機實施的。同時，為了說明隨數(shù)據(jù)容量增加執(zhí)行時間的增長規(guī)律，我們從已經(jīng)獲取的Twitter平臺的3 049位用戶對應(yīng)的社會網(wǎng)絡(luò)圖中分別截取了500，1 000，1 500，2 000和2 500個用戶對應(yīng)的網(wǎng)絡(luò)子圖，分別實施PageRank和 PR4WB算法。圖2給出了對應(yīng)的實驗結(jié)果。

圖2 PR4WB算法與PageRank算法所耗時間對比

圖2表明：在同樣的數(shù)據(jù)容量下，PR4WB算法的執(zhí)行時間略高于PageRank算法。這是因為相比傳統(tǒng)的PageRank算法，PR4WB算法需要額外計算用戶活躍度等動態(tài)評估指標(biāo)，所以自然要高些。然而，兩個算法在相同數(shù)據(jù)容量下，差距并不大；而且，隨著數(shù)據(jù)容量(用戶數(shù))的增加，兩者的時間攀升趨勢相當(dāng)，都小于線性增長速率。因此，雖然PR4WB算法是以時間為代價來獲取比PageRank算法更好的挖掘結(jié)果的，但是其時間代價并不高，是一個性價比很高的算法。

4 結(jié) 語

通過對微博中用戶影響力分析中需要考慮的關(guān)鍵因素分析，提出了一種更適合挖掘微博數(shù)據(jù)的加權(quán)PageRank算法，即PR4WB算法。PR4WB算法對于PageRank算法存在的平分權(quán)威值這一問題進行了修正，使得排序結(jié)果更客觀、準(zhǔn)確。通過計算微博用戶的活躍度、博文質(zhì)量及可行度，獲得節(jié)點的權(quán)重，利用權(quán)重修正傳統(tǒng)的PageRank模型的概率轉(zhuǎn)移矩陣。這樣，用戶的影響力排序不僅考慮了社會網(wǎng)絡(luò)中個體之間的鏈接關(guān)系，同時將用戶活躍度等動態(tài)因素參與影響力的排序中，使得微博用戶的影響力評估更全面。實驗結(jié)果表明，相比于傳統(tǒng)的PageRank算法，PR4WB算法用較小的時間代價換取了更準(zhǔn)確的評估效果。

[1] Page L,Brin S,Motwani R,et al.The PageRank citation ranking: bringing order to the web:SIDL-WP-1999-0120[R].Technical Report of Stanford University,1999.

[2] 縣小平.一種改進的PageRank算法[J].太原師范學(xué)院學(xué)報(自然科學(xué)版),2011,10(1):92-94.

[3] Weng J,Lim E P,Jiang J,et al.TwitterRank:finding topic-sensitive influential twitterers[C]//Proceedings of the Third ACM International Conference on Web Search and Data mining.New York,NY,USA:ACM Press,2010:261-270.

[4] Weng J,Yao Y,Leonardi E,et al.Event detection in Twitter:HPL-2011-98[R].Technical Report of HP Laboratories,2011.

[5] 尹紅軍.大規(guī)模社交網(wǎng)絡(luò)中局部興趣社區(qū)發(fā)現(xiàn)研究[D].合肥:中國科學(xué)技術(shù)大學(xué),2014.

[6] Kempe D,Kleinberg J,Tardos é.Maximizing the spread of influence through a social network[C]//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Washington,DC,USA,2003:137-146.

[7] 熊小兵.微博網(wǎng)絡(luò)傳播行為中的關(guān)鍵問題研究[D].鄭州:解放軍信息工程大學(xué),2013.

[8] 丁兆云,賈焰,周斌.微博數(shù)據(jù)挖掘研究綜述[J].計算機研究與發(fā)展,2014,51(4):691-706.

[9] Noordhuis P,Heijkoop M,Lazovik A.Mining Twitter in the cloud:a case study[C]//Proceedings of the 2010 IEEE 3rd International Conference on Cloud Computing (CLOUD),2010:107-114.

[10] 陸研,毛健駿,屠方楠.網(wǎng)絡(luò)信息老化規(guī)律研究——新浪新聞與新浪微博實證研究[J].高等函授學(xué)報(哲學(xué)社會科學(xué)版),2011,24(12):52-55.

[11]JavaA,KolariP,FininT,etal.Modelingthespreadofinfluenceontheblogosphere[C]//Proceedingsofthe15thInternationalWorldWideWebConference(WWW06),Edinburgh,UK,2006:1-7.

[12]ChaM,HaddaiH,BenevenutoF,etal.MeasuringuserinfluenceinTwitter:themillionfollowerfallacy[C]//ProceedingsoftheFourthInternationalAAAIConferenceonWeblogsandSocialMedia,Washington,DC,USA,2010:10-17.

IMPROVEMENT OF PAGERANK MODEL AND MINING ALGORITHM OF MICROBLOG USER INFLUENCE

Mao Guojun Xie Songyan Hu Dianjun

(SchoolofInformation,CentralUniversityofFinanceandEconomics,Beijing100081,China)

With the development of Web technology, microblog has become one of the most popular social platforms. The calculation of user influence in microblog is the focus of related research. Through the improvement of the PageRank model, a new user influences mining algorithm PR4WB (PageRank for Microblog) is proposed to solve the problem that the traditional PageRank algorithm has too much potential error due to the transfer of page authority value. PR4WB algorithm takes into account the user relationship in microblog while using the concept of social network to link its activity, blog quality and credibility to form a dynamic evaluation model. Experiments based on Twitter data show that, PR4WB algorithm can more accurately and objectively reflect the user’s actual influence.

User influence Social network Microblog Twitter PageRank algorithm

2016-04-02。國家自然科學(xué)基金項目(61273293)。毛國君，教授，主研領(lǐng)域：數(shù)據(jù)挖掘。謝松燕，碩士生。胡殿軍，碩士生。

TP391.1

A

10.3969/j.issn.1000-386x.2017.05.005