云計(jì)算環(huán)境下影響力優(yōu)化研究與實(shí)現(xiàn)

孫 紅,左 騰

1(上海理工大學(xué),上海 200093) 2(上?，F(xiàn)代光學(xué)系統(tǒng)重點(diǎn)實(shí)驗(yàn)室,上海 200093)

1 引 言

隨著互聯(lián)網(wǎng)的發(fā)展,社交作為互聯(lián)網(wǎng)應(yīng)用發(fā)展的必備要素,不再局限于信息傳遞,而是與溝通交流、商務(wù)交易類應(yīng)用融合,借助其他應(yīng)用的用戶基礎(chǔ),形成更強(qiáng)大的關(guān)系鏈,從而實(shí)現(xiàn)對信息的廣泛、快速傳播.作為社交網(wǎng)絡(luò)的一種重要形式,微博(Weibo)有著即時(shí)發(fā)布、互動性強(qiáng)、簡便易用等特點(diǎn),微博迅速發(fā)展為最為主流的社交平臺.據(jù)CNNIC發(fā)布的第39次《中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告》數(shù)據(jù)顯示[1],截至 2016 年 12月,微博的使用率為37.1%,與2016 年6月相比略有上漲.

微博作為一種重要的社會平臺,在社會、政治、生活等各個(gè)方面都成為一種重要的社會輿論載體.每一個(gè)微博用戶可以通過微博獲取實(shí)時(shí)的新聞資訊,了解朋友及其他名人,社會媒體等等其它一些我們關(guān)心的實(shí)時(shí)動態(tài).如果一則消息在微博里面迅速傳播開,有很多人轉(zhuǎn)播,評論,點(diǎn)贊,那么這則微博相關(guān)的話題就會上微博頭條,從而會有更多的人知道這個(gè)話題,從而影響到社會輿論情況.如果某個(gè)微博用戶有眾多的粉絲和關(guān)注度,那么他發(fā)布的微博消息就會得到廣泛的關(guān)注,那么該用戶就可以影響信息的傳播.所以,現(xiàn)在就會有很多人通過購買水軍,來提高自己微博信息傳播的影響力,然而這些所謂的粉絲是不能夠當(dāng)作正常微博用戶來看的,他們會照成謠言和不良信息的的散布,給社會帶來不好的影響和輿論恐慌.

本文主要利用海量的新浪微博用戶數(shù)量來進(jìn)行相關(guān)研究,面對如此龐大的數(shù)據(jù)量,就必須利用并行化的方式來處理這些數(shù)據(jù).數(shù)據(jù)并行處理(Data Parallel Processing)是指計(jì)算機(jī)系統(tǒng)能夠同時(shí)執(zhí)行兩個(gè)或者更多個(gè)處理機(jī)的一種計(jì)算方法.并行處理的主要目的是節(jié)省大型和復(fù)雜問題的解決時(shí)間[2].為使用并行處理,首先需要對程序進(jìn)行并行化處理,也就是說將工作各個(gè)部分分配到不同處理機(jī)中[3].當(dāng)前比較常用的大數(shù)據(jù)分布式計(jì)算應(yīng)用最具有代表性的有:MapReduce,Spark和GraphX.由于MapReduce模型簡單、易于理解、易于使用,極大地簡化了程序員的開發(fā)工作.而且大量數(shù)據(jù)處理問題,包括很多機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘算法,都可以使用MapReduce實(shí)現(xiàn).為了提高計(jì)算效率,同時(shí)考慮到企業(yè)級大量數(shù)據(jù)中心正在采用云計(jì)算環(huán)境,云計(jì)算越來越普遍,而且開源云計(jì)算平臺巳經(jīng)被廣泛應(yīng)用,因此我們采用基于開源云計(jì)算平臺Hadoop的MapReduce架構(gòu)進(jìn)行并行處理,以縮計(jì)算時(shí)間,提高計(jì)算的效率和實(shí)時(shí)性[4].

2 研究背景

2.1 相關(guān)研究

微博最早起源于國外的,所以相關(guān)的研究算法也起源于國外學(xué)者的研究.因?yàn)門witter作為微博的鼻祖,國外對微博的研究主要集中在對Twitter 的研究.目前有關(guān)微博影響力分析算法主要參考Google 的PageRank[5]算法及其改進(jìn)后的算法[6,7]和HITS[8]算法及其改進(jìn)后算法[9,10].PageRank算法模型是為了實(shí)現(xiàn)網(wǎng)頁排名,該算法也是Google使用的搜索結(jié)果排名中的重要組成部分.事實(shí)上,PageRank模型本質(zhì)上是用于有向圖的節(jié)點(diǎn)級的計(jì)算技術(shù),因此應(yīng)用于用戶對微博的影響是自然的.借鑒PageRank算法的思想,在文獻(xiàn)[11]中提出了TwitterRank算法,該算法主要是衡量一個(gè)用戶在某一話題內(nèi)的影響力,主要思想是給定一個(gè)話題,用戶的影響力定義為他的所有粉絲的影響力之和.但是該算法僅考慮擁有相似話題的用戶間相互的影響力,不具有一般性.文獻(xiàn)[12]中,對Twitter的傳播特性進(jìn)行了分析,使用粉絲數(shù)量和微博轉(zhuǎn)發(fā)數(shù)量比對研究用戶在話題傳播過程中的影響,結(jié)果發(fā)現(xiàn)擁有眾多粉絲數(shù)量的微博用戶所發(fā)的微博不一定會得到很多的轉(zhuǎn)發(fā)或者評論,他們在微博中的轉(zhuǎn)發(fā)和引并不起絕對的影響,這表明用戶的粉絲數(shù)量和用戶的影響力并沒有直接關(guān)系,但是那些有影響力的用戶能夠在各種話題中產(chǎn)生顯著的影響.在文獻(xiàn)[13]里面,Xun Chen等人提出來Personal Rank算法,該算法也可以用于計(jì)算微博用戶的影響力,但是在計(jì)算時(shí)還是需要依賴PageRank算法.在文獻(xiàn)[14]里面,Jun Zhou等人使用回歸模型來預(yù)測每個(gè)用戶的影響力分?jǐn)?shù)分析個(gè)人財(cái)產(chǎn)及其內(nèi)容消息,而且他們的研究揭示了個(gè)體大多數(shù)用戶的影響隨時(shí)間而變化.在文獻(xiàn)[15]里,吳渝等通過對不同時(shí)間段的數(shù)據(jù)進(jìn)行分析提取出意見領(lǐng)袖.在文獻(xiàn)[16]里面,Guo-Jun Mao等人對用戶的活躍度進(jìn)行了分析,但是該文章里面只對用戶的評論數(shù)進(jìn)行了分析,并沒有深入分析也沒有剔除“僵尸粉”的干擾.

2.2 計(jì)算框架

本文主要用到的是基于Hadoop的MapReduce計(jì)算框架,該框架主要是通過簡單有力的接口來實(shí)現(xiàn)自動化的并行化和大規(guī)模分布式計(jì)算,結(jié)合這個(gè)接口的實(shí)現(xiàn)在大量普通的PC機(jī)上實(shí)現(xiàn)高性能計(jì)算[17].在Hadoop里面,數(shù)據(jù)存儲的核心是HDFS文件存儲系統(tǒng),HDFS使用Block(存儲快)對文件的存儲進(jìn)行操作.在Hadoop中,數(shù)據(jù)處理核心為MapReduce程序設(shè)計(jì)模型.MapReduce把數(shù)據(jù)處理分為兩個(gè)主要的階段,即Map階段和Reduce階段.MapReduce作業(yè)的輸入是一系列存儲在Hadoop分布式文件系統(tǒng)HDFS上的文件,在Map階段之前,首先要對數(shù)據(jù)進(jìn)行分塊處理成split,之后將數(shù)據(jù)信息交給Map任務(wù)去進(jìn)行讀取,然后進(jìn)行分類寫入.一個(gè)Map任務(wù)的執(zhí)行過程和數(shù)據(jù)輸入輸出的形式如下所示:

Map:data→→list

Map階段主要是對輸入進(jìn)行整合,通過用戶自己定義Map函數(shù),定義輸入格式獲取文件信息和類型,并且確定讀取方式,最終將讀取的Split內(nèi)容,解析成以鍵值對的形式保存.然后自定義的算法,將符合的數(shù)據(jù)分類,根據(jù)相同的key值生成若干條列表,該表存儲著具有相同key值的value組成的鍵值對(list).

一個(gè)Reduce任務(wù)的執(zhí)行過程和數(shù)據(jù)輸入輸出的形式如下所示:

Reduce:>→list

Reduce是用來對結(jié)果進(jìn)行后續(xù)處理.系統(tǒng)框架自動對Map輸出結(jié)果進(jìn)行Shuffle和Sort處理,根據(jù)相同的鍵將其對應(yīng)的值組合成一個(gè)集合的形式輸入給Reduce函數(shù).

圖1 MapReduce流程圖Fig.1 MapReduce flow chart

通過接收到的鍵值對數(shù)據(jù)對Map獲取內(nèi)容的值進(jìn)行二次整理和歸并排序,最后以形式將計(jì)算結(jié)果輸出到文件存儲系統(tǒng)HDFS.MapReduce的處理過程如圖1所示.

3 MR-UIRank微博用戶影響力模型

3.1 PageRank模型

最初的PageRank模型,是Google在搜索引擎結(jié)果中對網(wǎng)站排名的核心算法.PageRank通過計(jì)算頁面鏈接的數(shù)量和質(zhì)量來確定網(wǎng)站的重要性的粗略估計(jì),PageRank 是基于從許多優(yōu)質(zhì)的網(wǎng)頁鏈接過來的網(wǎng)頁,必定還是優(yōu)質(zhì)網(wǎng)頁的回歸關(guān)系,來判定所有網(wǎng)頁的重要性.

為了方便研究,現(xiàn)給出與本文相關(guān)的公式定義.

定義1.(PageRank算法)對所有研究的網(wǎng)頁給定一個(gè)有向圖G=,它是由頂點(diǎn)的集合 V和邊的集合 A組成.網(wǎng)頁P(yáng)i∈(G)的排名可以用下面的公式來計(jì)算.

(1)

其中Mpi是所有對Pi網(wǎng)頁有出鏈的網(wǎng)頁集合,L(Pi)是網(wǎng)頁P(yáng)i的出鏈數(shù)目,N是研究網(wǎng)頁總數(shù),α代表的是阻尼因子,取值范圍是0-1.根據(jù)上面的公式,我們可以計(jì)算每個(gè)網(wǎng)頁的PR(下文的所有的PR代表PageRank)值,在不斷迭代趨于平穩(wěn)的時(shí)候,即為最終結(jié)果.圖2顯示了運(yùn)用PageRank算法時(shí),網(wǎng)頁P(yáng)i與網(wǎng)頁P(yáng)j之間的關(guān)系.

圖2 網(wǎng)頁P(yáng)i和網(wǎng)頁P(yáng)j的關(guān)系Fig.2 Page pi and page pj relationship

在表現(xiàn)網(wǎng)頁之間鏈接關(guān)系時(shí),Google使用了矩陣,即下面的定義2.

定義2.(Google初始矩陣)我們可以用一個(gè)矩陣來表示這張圖的出鏈入鏈關(guān)系,初始矩陣S=(si,j),其中si,j代表網(wǎng)頁j跳轉(zhuǎn)到頁面i的概率.也就是說,對于i,j∈G,與有向圖G相關(guān)的Google矩陣可以被設(shè)置如下:

(2)

其中L(j)是網(wǎng)頁j的出站鏈接總數(shù).

現(xiàn)在給出N為4的一個(gè)例子(共有A、B、C、D、E、F、G七張網(wǎng)頁)幫助說明這個(gè)矩陣.對于圖3所示的有向圖,其Google初始矩陣可以通過公式(2)獲得,圖4給出了Google初始矩陣S計(jì)算結(jié)果.

圖3 頁面有向圖Fig.3 A directed graph for page

圖4 Google 初始矩陣Fig.4 Google initial matrix

定義3.(Google矩陣)得到初始矩陣后,我們就可以計(jì)算PR值了,當(dāng)只有α概率的用戶會點(diǎn)擊網(wǎng)頁鏈接,剩下(1-α)概率的用戶會跳到無關(guān)的頁面上去,而訪問的頁面恰好是這7個(gè)頁面中A的概率只有(1-α)/7(α是阻尼系數(shù),Google在計(jì)算網(wǎng)頁排名的時(shí)候取α等于0.85,所以本文在這里也取0.85),所以真正的Google矩陣由公式(3)計(jì)算.

(3)

定義4.(PR值計(jì)算)在有向圖G及其Google矩陣GM里面,其中n是G中的節(jié)點(diǎn)數(shù)然后.于是得到Pn=GM×Pn-1,可以通過以下公式(3)逐級地迭代更新秩向量,直到得到Pn=Pn-1時(shí),才算迭代完成,這時(shí)的Pn就是PR的值.于是計(jì)算PR值的過程就變成了一個(gè) Markov 過程.

Pn=GM×Pn-1

(4)

3.2 MR-UIRank模型

傳統(tǒng)的PageRank模型可以幫助評估微博用戶的影響力,但其有效性并不被大多數(shù)人認(rèn)可.傳統(tǒng)的PageRank模型僅考慮鏈接關(guān)系,即用戶與用戶之間的關(guān)注與被關(guān)注關(guān)系.把微博用戶的粉絲看作網(wǎng)站的入站鏈接,微博用戶關(guān)注的人看作網(wǎng)站的出站鏈接,這樣就可以把PageRank模型應(yīng)用到計(jì)算微博用戶影響力里面來[18].但是,在計(jì)算影響力的時(shí)候,那些擁有眾多“僵死粉”的微博用戶的影響力就會被虛假提高,從而計(jì)算出來的影響力并不準(zhǔn)確,其實(shí)那些擁有眾多“水軍”的用戶影響力并沒有那么高.所以,首先要剔除微博用戶的僵尸粉,在進(jìn)行粉絲篩選的時(shí)候,需要選取高質(zhì)量的粉絲.需要選取長期關(guān)注博主的粉絲,而不是近期突然增加的粉絲.

定義5.(粉絲選取)認(rèn)定選取的粉絲集合為F,其中選取的粉絲是關(guān)注博主三個(gè)月以上的用戶.而且這些用戶在三個(gè)禮拜以內(nèi)有和別人互動,且評論或者轉(zhuǎn)發(fā)過該博主的微博等這樣的交互行為.

F(i)={j|(j,i)∈A∪FT>3m∪AT>3w}

(5)

F(i)代表用戶i的粉絲集合,j代表其中一個(gè)粉絲,FT代表的是粉絲j關(guān)注博主的時(shí)間,大于三個(gè)月,AT代表粉絲j活躍的天數(shù)是三周.這一步只是對粉絲進(jìn)行了篩選,剔除了一些僵死粉的干擾.選取完粉絲后就需要計(jì)算用戶的活躍度了,下面的定義6代表粉絲活躍度計(jì)算公式.

定義6.(用戶活躍度計(jì)算)用戶的活躍度包括很多條件,如用戶發(fā)布的微博數(shù),轉(zhuǎn)發(fā)微博數(shù),點(diǎn)贊微博數(shù),評論微博數(shù),@別人的微博數(shù),收藏微博數(shù)量以及在微博中的活躍的天數(shù).本文設(shè)定的時(shí)間段是最近三個(gè)月內(nèi)微博用戶的活動情況,綜合這些條件,下面給定微博用戶i其活躍度的計(jì)算公式:

(6)

其中nbi是微博用戶i三個(gè)月內(nèi)發(fā)布的微博數(shù)量,NB是整個(gè)微博里面所有微博用戶三個(gè)月內(nèi)發(fā)布的微博數(shù)量;nri是微博用戶i三個(gè)月內(nèi)轉(zhuǎn)發(fā)的微博數(shù)量,NRi是三個(gè)月內(nèi)整個(gè)微博里面所有微博用戶轉(zhuǎn)發(fā)微博數(shù)量;nci是微博用戶i三個(gè)月內(nèi)評論微博數(shù)量,NCi是三個(gè)月內(nèi)整個(gè)微博里面所有微博用戶評論微博數(shù)量;nli是微博用戶i三個(gè)月內(nèi)點(diǎn)贊微博數(shù)量,NLi是三個(gè)月內(nèi)整個(gè)微博里面所有微博用戶點(diǎn)贊微博數(shù)量;nai是微博用戶i三個(gè)月內(nèi)“@”其他用戶微博數(shù)量,NAi是三個(gè)月內(nèi)整個(gè)微博里面所有微博用戶“@”其他用戶微博數(shù)量;di是微博用戶i三個(gè)月內(nèi)的活躍天數(shù),Di是三個(gè)月內(nèi)整個(gè)微博里面所有微博用戶平均活躍天數(shù).

在研究了用戶的活躍度之后,但還需要對用戶的微博質(zhì)量進(jìn)行研究.微博的質(zhì)量體現(xiàn)在微博的內(nèi)容是否健康,真實(shí),是否對我們整個(gè)社會有一定的影響.例如那些在微博里面散布廣告,發(fā)布虛假消息的微博用戶,那么他們的這些行為對于整個(gè)微博環(huán)境,對于整個(gè)社會帶來了負(fù)面的影響,應(yīng)當(dāng)予以否定.所以,在選取微博內(nèi)容時(shí),就需要剔除那些質(zhì)量較差的微博,選取能夠?qū)τ谏鐣a(chǎn)生正面影響的微博.因此,在篩選微博數(shù)據(jù)的時(shí)候,本文就選取了和社會話題相關(guān)的微博作為研究對象.同時(shí)對用戶微博被評論的數(shù)量,被轉(zhuǎn)發(fā)的數(shù)量,被點(diǎn)贊的數(shù)量,和被收藏?cái)?shù)量進(jìn)行研究.如果微博被眾多人評論,轉(zhuǎn)發(fā),點(diǎn)贊和收藏自然說明該用戶的影響力要高.根據(jù)上面提出的思想,下面的定義7給出了在用戶微博質(zhì)量的簡單評估計(jì)算方法.

定義7.(用戶微博質(zhì)量計(jì)算)對由于用戶發(fā)布微博,有著不確定性,且微博的內(nèi)容和每天發(fā)生的事情有關(guān),所以,在選取微博內(nèi)容的時(shí)候,本文選取了最近三個(gè)月的微博內(nèi)容作為實(shí)驗(yàn)的對象.于微博用戶i,選取的研究話題為社會話題為SI(Social Issues),用戶微博質(zhì)量計(jì)算公式如下:

(7)

(8)

(9)

(10)

(11)

Quality(i)=QSI(i)+QR(i)+QC(i)+QL(i)+QF(i)

(12)

其中nsii是用戶i發(fā)布與主題SI相關(guān)的微博數(shù)量,Ni是用戶i在微博中發(fā)布的所有微博數(shù)量;rsii是用戶i發(fā)布與主題SI相關(guān)的微博被轉(zhuǎn)發(fā)的數(shù)量,Ri是在微博里面所有被轉(zhuǎn)發(fā)的微博數(shù)量;csii是用戶i發(fā)布與主題SI相關(guān)的微博被評論的數(shù)量,Ci是在微博里面所有被評論的微博數(shù)量;lsii是用戶i發(fā)布與主題SI相關(guān)的微博被點(diǎn)贊的數(shù)量,Li是在微博里面所有被點(diǎn)贊的微博數(shù)量.fsii是用戶i發(fā)布與主題SI相關(guān)的微博被收藏的數(shù)量,Fi是在微博里面所有被收藏的微博數(shù)量.研究的時(shí)間段是最近的三個(gè)月.

此外,還有另一個(gè)因素也可以在很大程度上反映用戶的影響力,就是微博用戶的可信度.比如微博里面的那些大V,一些經(jīng)過官方認(rèn)證博主,那么他們的發(fā)言就會很有影響力,人們愿意相信這些人所發(fā)布的微博.目前在新浪微博平臺上已經(jīng)提供認(rèn)證機(jī)制,共有四種認(rèn)證方式.第一種是興趣認(rèn)證,第二種是自媒體認(rèn)證,第三種是身份認(rèn)證,最后一種是官方認(rèn)證.在此,本文利用微博上不同的認(rèn)證,給出不同的用戶信譽(yù)度.定義8給出了在微博上用戶可信度的簡單計(jì)算方法.

定義8.(微博用戶可信度)對于微博用戶i,其可信度可以計(jì)算公式如下:

(13)

在進(jìn)行運(yùn)算PageRank算法之前還需要修改微博用戶的權(quán)重,由定義9給出.

定義9.(微博用戶權(quán)重)對于微博用戶i,它的權(quán)重w(weiht)計(jì)算公式如下:

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

(14)

然后將用戶權(quán)重加入進(jìn)原始PageRank模型計(jì)算.

定義10.(加權(quán)Google矩陣)對于有向圖G=,令其加權(quán)的Google矩陣Z=(zi,j),其中zi,j計(jì)算如下:

(15)

公式(15)中的zi,j是公式(3)中的值gmi,j與用戶權(quán)重w(i)的乘積,所以加權(quán)的Google矩陣考慮的用戶的鏈接結(jié)構(gòu)包括用戶活躍度,用戶微博質(zhì)量和用戶可信度等因素.假設(shè)已經(jīng)獲得圖1中每個(gè)節(jié)點(diǎn)的評估參數(shù),如令w(A)=w1,w(B)= w2,w(C)= w3,w(D)=w4,w(E)=w5,w(F)=w6,w(G)=w7那么通過計(jì)算,就可以獲得加權(quán)后的的Google矩陣Z.

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)

在獲取新浪微博數(shù)據(jù)時(shí),首先要先注冊新浪微博賬號,然后利用該賬號在新浪微博開放平臺完成開發(fā)者的注冊,注冊身份為學(xué)生,然后在開放平臺上創(chuàng)建一個(gè)應(yīng)用,創(chuàng)建完應(yīng)用后,開發(fā)者會得到獲取兩個(gè)非常重要的參數(shù)App Key和Secret Key.在創(chuàng)建應(yīng)用過程中需要填寫一個(gè)授權(quán)回調(diào)頁.應(yīng)用創(chuàng)建完成后,就可以利用新浪官方API進(jìn)行開發(fā)了.首先進(jìn)入開放平臺,在文檔里面資源下載和API選項(xiàng),首先需要在資源下載下面下載相關(guān)的SDK,本文用到的是JAVA SDK.下載完了JAVA SDK后就需要導(dǎo)入到eclipse里面,然后是配置下載下來的JAVA SDK.主要改一個(gè)文件,src文件夾下面的config.properties,配置如下參數(shù).

1.client_ID:appkey 創(chuàng)建應(yīng)用獲取到的appkey (App Key)

2.client_SERCRET:app_secret 創(chuàng)建應(yīng)用獲取到的appsecret(Secret Key)

3.redirect_URI:回調(diào)地址 OAuth2的回調(diào)地址(就是在高級信息里面填寫的授權(quán)回調(diào)頁).

在配置好配置文件后就需要進(jìn)行Oath2.0認(rèn)證,這是在調(diào)用所有API之前都需要進(jìn)行的操作.

調(diào)用example下面weibo4j.examples.oauth2包里面的 OAuth4Code.java.如果這個(gè)步驟完成了就可以任意調(diào)用微博API了.然后再微博API選項(xiàng)下面查閱相關(guān)的API文檔,就可以在eclipse里面下載到需要用到的數(shù)據(jù).然后利用微博API獲取了64678個(gè)微博用戶,其中包含用戶的基本信息和用戶關(guān)系網(wǎng)絡(luò)和發(fā)布的微博信息等一些數(shù)據(jù),然后從64678個(gè)用戶里面選擇3958個(gè)微博用戶作為實(shí)驗(yàn)對象.雖然3958個(gè)用戶只是新浪微博用戶總數(shù)的一小部分,但這些用戶的關(guān)系是相對完整的,所以我們可以使用它們來測試我們的算法在本文中的有效性.

4.2 實(shí)驗(yàn)環(huán)境

本次實(shí)驗(yàn)采用4臺PC機(jī)搭建云計(jì)算Hadoop平臺,其中每臺機(jī)器的配置均為:Intel 酷睿i7 6700HQ 3.5GHz,內(nèi)存DDR4 2133MHz 16GB,硬盤2TB.在每臺PC機(jī)操作系統(tǒng)為64位Centos7 linux,而且配置安裝Hadoop 的版本為2.7.3、JDK為jdk-8u111-linux-x64版本以及其他環(huán)境配置.

搭建的云計(jì)算hadoop平臺集群設(shè)置信息如圖5所示.

圖5 Hadoop集群設(shè)置Fig.5 Hadoop cluster settings

4.3 實(shí)驗(yàn)結(jié)果

本文對實(shí)驗(yàn)結(jié)果進(jìn)行比較分析選取社會問題作為PageRank和MR-UIRank算法計(jì)算時(shí)的主題,分別對傳統(tǒng)的PageRank算法和本文提出的MR-UIRank算法計(jì)算出的用戶影響力進(jìn)行排序,列出PageRank算法和MR-UIRank算法影響力排名前10的用戶.計(jì)算結(jié)果如表1和表2所示.表中的微博數(shù)是用戶最近三個(gè)月所發(fā)布的微博數(shù)量.

表1 PageRank算法計(jì)算結(jié)果
Table 1 Calculation by Pagerank

排名微博用戶名粉絲數(shù)微博數(shù)認(rèn)證1新手指南172567565125官方2微博管理員15672263666官方3謝娜88124987159身份4陳坤8075713074身份5姚晨80321437172身份6趙薇7898828640身份7何炅82099269122身份8angelababy7802469630身份9人民日報(bào)509764113060官方10央視新聞485761653335官方

通過對表1的分析,可看傳統(tǒng)的PageRank算法在計(jì)算時(shí)的最注重的是粉絲數(shù)量,而忽略了用戶的自身行為活動,而且他們近期發(fā)布的微博數(shù)量也比較少.我們可以看出:排名靠前的都是影視大咖等這一些知名度較高的微博用戶,他們的歌迷,影迷,粉絲眾多從而導(dǎo)致他們的影響力很高.由此本文發(fā)現(xiàn)排名第一和第二微博用戶是新手指南和微博管理員,但是他們實(shí)際的影響力并沒有計(jì)算結(jié)果那么高.他們的排名之所以這么高是應(yīng)為他們擁有眾多粉絲,他們擁有粉絲數(shù)量是排名第三微博用戶(謝娜)的將近兩倍,因?yàn)樗麄儞碛羞@么多的粉絲數(shù)量,在傳統(tǒng)的PageRank算法計(jì)算影響力的時(shí)候就把他粉絲的影響力加權(quán)起來了,這樣影響力就比其他用戶的高了許多.擁有這么多粉絲數(shù)量的原因是在用戶最開始注冊微博的時(shí)候就系統(tǒng)就幫微博用戶就自動關(guān)注了他們,而且用戶也沒有去取消關(guān)注,還有就是當(dāng)微博用戶不去用他們的微博賬號后,之前的微博賬號不能注銷,所以這樣在無形之中就產(chǎn)生了“僵尸用戶”,而且這些“僵尸用戶”也不會被系統(tǒng)清除,所以他們的粉絲才會這么多,但其活躍度相對而言不是很高.所以在目前微博里面就會有明星花錢去買粉絲,來提高自己的想象力,提高自己的知名度.在表1里面,我們還可以看到,人民日報(bào)和央視新聞也擠入了前十,雖然他們得粉絲數(shù)量和前面的微博用戶相差很大,但是發(fā)布的微博數(shù)量多.

表2 MR-UIRank算法計(jì)算結(jié)果
Table 2 Calculation byMR-UIRan

排名微博用戶名粉絲數(shù)微博數(shù)認(rèn)證1中國新聞網(wǎng)310891102803官方2人民日報(bào)509764113060官方3央視新聞485761653335官方4新浪新聞106879172855官方5人民網(wǎng)371373675422官方6法制晚報(bào)161633113929官方7環(huán)球時(shí)報(bào)71063714877官方8中國經(jīng)營報(bào)23364983075官方9成都商報(bào)274330323535官方10Vista看天下514359421898官方

分析表2可以發(fā)現(xiàn)MR-UIRank算法得到的結(jié)果和粉絲數(shù)量沒有呈現(xiàn)出正相關(guān)的關(guān)系.而微博用戶的自身的活動,他的微博數(shù)量,所發(fā)布微博的內(nèi)容等一些他的動態(tài)行為成了評論影響力強(qiáng)有力的標(biāo)準(zhǔn).排名靠前的是中國最具權(quán)威的報(bào)刊和新聞媒體人民日報(bào)和央視新聞,可以看到,他們的粉絲數(shù)量和微博數(shù)量都是非常高的.MR-UIRank算法的前10個(gè)用戶他們都是官方認(rèn)證用戶,而且發(fā)布了足夠的微博,粉絲.此外,為了評估文章的質(zhì)量,我們把主題放在社會問題上,所以MR-UIRank算法得到的前10個(gè)用戶,大多是官方認(rèn)證的新聞媒體,他們具有更大的權(quán)威性,而且這10個(gè)用戶里面沒有一個(gè)娛樂明星,這也說明這些娛樂明星發(fā)布的微博很少與社會話題有關(guān),通過查看他們的微博,他們發(fā)布的微博話題大多數(shù)都是他們的日常生活或者一些宣傳,因此在MR-UIRank算法里面他們都排不上名.PageRank算法在評估用戶影響力時(shí)沒有考慮到用戶自身的動態(tài)行為,而是依賴于粉絲數(shù)量,過于簡單片面,所以在一定程度上受到“僵尸粉的”干擾.

圖6 時(shí)間比較Fig.6 Time comparison

為了比較效率,本文用不同數(shù)量的用戶測試了傳統(tǒng)方式計(jì)算的時(shí)間和MR-UIRank算法執(zhí)行時(shí)間的變化與比較.本文分了七個(gè),分別包括1000,1500,2000,2500,3000,3500和4000個(gè)微博用戶數(shù)量.計(jì)算結(jié)果如圖6所示.

從圖6可以看出,MR-UIRank算法的執(zhí)行時(shí)間明顯低于在相同數(shù)據(jù)容量下執(zhí)行的傳統(tǒng)方式計(jì)算時(shí)間.這是因?yàn)榕c傳統(tǒng)計(jì)算方式算法相比,MR-UIRank算法利用了MapReduce計(jì)算框架,這樣就明顯提高了計(jì)算的效率,縮短了計(jì)算時(shí)間.而且,隨著計(jì)算數(shù)量的不斷增加,MR-UIRank算法的效率會明顯提高,優(yōu)勢會越來越大.所以在進(jìn)行大規(guī)模的計(jì)算時(shí),運(yùn)用MapReduce計(jì)算框架能夠明顯提高時(shí)效性,使得算法運(yùn)行得到優(yōu)化.

5 結(jié)束語

本文分析了微博社交網(wǎng)絡(luò)的用戶的關(guān)系網(wǎng)絡(luò)和自身的行為,結(jié)合傳統(tǒng)Pagerank算法,運(yùn)用云計(jì)算平臺進(jìn)行計(jì)算,結(jié)果表明本文的算充分法考慮用戶的實(shí)際活動行為以及用戶的粉絲,使得挖掘結(jié)果更客觀和準(zhǔn)確,可以獲得更加全面,真實(shí)的結(jié)果,更好的反應(yīng)微博用戶影響力.而且運(yùn)用云計(jì)算后的計(jì)算效率比傳統(tǒng)的計(jì)算更加高效,節(jié)省時(shí)間.

在下一步的研究中,將會研究算法的高效性和準(zhǔn)確性,在提高準(zhǔn)確度的情況下提升效率,縮短計(jì)算時(shí)間,以便于應(yīng)對更加規(guī)模龐大的數(shù)據(jù)量計(jì)算.

[1] The 39thstatistical report on Internet development in China[R].Beijing:China Internet Network Information Center,http://www.cnnic.net.cn/，2016.

[2] Fu Cheng-long.Study of parallel production technology of remote sensing product and its application[D].Zhengzhou: Henan University,2014.

[3] Sun H,Chen S P,Jin C,et al.Research and simulation of task scheduling algorithm in cloud computing[J].Telkomnika Indonesian Journal of Electrical Engineering,2013,11(11)：6664-6672.

[4] Xu Ya-bin,Li Zhuo,Dong Yuan.The quick spam filtering method based on social computing and machine learning[J].Systems Engineering-Theory & Practice,2014(S1):179-186.

[5] Page L,Brin S,Motwani R,et al.The pagerank citation ranking:bringing order to the web[R].Stanford InfoLab,1999.

[6] Lamberti F,Sanna A,Demartini C.A relation-based page rank algorithm for semantic web search engines[J].IEEE Transactions on Knowledge & Data Engineering,2009,21(1):123-136.

[7] Jing Y,Baluja S.Pagerank for product image search[C].International Conference on World Wide Web,ACM,2008:307-316.

[8] Kleinberg J M.Authoritative sources in a hyperlinked environment[C].Acm-Siam Symposium on Discrete Algorithms,Society for Industrial and Applied Mathematics,1998.

[9] Liu Y,Lin Y.Supervised HITS algorithm for medline citation ranking[C].IEEE International Conference on Bioinformatics and Bioengineering,Bibe 2007,Harvard Medical School,Boston,Ma,Usa,2007:1323-1327.

[10] Asano Y,Tezuka Y,Nishizeki T.Improvements of HITS algorithms for spam links[C].Joint,Asia-Pacific Web and,International Conference on Web-Age Information Management Conference on Advances in Data and Web Management,Springer-Verlag,2007:200-208.

[11] Jianshu Weng,Ee-Peng Lim,Jing Jiang,et al.TwitterRank:finding topic-sensitive influential twitterers[C].ACM International Conference on Web Search and Data Mining (WSDM),2010.

[12] Cha M,Haddadi H,Benevenuto F,et al.Measuring user influence in twitter:the million follower fallacy[C].International Conference on Weblogs and Social Media (ICWSM),2010.

[13] Chen Xu,Wang Peng-fei,Qin Zheng,et al.HLBPR:a hybrid local Bayesian personal ranking method[C].International Conference Companion on World Wide Web,International World Wide Web Conferences Steering Committee,2016:21-22.

[14] Zhou Jun,Zhang Yan,Wang Bing,et al.Predicting user influence in microblogs[C].Computer Communication and the Internet (ICCCI),2016 IEEE International Conference on IEEE,2016:292-295.

[15] Wu Yu,Ma Lu-lu,Lin Mao,et al.Discovery algorithm of opinion leaders based on user influence[J].Journal of Chinese Computer Systems,2015,36(3):561-565.

[16] Mao G J,Zhang J.A pagerank-based mining algorithm for user influnces on micro-bloges [C].Pacific Asia Conference on Information Systems(PACIS),2016.

[17] Pan Quan,Guo Ming,Lin Peng.An algorithm for the maximum clique based on MapReduce[J].Systems Engineering-Theory & Practice,2011,(S2):150-153.

[18] Xu Wen-tao,Liu Feng,Zhu Er-zhou.Research on novel ranking algorithm of microblog user′s influence based on MapReduce [J].Computer Science,2016,43(9):66-70.

附中文參考文獻(xiàn)：

[1] 第39次中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告[R].北京:中國互聯(lián)網(wǎng)絡(luò)信息中心,http://www.cnnic.net.cn/,2016.

[2] 付成龍.遙感產(chǎn)品并行生產(chǎn)技術(shù)的研究及其應(yīng)用[D].鄭州:河南大學(xué),2014.

[4] 徐雅斌,李 卓,董 源.基于社會計(jì)算和機(jī)器學(xué)習(xí)的垃圾郵件快速過濾[J].系統(tǒng)工程理論與實(shí)踐,2014,(S1):179-186.

[15] 吳 渝,馬璐璐,林 茂,等.基于用戶影響力的意見領(lǐng)袖發(fā)現(xiàn)算法[J].小型微型計(jì)算機(jī)系統(tǒng),2015,36(3):561-565.

[17] 潘 全,郭 鳴,林 鵬.基于MapReduce的最大團(tuán)算法[J].系統(tǒng)工程理論與實(shí)踐,2011,(S2):150-153.

[18] 徐文濤,劉 鋒,朱二周.基于MapReduce的新型微博用戶影響力排名算法研究[J].計(jì)算機(jī)科學(xué),2016,43(9):66-70.