原 野 李 晨 田麗華*

1(西安交通大學(xué)軟件學(xué)院 陜西 西安 710049)2(新浪網(wǎng)技術(shù)(中國(guó))有限公司 北京 100000)

面向微博的PageRank算法的改進(jìn)與應(yīng)用

原 野1,2李 晨1田麗華1*

1(西安交通大學(xué)軟件學(xué)院 陜西 西安 710049)2(新浪網(wǎng)技術(shù)(中國(guó))有限公司 北京 100000)

從海量數(shù)據(jù)下的社會(huì)化網(wǎng)絡(luò)中識(shí)別出各個(gè)領(lǐng)域下產(chǎn)出高質(zhì)量?jī)?nèi)容的具有一定影響力的專家，進(jìn)行具有針對(duì)性的廣告推薦與決策支持，已經(jīng)成為微博數(shù)據(jù)挖掘亟待解決的問(wèn)題之一。從微博的用戶特征和行為特征出發(fā)，確定了采集博文的規(guī)則與互動(dòng)量計(jì)算公式，并應(yīng)用PageRank算法對(duì)微博用戶影響力計(jì)算時(shí)存在的數(shù)據(jù)陳舊性和主題不相關(guān)性的問(wèn)題進(jìn)行了改進(jìn)，最后分別基于MapReduce和Spark的并行計(jì)算框架對(duì)算法進(jìn)行了實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果表明，該挖掘方法具有較好的準(zhǔn)確性，在Spark并行計(jì)算框架下表現(xiàn)出較高的性能，尤其適合大規(guī)模數(shù)據(jù)集的場(chǎng)景。

微博 用戶影響力 PageRank Spark 大數(shù)據(jù)

0 引 言

微博是一種典型的Web 2.0社交網(wǎng)絡(luò)服務(wù)SNS(Social Networks Service)應(yīng)用[1]。它以短文本、圖片、小視頻等方式拓展了用戶的交流途徑，創(chuàng)建了一個(gè)類似傳統(tǒng)社區(qū)的網(wǎng)絡(luò)虛擬圈。新浪微博由于其對(duì)產(chǎn)品的精準(zhǔn)定位，在競(jìng)爭(zhēng)中脫穎而出，領(lǐng)先于國(guó)內(nèi)同類產(chǎn)品，已經(jīng)融入到社會(huì)生活的方方面面，成為了獲取實(shí)時(shí)信息的最佳平臺(tái)。其擁有高達(dá)1.4億的日活躍用戶數(shù)，每天有數(shù)百GB甚至TB級(jí)別的結(jié)構(gòu)化數(shù)據(jù)入庫(kù)。因此，從海量數(shù)據(jù)下的社會(huì)化網(wǎng)絡(luò)中識(shí)別出各領(lǐng)域下的專家和具有一定影響力的用戶，進(jìn)而利用這些識(shí)別出的專家和用戶進(jìn)行具有針對(duì)性的推薦，已經(jīng)成為亟待解決的問(wèn)題。

對(duì)于高影響力微博用戶的挖掘，不少研究從PageRank算法和評(píng)估模型入手，進(jìn)行了影響力評(píng)估[2-5]。這些研究專注于某個(gè)模型或者算法的改進(jìn)，為建立用戶評(píng)價(jià)模型提出了多種思路，但均沒(méi)有考慮挖掘數(shù)據(jù)的規(guī)模、可應(yīng)用性和可擴(kuò)展性，無(wú)法產(chǎn)生實(shí)際的應(yīng)用價(jià)值。其中，文獻(xiàn)[3]結(jié)合用戶潛在的影響力和博文傳播影響力，提出了一種基于PageRank的影響力評(píng)估指標(biāo)，具有一定的合理性和有效性。但這些指標(biāo)缺乏通用性，只能描述特定的少量用戶，因此，其計(jì)算的范圍被局限，不能針對(duì)海量的用戶進(jìn)行計(jì)算與應(yīng)用。針對(duì)用戶推薦與挖掘，也有一些研究從其他方面入手，利用聚類、鏈接分析、標(biāo)簽預(yù)測(cè)等方法提出了一系列描述用戶興趣和影響力的方法及模型[6-8]。這些模型從不同的角度對(duì)用戶影響力進(jìn)行了建模及實(shí)驗(yàn)分析，每種方法都有各自的側(cè)重點(diǎn)，但同樣缺乏對(duì)海量數(shù)據(jù)集下的實(shí)證。如文獻(xiàn)[7]從鏈接分析和用戶行為兩個(gè)角度衡量用戶的影響力，提出了微博用戶影響力指數(shù)模型。但該模型以整體用戶為對(duì)象，沒(méi)有考慮微博用戶的聚類化，即在不同領(lǐng)域下分別進(jìn)行影響力指數(shù)的計(jì)算，使用戶間的對(duì)比更有意義。

本文通過(guò)分析微博的互動(dòng)機(jī)制，進(jìn)而將用戶的行為量化，基于PageRank提出了一種微博用戶影響力計(jì)算方法。該方法改進(jìn)了PageRank的主題陳舊性，引入了時(shí)間區(qū)間，限定分析的數(shù)據(jù)為最新數(shù)據(jù)。同時(shí)，方法還對(duì)領(lǐng)域進(jìn)行了區(qū)分，針對(duì)領(lǐng)域內(nèi)用戶而不是整體微博用戶進(jìn)行計(jì)算，大大改善了算法的主題不相關(guān)特點(diǎn)。該算法兼顧了挖掘的覆蓋度和準(zhǔn)確性，并針對(duì)并行計(jì)算框架做了設(shè)計(jì)與應(yīng)用，使得用戶影響力計(jì)算方法能夠在大數(shù)據(jù)規(guī)模下高效運(yùn)行，具有很高的可應(yīng)用性和可擴(kuò)展性。

1 PageRank算法

PageRank算法，又稱為佩奇排名算法，是谷歌用來(lái)衡量網(wǎng)頁(yè)重要性、標(biāo)識(shí)網(wǎng)頁(yè)等級(jí)的一種方法[9]。PageRank算法的基本思想是：確立一個(gè)評(píng)估網(wǎng)頁(yè)的權(quán)重值(PR值)，該值標(biāo)志著一個(gè)網(wǎng)頁(yè)的相關(guān)性和質(zhì)量。在揉合考慮多個(gè)特征元素之后，評(píng)估指向某個(gè)網(wǎng)頁(yè)的其他網(wǎng)頁(yè)的重要性，再給出這個(gè)網(wǎng)頁(yè)的重要性。即“被越多優(yōu)秀的網(wǎng)頁(yè)所指向的網(wǎng)頁(yè)，它是優(yōu)質(zhì)網(wǎng)頁(yè)的概率會(huì)更大”。

PageRank算法在入鏈數(shù)的基礎(chǔ)上考慮了網(wǎng)頁(yè)質(zhì)量的因素，提出了兩個(gè)基本的假設(shè)：

(1) 數(shù)量假設(shè)：在網(wǎng)頁(yè)圖模型中，如果某個(gè)頁(yè)面得到的入鏈數(shù)數(shù)目越多，則證明其具有更高的重要性。

(2) 質(zhì)量假設(shè)：在網(wǎng)頁(yè)圖模型中，如果指向某個(gè)頁(yè)面的多個(gè)頁(yè)面的質(zhì)量越高(PR值越大)，則該頁(yè)面的重要性就會(huì)越高。

PageRank算法類似于一個(gè)投票系統(tǒng)，每個(gè)人擁有一定的初始權(quán)值，PageRank算法是公平的，因此此權(quán)重值在開(kāi)始時(shí)是一致的，并不會(huì)考慮其他元素的影響。隨后令每個(gè)人對(duì)其他人進(jìn)行投票，且可以將自己的票按照一定的比例分別投給多個(gè)人。在一輪投票完畢后，每個(gè)用戶會(huì)得到匯總后的投票數(shù)，該投票數(shù)就是其新一輪開(kāi)始投票時(shí)具有的票數(shù)(權(quán)值)。如此反復(fù)投票N次，直到每個(gè)人獲得的投票數(shù)保持穩(wěn)定的時(shí)候，結(jié)束運(yùn)算，每個(gè)人的最終得票值即為其重要性。

在網(wǎng)頁(yè)中，某些網(wǎng)頁(yè)是沒(méi)有網(wǎng)頁(yè)指向的，也有某些網(wǎng)頁(yè)是沒(méi)有任何鏈接的，這些孤立網(wǎng)頁(yè)會(huì)在迭代計(jì)算的過(guò)程中逐漸降低得分直至為0或者在某次排名中丟失，出現(xiàn)“排名泄漏”和“排名下沉”。因此，PagRank中存在一個(gè)阻尼系數(shù)，來(lái)防止這些情況的出現(xiàn)，如式(1)所示：

(1)

其中，P1，P2，…，Pn是被研究的頁(yè)面，N是所有頁(yè)面的數(shù)量，L(Pj)是Pj鏈出頁(yè)面的數(shù)量，M(Pi)是Pi鏈入頁(yè)面的數(shù)量，q為阻尼系數(shù)。

2 微博互動(dòng)機(jī)制

以新浪微博為例，互動(dòng)主要由某些特定的用戶發(fā)布博文來(lái)引發(fā)，整個(gè)互動(dòng)過(guò)程是一對(duì)多的，以某個(gè)用戶的博文或話題為中心，層層傳播，帶動(dòng)起大量普通用戶的參與。因此要觀察研究微博互動(dòng)的機(jī)制，就需要從用戶特征和行為特征兩個(gè)方面出發(fā)。

1) 用戶特征

通過(guò)觀察分析新浪微博近3個(gè)月的熱門微博榜數(shù)據(jù)，可以發(fā)現(xiàn)榜單上的用戶構(gòu)成主要如圖1所示，其中微博會(huì)員是微博的一種收費(fèi)機(jī)制，主要作用在于提升微博用戶發(fā)表博文的傳播力。一般來(lái)說(shuō)，微博會(huì)員活躍度高，內(nèi)容產(chǎn)出質(zhì)量也較高，其占據(jù)了12.35%的熱門微博數(shù)。橙V與藍(lán)V用戶，由于其經(jīng)過(guò)官方認(rèn)證，具有更高的權(quán)威性和可靠性，因此其影響力更大，傳播范圍更廣，分別占據(jù)了15.60%與7.23%的熱門微博數(shù)。對(duì)于人氣草根來(lái)說(shuō)，一般是因?yàn)槟承┨厥馐录蛞l(fā)群體關(guān)注的博文而被大家關(guān)注，這類用戶未來(lái)產(chǎn)生高影響力的可能性非常大。由上述微博會(huì)員、橙V、藍(lán)V、人氣草根構(gòu)成了一個(gè)能力用戶集合，該集合內(nèi)用戶具備長(zhǎng)期穩(wěn)定輸出高質(zhì)量?jī)?nèi)容的能力。同時(shí)，集合需要排除一部分用戶，即少量轉(zhuǎn)發(fā)抽獎(jiǎng)、營(yíng)銷等賬號(hào)。該類用戶能夠上榜往往是由投入了大量資金而出現(xiàn)短暫性爆發(fā)的關(guān)注度，其下的用戶一般不具備長(zhǎng)期穩(wěn)定輸出高質(zhì)量?jī)?nèi)容的能力。由此，確定了博文采集數(shù)據(jù)源的集合為上面提到的能力用戶集合，而將其他類用戶排除在外。

圖1 熱門微博用戶構(gòu)成

2) 行為特征

微博用戶間的互動(dòng)特征在很大程度上是由用戶發(fā)布消息的屬性特征所顯現(xiàn)出來(lái)的[10]?；?dòng)行為可以細(xì)化和歸結(jié)為多個(gè)種類，但從博文的影響力和擴(kuò)散性而言，互動(dòng)行為主要分為轉(zhuǎn)發(fā)、評(píng)論、贊等三種用戶行為，用戶間互動(dòng)的中心可以是話題、博文或者評(píng)論，以原創(chuàng)博文為中心的對(duì)話環(huán)狀結(jié)構(gòu)如圖2所示。其中原創(chuàng)博文外第一圈為第一層傳播者，影響力較高，此時(shí)也存在贊行為，但更為注重的是其轉(zhuǎn)發(fā)和評(píng)論，虛線表示原創(chuàng)博文用戶有時(shí)會(huì)回轉(zhuǎn)第一層傳播者的評(píng)論以獲得新一輪的關(guān)注。下面是針對(duì)三種用戶行為的具體介紹。

① 轉(zhuǎn)發(fā)。該行為是指某個(gè)用戶在閱讀了一篇博文(長(zhǎng)博文或短博文)之后產(chǎn)生了強(qiáng)烈的共鳴或反對(duì)情緒。其表現(xiàn)出該用戶對(duì)該博文產(chǎn)生了較強(qiáng)的關(guān)注且急于抒發(fā)自己的直觀感受。轉(zhuǎn)發(fā)數(shù)的高低反映了消息擴(kuò)散程度和傳播覆蓋面的廣度。

② 評(píng)論。評(píng)論是閱讀博文后有所感觸，由此產(chǎn)生的意見(jiàn)和看法。評(píng)論數(shù)的高低反映了消息在擴(kuò)散中引發(fā)的反響程度，也直接的體現(xiàn)了消息的影響力。

③ 贊。此行為只是單純的表達(dá)對(duì)一條博文是否認(rèn)同，其用戶主觀性比轉(zhuǎn)發(fā)和評(píng)論都要弱。贊的數(shù)目只能間接的反映一條博文的影響力。

圖2 以原創(chuàng)博文為中心的環(huán)狀傳播

3) 數(shù)據(jù)源過(guò)濾規(guī)則與互動(dòng)行為量化

根據(jù)對(duì)用戶特征與行為特征的分析，可以確定微博用戶影響力計(jì)算過(guò)程中使用的博文數(shù)據(jù)源的過(guò)濾規(guī)則，并可以得出用戶互動(dòng)量的計(jì)算公式。

① 過(guò)濾規(guī)則。以博文為中心，就要先提取出各個(gè)領(lǐng)域下的高質(zhì)量博文，這里采用用戶特征屬性來(lái)過(guò)濾這些博文。以新浪微博提供的API為例，博文數(shù)據(jù)源分為5個(gè)等級(jí)，橙V用戶博文、微博會(huì)員博文、高質(zhì)量可信用戶博文、普通用戶博文以及營(yíng)銷信息等低質(zhì)量博文。根據(jù)規(guī)則，確定普通用戶及以上等級(jí)的博文為數(shù)據(jù)源，之所以采用普通用戶博文，是由于某些普通用戶可能潛在內(nèi)容輸出能力，進(jìn)而成為新的微博人氣草根。確定用戶特征后，根據(jù)博文的原創(chuàng)標(biāo)識(shí)字段，進(jìn)一步確定博文是原創(chuàng)博文，所有轉(zhuǎn)發(fā)以及二次原創(chuàng)博文都將被排除在外。確定了過(guò)濾規(guī)則后，經(jīng)過(guò)過(guò)濾篩選的博文成為初始數(shù)據(jù)源。

② 互動(dòng)行為量化。本文提出了相應(yīng)的用戶間的互動(dòng)行為的量化，闡述如下。在T1到T2時(shí)間段內(nèi)，某用戶對(duì)另一用戶的所有博文所產(chǎn)生的互動(dòng)行為的總和，稱為該用戶對(duì)單個(gè)用戶的互動(dòng)行為量，如式(2)所示：

(2)

而在T1到T2時(shí)間段內(nèi)，某用戶對(duì)另一個(gè)用戶的互動(dòng)行為量占其某時(shí)間段內(nèi)總行為量的占比，稱為用戶對(duì)單個(gè)用戶的互動(dòng)行為概率，如式(3)所示：

(3)

其中，確定轉(zhuǎn)發(fā)、評(píng)論、贊行為的影響力因子分別為a、b、c，三個(gè)因子之和為1。T1、T2為時(shí)間點(diǎn)，所有博文的轉(zhuǎn)發(fā)、評(píng)論、贊的總次數(shù)分別為c_repo、c_cmt、c_like。

3 基于PageRank的微博用戶影響力計(jì)算方法

在以博文為中心的環(huán)狀傳播中，若某用戶的博文產(chǎn)生的轉(zhuǎn)發(fā)、評(píng)論、贊的數(shù)目越大，則其更容易出現(xiàn)在微博頭條之上，也代表其重要性和影響力更大。如果在與某條微博發(fā)生互動(dòng)行為的用戶當(dāng)中，具有高影響力和權(quán)重的高質(zhì)量用戶數(shù)量更多，則表明該博文的用戶影響力更大。因此，微博的互動(dòng)機(jī)制完全符合PageRank算法的基本條件，可以采用PageRank算法來(lái)進(jìn)行微博用戶影響力的計(jì)算。針對(duì)PageRank算法應(yīng)用于微博時(shí)存在的問(wèn)題，本文在其對(duì)微博影響力的計(jì)算方面進(jìn)行了相應(yīng)的改進(jìn)。

1) 數(shù)據(jù)陳舊性

在PageRank算法的基本原理中，網(wǎng)頁(yè)的PR值均勻地分配給鏈出的網(wǎng)頁(yè)，這樣會(huì)造成存在時(shí)間比較久的舊網(wǎng)頁(yè)被鏈接次數(shù)明顯高于新網(wǎng)頁(yè)，從而使得舊網(wǎng)頁(yè)P(yáng)R值高但內(nèi)容陳舊，新網(wǎng)頁(yè)P(yáng)R值低但內(nèi)容重要[11]。本文提出的在微博中應(yīng)用的PageRank算法通過(guò)引入時(shí)間區(qū)間的方法，來(lái)解決了這個(gè)問(wèn)題。引入算法進(jìn)行計(jì)算的用戶博文數(shù)據(jù)，限定在一定時(shí)間段內(nèi)，這樣一來(lái)，由用戶產(chǎn)生的互動(dòng)量就被限制在了最新區(qū)間內(nèi)，可以實(shí)時(shí)、動(dòng)態(tài)反映用戶最新的影響力情況。

2) 主題相關(guān)性

PageRank應(yīng)用在網(wǎng)頁(yè)鏈接排名中的另一個(gè)缺點(diǎn)是忽略了主題性，導(dǎo)致結(jié)果的相關(guān)性和主題性降低[12]。而本文以博文為中心的影響力的計(jì)算是限定在一定領(lǐng)域內(nèi)的。多個(gè)領(lǐng)域下的數(shù)據(jù)可以混合并同時(shí)進(jìn)行運(yùn)算，一個(gè)領(lǐng)域下的能力不對(duì)另一個(gè)領(lǐng)域下的能力產(chǎn)生任何影響，由此，在確定了領(lǐng)域的同時(shí)又保證了計(jì)算的公平性和準(zhǔn)確性。

根據(jù)上述結(jié)論，本文確定了以博文為中心，以用戶博文的互動(dòng)量為用戶影響力的評(píng)價(jià)標(biāo)準(zhǔn)，具體流程如圖3所示。

圖3 微博用戶影響力計(jì)算流程圖

1) 初始權(quán)值和概率轉(zhuǎn)移矩陣的建立

在得到了互動(dòng)量計(jì)算公式之后，就可以考慮將其應(yīng)用到PageRank算法之中了。應(yīng)用PagekRank算法最重要也是最基本的流程為兩步：第一步建立概率轉(zhuǎn)移矩陣，上述用戶對(duì)單個(gè)用戶的行為概率就是概率轉(zhuǎn)移矩陣中的概率值。第二步初始化權(quán)值，對(duì)不同領(lǐng)域下的用戶按照一定的規(guī)則賦初值。規(guī)則如下：

① 用戶數(shù)在1千萬(wàn)以下的領(lǐng)域：用戶初始權(quán)值為1/E。這里E為該領(lǐng)域下的總數(shù)。

② 用戶數(shù)在1千萬(wàn)以上的領(lǐng)域：用戶初始權(quán)值為1/E。這里一般取E>107,才能保證算法收斂時(shí)，所得權(quán)值不至過(guò)大而給后續(xù)計(jì)算帶來(lái)問(wèn)題。

2) 迭代計(jì)算過(guò)程

將初始權(quán)值與概率矩陣相乘，相乘得到的結(jié)果為新一輪的權(quán)值，之后將新權(quán)值繼續(xù)與概率矩陣相乘，重復(fù)迭代計(jì)算至兩次結(jié)果差值小于ε，得到最終計(jì)算結(jié)果。

此處偽代碼如下，其中X為權(quán)值(x1，x2，…，xn)，A為概率轉(zhuǎn)移矩陣：

R=AX;

while(true ) {

if(|X-R|<ε) {

//如果最后兩次的結(jié)果近似或者相同，返回

return R;

} else{

X=R;

R=AX;

}

}

4 算法并行化實(shí)現(xiàn)及結(jié)果分析

根據(jù)算法的設(shè)定，取某一時(shí)間段的博文進(jìn)行處理分析與計(jì)算，一般來(lái)說(shuō)，離線分析取時(shí)間跨度在2個(gè)月以上的博文數(shù)據(jù)較為合適，而每天在微博全領(lǐng)域下產(chǎn)生的博文經(jīng)過(guò)過(guò)濾后數(shù)據(jù)量仍在千萬(wàn)級(jí)別，即需要處理2個(gè)月近億條(TB級(jí)別)的數(shù)據(jù)，而這只是博文數(shù)據(jù)。在計(jì)算互動(dòng)量時(shí)，針對(duì)每一條博文都有數(shù)十萬(wàn)的轉(zhuǎn)發(fā)、評(píng)論、贊，數(shù)據(jù)量的規(guī)模已經(jīng)遠(yuǎn)遠(yuǎn)超過(guò)了單機(jī)所能處理的范圍。因此，必須采用分布式系統(tǒng)下的分布式計(jì)算框架，才能夠滿足算法運(yùn)行的需求。本文從兩種最流行的分布式計(jì)算框架出發(fā)，對(duì)算法進(jìn)行了并行化設(shè)計(jì)，并在之后對(duì)其進(jìn)行性能分析比較，最終確定出適合的運(yùn)算框架。

4.1 MapReduce與Spark計(jì)算框架下的迭代計(jì)算設(shè)計(jì)

1) 數(shù)據(jù)采集與格式

本文通過(guò)使用新浪微博內(nèi)部API以及數(shù)據(jù)倉(cāng)庫(kù)來(lái)獲取新浪微博的用戶數(shù)據(jù)，所有數(shù)據(jù)均為線上真實(shí)數(shù)據(jù)。數(shù)據(jù)的格式、初始權(quán)值及概率轉(zhuǎn)移矩陣的全部數(shù)據(jù)以行文本格式出現(xiàn)。通過(guò)多級(jí)hive操作及MapReduce程序的清理轉(zhuǎn)化，得到了參與計(jì)算的初始數(shù)據(jù)集合。其中，某領(lǐng)域下初始權(quán)值的文本存儲(chǔ)格式如表1所示，鄰接矩陣的文本存儲(chǔ)格式如表2所示。借助加入標(biāo)簽與用戶uid組合，可以將用戶加入到不同領(lǐng)域的計(jì)算中去，如果某用戶在多個(gè)領(lǐng)域下均存在內(nèi)容輸出能力，在這種方式下由于標(biāo)簽的存在，用戶在各領(lǐng)域下的計(jì)算就不會(huì)產(chǎn)生相互影響。

表1 初始權(quán)值文本存儲(chǔ)格式示例

表2 初始鄰接矩陣文本存儲(chǔ)格式示例

2) MapReduce下的迭代計(jì)算設(shè)計(jì)

在使用python編寫的MapReduce代碼中，不能將全部的初始權(quán)值、矩陣載入內(nèi)存后做矩陣乘法。因?yàn)閿?shù)據(jù)量的規(guī)模巨大，集群中在高負(fù)荷運(yùn)算下沒(méi)有一個(gè)單點(diǎn)的內(nèi)存可以載入全部的用戶權(quán)值集合。因此，將每一個(gè)用戶的權(quán)值分別乘以矩陣中的它對(duì)應(yīng)的那一行的概率值(即某個(gè)點(diǎn)的全部出度的值)，對(duì)整個(gè)矩陣做了這樣的操作后，得到一個(gè)臨時(shí)矩陣TMP_MATRIX。該矩陣為概率值乘以權(quán)值得到的矩陣，其每一列(即某個(gè)點(diǎn)的全部入度對(duì)應(yīng)的值)相加后的值的和，就是要得到的這一輪迭代的某個(gè)用戶下的新權(quán)值，再將新權(quán)值作為輸入返回迭代計(jì)算(見(jiàn)圖4中“迭代計(jì)算”部分所示)。這樣一來(lái)，就將龐大的矩陣計(jì)算拆分成了多個(gè)可以并行計(jì)算的任務(wù)，而這些任務(wù)之間又相互沒(méi)有任何依賴關(guān)系，可以很輕松地將其轉(zhuǎn)化為MapReduce程序進(jìn)行計(jì)算。在編寫MapReduce程序時(shí)，需要巧妙地利用HadoopStreamming將第一列認(rèn)定為進(jìn)入shuffle階段的鍵值的特性，通過(guò)拆分、合并、轉(zhuǎn)化標(biāo)簽類別TagCategory和uid來(lái)實(shí)現(xiàn)迭代的兩個(gè)步驟。

MapReduce下的計(jì)算過(guò)程如圖4所示。

圖4 MapReduce框架下微博用戶影響力計(jì)算過(guò)程

3) Spark計(jì)算框架下的迭代計(jì)算設(shè)計(jì)

Spark框架計(jì)算過(guò)程使用與MapReduc計(jì)算相同的數(shù)據(jù)作為輸入源。根據(jù)使用的初始權(quán)值數(shù)據(jù)和概率轉(zhuǎn)移矩陣數(shù)據(jù)，Spark從HDFS上讀取文件進(jìn)入內(nèi)存并創(chuàng)建了兩個(gè)不同的彈性數(shù)據(jù)集rdd_pr_value和rdd_pr_relation，得到初始rdd后，經(jīng)過(guò)對(duì)兩份數(shù)據(jù)的join、mapToPair、flatMapToPair、reduceByKey、mapValues等數(shù)據(jù)集的轉(zhuǎn)化操作后，最終以saveAsHadoopFile激活操作將得到的結(jié)果數(shù)據(jù)集存入到HDFS中去。其整個(gè)過(guò)程都以內(nèi)存計(jì)算為主，除了開(kāi)始讀入數(shù)據(jù)與最終寫出數(shù)據(jù)，整個(gè)計(jì)算過(guò)程基本不會(huì)與磁盤發(fā)生I/O行為，計(jì)算效率非常高。

在創(chuàng)建RDD(彈性數(shù)據(jù)集)之后，Spark會(huì)盡可能地將任務(wù)并行化、管道化，按照組織的數(shù)據(jù)來(lái)劃分階段(Stage)。PageRank算法的過(guò)程有固定Stage和變化Stage，其中準(zhǔn)備鄰接矩陣、準(zhǔn)備初始權(quán)值以及最終存入HDFS三個(gè)邏輯任務(wù)為固定不變的Stage，隨著數(shù)據(jù)量的擴(kuò)大其處理的并行任務(wù)會(huì)增加但Stage并不增加。而只有迭代次數(shù)的不斷增加，才會(huì)帶來(lái)Stage數(shù)目的不斷增加，增加的次數(shù)要根據(jù)迭代部分的復(fù)雜程度來(lái)確定。在程序劃分好階段后，會(huì)產(chǎn)生DAG(有向無(wú)環(huán)圖)作為邏輯執(zhí)行計(jì)劃。在執(zhí)行的過(guò)程中，每個(gè)階段又可能被分為多個(gè)任務(wù)接受調(diào)度。詳細(xì)的RDD轉(zhuǎn)化過(guò)程如圖5所示。

圖5 Spark框架下的PageRank計(jì)算RDD轉(zhuǎn)化過(guò)程

4) 動(dòng)態(tài)選擇并行計(jì)算框架

在性能對(duì)比上，Spark的性能遠(yuǎn)遠(yuǎn)好于MapReduce，但這是以消耗巨大內(nèi)存為前提的。彈性數(shù)據(jù)集意味著如果內(nèi)存不足，那么有部分?jǐn)?shù)據(jù)會(huì)被刷寫到磁盤之上，在這種情況下，Spark的速度與穩(wěn)定性均會(huì)降低，尤其是速度上并不比MapReduce快很多。因此，將挖掘中的全部任務(wù)都由MapReduce替換為Spark是不明智的，它會(huì)消耗大量資源，并引起資源調(diào)度的不穩(wěn)定。只有針對(duì)核心的、耗時(shí)較大的迭代任務(wù)，采用Spark才是高效的。結(jié)合集群使用情況來(lái)看，當(dāng)Spark迭代任務(wù)與HadoopMapReduce任務(wù)同時(shí)運(yùn)行在集群之中時(shí)，集群的負(fù)荷增大。通過(guò)監(jiān)控WebUI可以得知，非高峰期整體內(nèi)存使用率在92%至96%之間，處于正常運(yùn)行狀態(tài)，但高峰期時(shí)，使用Spark進(jìn)行迭代計(jì)算將因?yàn)榧簝?nèi)存不足節(jié)點(diǎn)數(shù)增加而導(dǎo)致部分任務(wù)被掛起等待，集群利用率下降。

由此，確定了只有迭代計(jì)算部分的任務(wù)采用Spark進(jìn)行計(jì)算。且計(jì)算時(shí)采用動(dòng)態(tài)選擇機(jī)制：設(shè)置Spark作為默認(rèn)迭代計(jì)算框架，當(dāng)啟動(dòng)Spark迭代任務(wù)時(shí)，若集群整體內(nèi)存充足，任務(wù)順利啟動(dòng)進(jìn)行計(jì)算；若內(nèi)存空閑量足夠啟動(dòng)的節(jié)點(diǎn)數(shù)不足，導(dǎo)致Spark任務(wù)無(wú)法啟動(dòng)，返回錯(cuò)誤代碼，腳本切換至HadoopMapReduce框架進(jìn)行計(jì)算，整體切換流程如圖6所示。

圖6 動(dòng)態(tài)切換計(jì)算框架流程圖

本文算法的執(zhí)行涉及到超大規(guī)模數(shù)據(jù)集(8 100萬(wàn)條接近4 TB的初始數(shù)據(jù))，因此，在分析采用何種大規(guī)模分布式計(jì)算框架時(shí)，就會(huì)涉及到性能、數(shù)據(jù)量和穩(wěn)定性上的考慮。Spark將常用數(shù)據(jù)貯存于內(nèi)存之中的機(jī)制，大大改善了MapReduce框架的運(yùn)算性能，減少了大量的I/O開(kāi)銷，但同時(shí)，這種內(nèi)存計(jì)算框架也存在著大量消耗內(nèi)存、調(diào)度不穩(wěn)定易崩潰的缺點(diǎn)。本文將兩種框架結(jié)合、根據(jù)集群當(dāng)前使用情況進(jìn)行動(dòng)態(tài)選擇，以內(nèi)存節(jié)點(diǎn)是否充足、Spark任務(wù)是否能正常啟動(dòng)作為切換的條件。當(dāng)內(nèi)存充足，集群壓力正常的情況下，選擇Spark可以大大提升運(yùn)行的效率；而在內(nèi)存不足，集群壓力較大的情況下，選擇MapRedcue則更為穩(wěn)定，其穩(wěn)定性上的優(yōu)勢(shì)完全彌補(bǔ)了速度上的不足，在多人共用的集群環(huán)境下尤為明顯。

4.2 微博用戶影響力計(jì)算實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)運(yùn)行與測(cè)試均在相同的集群環(huán)境之下完成，具體情況如下：

(1) 集群節(jié)點(diǎn)全部部署Hadoop CDH4(Cloudera版本，對(duì)應(yīng)Hadoop2.0)，并以Spark on Hadoop方式部署Spark-0.9.4版本。

(2) 集群規(guī)模：600臺(tái)節(jié)點(diǎn)，共計(jì)28 TB總內(nèi)存，CPU總核心數(shù)約1.5萬(wàn)個(gè)，磁盤約1 800 TB。

挖掘任務(wù)在集群各節(jié)點(diǎn)上運(yùn)行情況如圖7所示。

圖7 平臺(tái)基本運(yùn)行情況示意

根據(jù)上一節(jié)中不同并行計(jì)算框架下的設(shè)計(jì)，編寫了MapRedce程序和Spark程序并運(yùn)行在集群上，典型的用戶得分權(quán)重收斂情況如圖8所示，大部分用戶在迭代20次時(shí)歸于收斂，而迭代達(dá)到40次時(shí)，全部數(shù)據(jù)歸于收斂。

圖8 隨迭代次數(shù)增加用戶權(quán)值收斂情況

上述集群環(huán)境下，進(jìn)行了多次用戶影響力計(jì)算實(shí)驗(yàn)，總體計(jì)算時(shí)間保持在1個(gè)小時(shí)20分鐘之內(nèi)，整體運(yùn)行時(shí)長(zhǎng)如表3所示。

表3 挖掘運(yùn)行性能統(tǒng)計(jì) min

經(jīng)過(guò)對(duì)數(shù)據(jù)的采集和預(yù)處理，并利用動(dòng)態(tài)選擇的分布式框架對(duì)近3個(gè)月的來(lái)自于新浪微博的真實(shí)線上用戶數(shù)據(jù)進(jìn)行微博用戶影響力計(jì)算，得出了最終的用戶影響力。在計(jì)算結(jié)果覆蓋的若干領(lǐng)域中，以熱門領(lǐng)域“健康醫(yī)療”為例分析與說(shuō)明挖掘?qū)ο蟮哪芰敵觥１?為采用本算法和計(jì)算框架后得出的“健康醫(yī)療”領(lǐng)域下前8名用戶的得分及排名情況，通過(guò)將此結(jié)果與微博影響力排行榜對(duì)應(yīng)醫(yī)療領(lǐng)域下的榜單進(jìn)行對(duì)比發(fā)現(xiàn)，其中8人中有6人上榜，且排名順序一致。這里，微博影響力排行榜來(lái)源于微風(fēng)云網(wǎng)站，這個(gè)第三方公司服務(wù)與新浪微博、百度、Discovery等多家公司，其數(shù)據(jù)具有一定的權(quán)威性[13]。

表4 健康醫(yī)療標(biāo)簽下排名前8的用戶情況統(tǒng)計(jì)

經(jīng)過(guò)對(duì)實(shí)驗(yàn)結(jié)果的分析，可以得出，若某一時(shí)間段內(nèi)，用戶的互動(dòng)量上升，則該用戶的權(quán)重值會(huì)由于PageRank權(quán)重的上升而增加。這一改進(jìn)的計(jì)算策略有效地改善了傳統(tǒng)PageRank算法挖掘能力用戶的陳舊性缺點(diǎn)，而引入時(shí)間區(qū)間與領(lǐng)域區(qū)分后，挖掘排名的動(dòng)態(tài)性和準(zhǔn)確度均得到了提高。

根據(jù)挖掘的結(jié)果，本文經(jīng)過(guò)展示系統(tǒng)將各領(lǐng)域下的高影響力用戶(高權(quán)重值)進(jìn)行了分類與整理，并設(shè)定了條件進(jìn)行篩選，如圖9所示。本文的用戶挖掘覆蓋了大多數(shù)社會(huì)生活領(lǐng)域，挖掘的結(jié)果具有較高的準(zhǔn)確性和可用性，可以支持廣告推薦與群組推薦。

為了進(jìn)一步驗(yàn)證算法的性能，我們比較了本文的改進(jìn)算法與文獻(xiàn)[3]及文獻(xiàn)[5]中改進(jìn)的PageRank算法對(duì)于相應(yīng)領(lǐng)域下的新浪微博用戶的挖掘結(jié)果，如表5所示。通過(guò)結(jié)果可以看出本文挖掘的健康醫(yī)療領(lǐng)域下的用戶與文獻(xiàn)[3]、文獻(xiàn)[5]相比，排名趨勢(shì)基本一致，但從數(shù)據(jù)規(guī)模上說(shuō)，文獻(xiàn)[3]與文獻(xiàn)[5]通過(guò)用戶活躍度和關(guān)注度對(duì)數(shù)據(jù)集進(jìn)行了篩選，限制了最終參與挖掘的數(shù)據(jù)的廣度，那么一次可挖掘的主題較為有限，而本文算法直接對(duì)于所有用戶的數(shù)據(jù)進(jìn)行挖掘，規(guī)模更大，挖掘出的主題覆蓋度更高。這是由于本文算法的研究重點(diǎn)在于覆蓋各個(gè)領(lǐng)域下的用戶，并采用并行架構(gòu)提升結(jié)果的實(shí)時(shí)性和動(dòng)態(tài)性。而文獻(xiàn)[3]的重點(diǎn)在于從話題和博文的影響力進(jìn)行PageRank計(jì)算，文獻(xiàn)[5]則是從活躍度和關(guān)注度進(jìn)行計(jì)算，它們挖掘的結(jié)果是全局性的影響力排名及分析，沒(méi)有討論數(shù)據(jù)規(guī)模和覆蓋度相關(guān)的問(wèn)題。本文挖掘使用的數(shù)據(jù)規(guī)模在TB級(jí)別，討論的是大規(guī)模集群挖掘下的相關(guān)問(wèn)題，因此挖掘的方法具有更高的應(yīng)用性。

5 結(jié) 語(yǔ)

根據(jù)對(duì)用戶特征和行為特征的分析，本文針對(duì)PageRank算法在微博用戶影響力的計(jì)算上做了改進(jìn)，引入了時(shí)間區(qū)間和領(lǐng)域區(qū)間，給出了用戶影響力的量化計(jì)算公式?；赑ageRank改進(jìn)的用戶影響力算法，分別在MapReduce和Spark計(jì)算框架下進(jìn)行了微博用戶影響力迭代計(jì)算。實(shí)驗(yàn)結(jié)果表明，基于PageRank改進(jìn)的用戶影響力計(jì)算方法具有較好的準(zhǔn)確性，在采用Spark并行化計(jì)算框架進(jìn)行迭代計(jì)算時(shí)性能較高，比較適合大規(guī)模數(shù)據(jù)集合的挖掘場(chǎng)景。

[1] 吳根平.我國(guó)政府微博發(fā)展現(xiàn)狀及對(duì)策[J].信息化建設(shè),2011(10):23-27.

[2] Weng J,Lim E,Jiang J,et al.Twitterrank:finding topic-sensitive influential twitters[C]//WSDM,2010.

[3] 吳少華,馬曉娟,胡勇.基于改進(jìn)PageRank算法的微博用戶影響力評(píng)估[J].四川大學(xué)學(xué)報(bào)(自然科學(xué)版),2015(5):1040-1044.

[4] 陳少欽.基于PageRank的社交網(wǎng)絡(luò)用戶實(shí)時(shí)影響力研究[D].上海交通大學(xué),2013.

[5] 歐衛(wèi),歐繽憶,謝贊福,等.一種基于PageRank的微博用戶影響度評(píng)估算法[J].計(jì)算機(jī)與現(xiàn)代化,2013(12):34-37,40.

[6] 楊尊琦,張倩楠.基于k-means算法的微博用戶推薦功能研究[J].情報(bào)雜志,2013(8):142-144,131.

[7] 原福永,馮靜,符茜茜.微博用戶的影響力指數(shù)模型[J].現(xiàn)代圖書情報(bào)技術(shù),2012(6):60-64.

[8] 邢千里,劉列,劉奕群,等.微博中用戶標(biāo)簽的研究[J].軟件學(xué)報(bào),2015(7):1626-1637.

[9] Page L.The PageRank Citation Ranking:Bringing Order to the Web[C]//Stanford InfoLab,1999:1-14.

[10] 夏雨禾.微博互動(dòng)的結(jié)構(gòu)與機(jī)制—基于對(duì)新浪微博的實(shí)證研究[J].新聞與傳播研究,2010(4):60-69.

[11] 周奇峰.基于用戶興趣的PageRank算法改進(jìn)策略[J].網(wǎng)絡(luò)安全技術(shù)與應(yīng)用,2014(6):52-53.

[12] Pedroche F,Moreno F,González A,et al.Leadership groups on Social Network Sites based on Personalized PageRank[J].Mathematical & Computer Modelling,2013,57(s7/8):1891-1896.

[13] 微博影響力評(píng)估平臺(tái).微博影響力排行榜[EB/OL].2015.http://www.tfengyun.com/rankings.php.

IMPROVEMENT AND APPLICATION OF PAGERANK ALGORITHM FOR MICRO-BLOG

Yuan Ye1,2Li chen1Tian Lihua1*

1(SoftwareEngineeringSchool,Xi’anJiaotongUniversity,Xi’an710049,Shaanxi,China)2(SinaCorporation,Beijing100000,China)

It has been one of the urgent problems of micro-blog mining to identify experts with ability to produce high-quality content and high influence under various fields in social network with massive data, and make targeted advertising recommendation and decision support. In this paper, on the basis of user features and behavior features, the rules of selecting article in micro-blog and interaction calculation formula are determined, and the obsolescence of data and irrelevance of theme have been improved by PageRank algorithm. Finally, the algorithm is implemented respectively in the parallel computing framework of MapReduce and Spark. Experimental results show that the proposed method has high accuracy and great performance under Spark, especially under large-scale dataset scene.

Micro-blog User Influence PageRank Spark Big data

2016-01-25。國(guó)家自然科學(xué)

61403302)。原野，碩士生，主研領(lǐng)域：數(shù)據(jù)挖掘。李晨，講師。田麗華，高級(jí)工程師。

TP301.6

A

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