基于PageRank的微博用戶影響力度量

王曉彤

(廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，廣東 廣州 510006)

?

基于PageRank的微博用戶影響力度量

王曉彤

(廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，廣東 廣州 510006)

摘要:在微博社區(qū)中具有較高影響力的用戶對信息推薦、市場營銷、輿情控制等方面都起著重要作用.針對現(xiàn)有僅考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的影響力研究方法，以微博用戶為基礎(chǔ)，提出了一種新的微博用戶影響力度量模型——UIRank模型.此模型以用戶之間的交互行為作為切入點(diǎn)，根據(jù)用戶不同行為的權(quán)重差異確定用戶間UIRank值的分配比例.實(shí)驗(yàn)證明，文中提出的影響力度量方法相比已有的方法更加準(zhǔn)確和高效.

關(guān)鍵詞:社交網(wǎng)絡(luò)； 用戶行為交互； 網(wǎng)絡(luò)拓?fù)洌?用戶影響力； 影響力算法

微博作為社交網(wǎng)絡(luò)的重要平臺之一，已經(jīng)成為人們進(jìn)行交流的主要媒介.在微博社區(qū)中，用戶受到的關(guān)注度的高低同其影響力的大小密切相關(guān)，用戶的影響力越大，其受到關(guān)注的程度越高，從而對整個(gè)社交網(wǎng)絡(luò)產(chǎn)生的影響越大.因此，對用戶影響力進(jìn)行量化與排序已經(jīng)成為社會學(xué)[1-2]、心理學(xué)、新聞傳播學(xué)等領(lǐng)域的研究熱點(diǎn).

PageRank算法[3]是研究用戶影響力的一種基本方法，該算法通過網(wǎng)頁的鏈接結(jié)構(gòu)來度量網(wǎng)頁的重要性，谷歌公司已經(jīng)將其應(yīng)用到Twitter[4]用戶的排名中[5].YAMAGUCHI[6]基于微博網(wǎng)絡(luò)圖提出了Twitter用戶排名(TURank) 算法，該算法只考慮了微博的內(nèi)容，但是忽略了其他用戶對內(nèi)容的進(jìn)一步處理.針對PageRank算法沒有考慮主題對排序結(jié)果的影響，T. Havdiwala H等[7]對其進(jìn)行了改進(jìn)，改進(jìn)的算法以網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)為度量基礎(chǔ)，還加入上下文相關(guān)性和主題敏感度等影響因素.康書龍等[8]通過分析新浪微博用戶的行為和關(guān)系提出了一個(gè)更先進(jìn)的算法來評估用戶的影響力，但是該算法只考慮了發(fā)布微博的頻率，忽略了用戶間的交互行為帶來的影響，實(shí)驗(yàn)證明這些因素同樣會對用戶的影響力產(chǎn)生較大的影響.CHA等[9]提出了評估用戶影響力的3個(gè)要素：粉絲數(shù)量，轉(zhuǎn)發(fā)次數(shù)和被提及次數(shù).針對這三方面的度量要素研究了基于主題和時(shí)間的動(dòng)態(tài)性的用戶影響力，發(fā)現(xiàn)有影響力的用戶可以同時(shí)在很多主題上保持較高的影響力.國內(nèi)學(xué)者中，陳浩[10]提出的UserRank算法從用戶自身質(zhì)量及其追隨者(即follower)質(zhì)量入手,考慮追隨者數(shù)量，但是其文中并沒有突出轉(zhuǎn)發(fā)，評論等行為的重要性.并且，近年來，影響力最大化和基于主題的用戶影響力研究也獲得了極大的關(guān)注[11-15].Weng J等[16]提出的TwitterRank算法，不僅考慮網(wǎng)絡(luò)結(jié)構(gòu)與用戶交互，還分析了主題的相似性并與現(xiàn)有的算法進(jìn)行對比.

本文以用戶作為切入點(diǎn)，同時(shí)對網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和微博上的用戶行為進(jìn)行分析，提出了一種新的影響力評估模型——UIRank模型.

1影響力計(jì)算模型

1.1網(wǎng)絡(luò)結(jié)構(gòu)

在微博中，一個(gè)用戶可以在不經(jīng)過其他用戶允許情況下去“關(guān)注(follow)”另一個(gè)用戶，其中，產(chǎn)生“Following”行為的用戶被定義為“Follower”，而“Followed”的用戶定義為“Followee”.微博用戶之間的網(wǎng)絡(luò)結(jié)構(gòu)可以用一個(gè)有向圖(見圖1)表示，圖中的每一個(gè)節(jié)點(diǎn)代表一個(gè)用戶，節(jié)點(diǎn)間的有向邊代表用戶之間的相互關(guān)系.本文使用G=(V,E)代表一個(gè)網(wǎng)絡(luò)結(jié)構(gòu)，其中V代表用戶集合，E是有向邊的集合.圖1中用戶A“follow”用戶B，即A是B的 “Follower”，B是A的“Followee”.除了“關(guān)注”外，微博用戶之間還存在其他交互行為，如轉(zhuǎn)發(fā)(Retweet)、評論(Comment)和提及(Mention).

圖1　微博網(wǎng)絡(luò)中用戶關(guān)系的描述圖

1.2模型假設(shè)

研究表明，微博網(wǎng)絡(luò)結(jié)構(gòu)模型與網(wǎng)頁鏈接模型相似，用戶A“follow”用戶B類似于網(wǎng)頁A“vote”網(wǎng)頁B.本文提出的影響力計(jì)算方法是基于經(jīng)典的PageRank算法[3].PageRank算法[3]的計(jì)算基于以下兩個(gè)基本假設(shè).

1) 數(shù)量假設(shè)：在Web圖模型中，如果鏈接到網(wǎng)頁A的網(wǎng)頁數(shù)量越多，那么網(wǎng)頁A越重要.

2) 質(zhì)量假設(shè)：根據(jù)鏈接到網(wǎng)頁A的網(wǎng)頁質(zhì)量的不同決定網(wǎng)頁A的重要性.如果越多高質(zhì)量的網(wǎng)頁指向網(wǎng)頁A，則網(wǎng)頁A越重要.

利用以上兩個(gè)假設(shè)，PageRank算法初始化時(shí)賦予每個(gè)網(wǎng)頁相同的重要性得分，通過迭代計(jì)算每個(gè)頁面節(jié)點(diǎn)的PageRank值，直到收斂.即被越多優(yōu)質(zhì)的網(wǎng)頁所指的網(wǎng)頁，它是優(yōu)質(zhì)網(wǎng)頁的概率就越大.

由于存在一些出鏈為0，沒有鏈接指向任意其他網(wǎng)頁的網(wǎng)頁.因此需要對 PageRank公式進(jìn)行修正，即在原來的公式中增加了阻尼系數(shù)(damping factor)p，一般p取值0.85.其意義是，在任意時(shí)刻，用戶到達(dá)某頁面后并繼續(xù)向后瀏覽的概率. 則1-p=0.15表示用戶停止點(diǎn)擊，隨機(jī)跳到新網(wǎng)頁鏈接的概率.PageRank的計(jì)算公式如下：

(1)

本文根據(jù)微博網(wǎng)絡(luò)結(jié)構(gòu)模型與網(wǎng)頁鏈接模型相似，對PageRank的假設(shè)進(jìn)行修正，提出UIRank模型的兩個(gè)假設(shè).

假設(shè)1：如果一條微博被轉(zhuǎn)發(fā)評論多次，那么可以認(rèn)為它很重要.

假設(shè)2：一條微博被轉(zhuǎn)發(fā)評論次數(shù)不高但是轉(zhuǎn)發(fā)評論該微博的用戶中包含高影響力用戶，那么同樣可以認(rèn)為它很重要.

UIRank模型初始化方式為：首先，隨機(jī)訪問用戶集合中的一個(gè)用戶，然后根據(jù)當(dāng)前用戶的“follow”關(guān)系繼續(xù)訪問下一個(gè)用戶.

1.3模型構(gòu)建

本文充分考慮微博用戶的不同行為，通過改進(jìn)傳統(tǒng)的PageRank算法評估微博的用戶影響力，使得它更適合微博網(wǎng)絡(luò)結(jié)構(gòu).

在PageRank算法中，每個(gè)網(wǎng)頁將其當(dāng)前的PageRank值平均分配到本網(wǎng)頁包含的所有網(wǎng)頁鏈接，這樣將導(dǎo)致網(wǎng)頁本身的重要性被忽略.所以在UIRank模型的分析過程中，將用戶不同行為的權(quán)重作為分配UIRank值的依據(jù).最終，活躍度高的用戶影響力將會比活躍度低的用戶高，這樣可以彌補(bǔ)僅依賴“Follower”和“Followee”關(guān)系網(wǎng)絡(luò)評估影響力的缺陷.UIRank模型的數(shù)學(xué)表示如下：

(2)

其中，p是阻尼系數(shù)，本文取值為0.5;M(u)是用戶u的所有“Follower”的集合；A(v,u)是用戶v對用戶u的UIRank值的貢獻(xiàn)比率，表示用戶u的行為權(quán)重占用戶v的所有“Followee”的行為權(quán)重之和的比例，公式表達(dá)為

(3)

式(3)中，Wu代表用戶u的用戶行為權(quán)重，Nv代表用戶v的“Followee”數(shù)目(即用戶v的出度).

根據(jù)前面的描述，UIRank模型相比TunkRank等其他模型最大的改進(jìn)是對用戶不同行為做了充分的分析，將其作為影響力評估的重要指標(biāo).UIRank算法通過分析不同行為的權(quán)重分配UIRank值.其中，用戶行為主要包括用戶更新微博的頻率，與其他用戶的交互(評論，轉(zhuǎn)發(fā))等，將它們作為用戶的活躍度和用戶之間互動(dòng)的積極度.圖2為用戶行為權(quán)重模型.

圖2　用戶行為權(quán)重模型

式(3)中采用Wu代表用戶u的行為權(quán)重，同時(shí)考慮用戶活躍度和互動(dòng)積極度，得

Wi=a·Xi+b·Yi.

(4)

式(4)中用戶的活躍度Xi表示在一個(gè)時(shí)間段內(nèi)用戶更新微博的頻率，用戶的互動(dòng)積極度Yi表示在一個(gè)時(shí)間段內(nèi)用戶之間提到(Mention)，評論(Comment)和轉(zhuǎn)發(fā)(Retweet)的交互頻率.

(5)

(6)

其中，T表示一個(gè)時(shí)間段.為了更客觀地描述用戶的活躍度和積極度，T選取同一個(gè)時(shí)間段.Pi表示用戶i發(fā)表的微博數(shù)目，Ai表示“@”的數(shù)量，Ci表示評論數(shù)，Ri表示轉(zhuǎn)發(fā)數(shù)，c，d，e分別表示加權(quán)系數(shù).根據(jù)對UIRank模型的分析可知，用戶行為對權(quán)值的影響不同，加權(quán)系數(shù)也不同.本文使用序關(guān)系分析法確定UIRank算法中權(quán)重系數(shù)，序關(guān)系分析法的定義如下.

定義1若評價(jià)指標(biāo)Xi相對于某評價(jià)目標(biāo)的重要性程度大于Xj時(shí)，記為Xi>Xj.

在序關(guān)系分析法中，不同評價(jià)指標(biāo)之間存在數(shù)量約束rk，rk的確定滿足如下的兩個(gè)定理.

定理1若評價(jià)指標(biāo)X1,X2,X3…,Xm之間存在序數(shù)關(guān)系X1>X2>X3…>Xm,則rk與rk-1之間必須滿足，rk-1>1/rk.

通過上文用戶行為的分析，微博作為一個(gè)交互網(wǎng)絡(luò)，用戶之間的交互行為比用戶發(fā)微博的行為更具影響力，而在用戶交互行為中評論行為將作為首要因素，基于序關(guān)系分析法，本文將作如下參數(shù)設(shè)置：a= 0.4，b= 0.6，c= 0.5，d= 0.3，e= 0.2.然后通過式(5)和(6)計(jì)算活躍度Xi和積極度Xj，最后得到用戶行為權(quán)重Wi.UIRank的算法的基本描述如表1所示.

表1　UIRank算法基本描述

2實(shí)驗(yàn)

2.1數(shù)據(jù)描述

騰訊微博自2010年4月創(chuàng)建以來已經(jīng)成長為國內(nèi)最大的微博網(wǎng)站之一.當(dāng)前，騰訊微博注冊用戶超過兩億，每天產(chǎn)生超過4千萬條微博信息，為保證本文使用騰訊微博的數(shù)據(jù)集更具有說服力，本文使用的數(shù)據(jù)集來自國際知識發(fā)現(xiàn)和數(shù)據(jù)挖掘競賽(KDD Cup).在進(jìn)行實(shí)驗(yàn)之前，本文先對數(shù)據(jù)進(jìn)行預(yù)處理，剔除數(shù)據(jù)集中的冗余樣本以及不完整樣本，最終得到包含60 000多個(gè)用戶的樣本集.數(shù)據(jù)集中各字段描述如表2所示.

表2　數(shù)據(jù)集中各個(gè)字段含義

2.2實(shí)驗(yàn)結(jié)果和算法比較

為了證明UIRank算法的準(zhǔn)確性，本文采用TunkRank算法在相同的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)并作對比.TunkRank算法的數(shù)學(xué)描述如式(7)所示，p值取0.2.

(7)

其中，F(xiàn)ollowers是v的所有“Follower”，F(xiàn)ollowees是v的所有“Followee”.

表3和表4展示了通過TunkRank和UIRank兩種算法在相同數(shù)據(jù)集上找到的排名前十的最有影響力的用戶，可以觀察到在兩個(gè)表中有7個(gè)用戶是重疊的.在UIRank算法中，用戶1010402，用戶640892和用戶330571成為進(jìn)入前十的新用戶，它們原來在TunkRank算法中分別排第11位，第39位和48位.他們能夠進(jìn)入前十的原因各不相同.雖然被其他人提到的次數(shù)少，但是用戶1010402獲得相對較大數(shù)量的轉(zhuǎn)發(fā)行為.對于用戶640892和330571，他們分別被4個(gè)和3個(gè)排名前十的用戶“follow”，彌補(bǔ)了追隨者少和交互少的缺陷.此外，用戶1774520排名高于用戶1775076的原因是他/她與他人互動(dòng)頻繁.通過本文提出的UIRank算法得到影響力排名前30名用戶中，有22個(gè)用戶被排在第一位的用戶1928699“follow”.因此，對比兩種方法的實(shí)驗(yàn)結(jié)果可知TunkRank算法嚴(yán)重依賴“follower”的數(shù)量和質(zhì)量，UIRank算法不但考慮“Follower”的因素還進(jìn)一步考慮用戶間的行為交互，更加合理準(zhǔn)確.

2.3驗(yàn)證

在2.2中驗(yàn)證了UIRank模型的有效性，本部分將驗(yàn)證通過UIRank模型挑選出的最有影響力用戶的正確性.因?yàn)楸疚氖褂玫臄?shù)據(jù)集中用戶經(jīng)過了匿名處理，不能得到他們在微博中真實(shí)的用戶名，所以，本文采用與引文[17]中影響力最大化相似的評估方法.基于上一部分選出的最有影響力的10個(gè)用戶，仿照網(wǎng)絡(luò)中信息傳播度量的方法得到最后被激活(activated)的用戶數(shù)目.最后本文根據(jù)不同方法激活的用戶數(shù)目進(jìn)行對比.首先發(fā)現(xiàn)通過UIRank模型得到的影響力的取值范圍是0到1，這個(gè)數(shù)值反映了一個(gè)用戶對另一個(gè)用戶產(chǎn)生影響的程度.由于本文的主要目的不是計(jì)算信息傳播概率，根據(jù)引文[17]可知本文將UIRank值作為傳播概率是合理的，本文選取TunkRank，PageRank和MaxDegree方法進(jìn)行對比分析，以此驗(yàn)證通過UIRank方法得到的結(jié)果是準(zhǔn)確的.

表3　TunkRank算法排名前10的最有影響力的用戶

表4　UIRank算法排名前10的最有影響力的用戶

基于引文[17]本文首先將種子集合的大小標(biāo)記為k，對應(yīng)的種子集中包含最有影響力的k個(gè)用戶，再根據(jù)1到10的排名，本文添加下一個(gè)最有影響力的用戶到種子集中，每一次的實(shí)驗(yàn)結(jié)果都進(jìn)行了10 000次的模擬，圖3中可以看到所有方法的趨勢都是上升的，但是每一次通過本文中的方法選中的k個(gè)用戶激活的用戶最多，這樣就可以證明本文提出的方法是最有效的，并且選出的用戶確實(shí)是最有影響力的.

圖3　不同方法激活用戶數(shù)對比圖

3結(jié)論

本文通過考慮用戶之間的行為交互對PageRank算法進(jìn)行改進(jìn)，提出一個(gè)新的模型來對用戶影響力進(jìn)行分析，并與TunkRank算法進(jìn)行比較，進(jìn)一步分析它們之間的差異.最后，本文將幾個(gè)著名的算法選為基線，使用影響最大化來驗(yàn)證算法的有效性.實(shí)驗(yàn)結(jié)果表明，本文算法的結(jié)果更加準(zhǔn)確和高效.

由上面的分析可以得到以下結(jié)論：(1) 一般情況下，追隨者的數(shù)量和質(zhì)量在一定程度上影響用戶的影響力；(2) 用戶影響力和用戶與他人的交互行為密切相關(guān)，而且不同交互行為對他人影響力的貢獻(xiàn)是不一樣的；(3) 一些用戶即使在追隨者“Follower”數(shù)量和交互(Interaction)上有劣勢，但當(dāng)這些“follower”擁有很大的影響力值時(shí)，也會使這些用戶獲得很大的影響值.

本文中提出的UIRank模型可以合理準(zhǔn)確地計(jì)算微博用戶的影響力，對于市場營銷，輿情控制等方面都有重要的現(xiàn)實(shí)意義.高質(zhì)量的微博內(nèi)容將更有利于傳播，但是本文的UIRank模型并沒有對微博內(nèi)容本身進(jìn)行分析.這個(gè)問題是后續(xù)研究的重點(diǎn).

參考文獻(xiàn)：

[1] 楊春燕, 李志明. 基于可拓學(xué)的社會網(wǎng)絡(luò)結(jié)構(gòu)研究[J]. 廣東工業(yè)大學(xué)學(xué)報(bào), 2014, 31(1): 1-6.

YANG C Y, LI Z M. Extenics based social network structure[J]. Journal of Guangdong University of Technology, 2014, 31(1): 1-6.

[2] 朱伶俐, 李衛(wèi)華, 李小妹. 客戶價(jià)值可拓知識挖掘軟件研究[J]. 廣東工業(yè)大學(xué)學(xué)報(bào), 2012, 29(4): 7-13.

ZHU L L, LI W H, LI X M. Research on extension knowledge mining[J]. Journal of Guangdong University of Technology, 2012, 29(4): 7-13.

[3] PAGE L, BRIN S, MOTWASNI R, et al. The PageRank citation ranking: bringing order to the web[R]. Stanford InfoLab, 1999.

[4] KWAK H, LEE C, PARK H. What is Twitter, a social network or a news media?[C]∥ Proceedings of the 19th International Conference on World Wide Web. Raleigh NC:ACM, 2010: 591-600.

[5] GAYO-AVELLO D. Nepotistic relationships in twitter and their impact on rank prestige algorithms[J]. Information Processing & Management, 2013, 49(6): 1250-1280.

[6] YAMAGUCHI Y, TAKAHASHI T, AMAGASA T. Turank: Twitter user ranking based on user-tweet graph analysis[C]∥Web Information Systems Engineering-WISE 2010.Hong Kong:Springer Berlin Heidelberg, 2010: 240-253.

[7] HAVELIWALA T H. Topic-sensitive pagerank: A context-sensitive ranking algorithm for web search[J]. Knowledge and Data Engineering, 2003, 15(4): 784-796.

[8] 康書龍.基于用戶行為及關(guān)系的社交網(wǎng)絡(luò)節(jié)點(diǎn)影響力評價(jià)[D]. 北京：北京郵電大學(xué)信息與通信工程學(xué)院, 2011:1-59.

[9] CHA M, HADDADI H, BENEVENUTO F. Measuring user influence in Twitter: The million follower fallacy[C]∥ Proceedings of the 4th International AAAI Conference on Weblogs and Social Media. Atlanta: AAAI, 2010: 10-17.

[10] 陳浩. 基于 Hadoop 的微博用戶影響力排名算法研究[D]. 上海: 華東理工大學(xué)信息科學(xué)與工程學(xué)院, 2014.

[11] GOYAL A, BONCHI F, LAKSHMANAN L V S. A data-based approach to social influence maximization[J]. Proceedings of the VLDB Endowment, 2011, 5(1): 73-84.

[12] LIU L, TANG J, HAN J. Mining topic-level influence in heterogeneous networks[C]∥Proceedings of the 19th ACM International Conference on Information and Knowledge Management. Toronto Canada: ACM, 2010: 199-208.

[13] LI D, SHUAI X, Sun G. Mining topic-level opinion Influence in microblog[C]∥Proceedings of the 21st ACM international Conference on Information and Knowledge Management. Maui USA: ACM, 2012: 1562-1566.

[14 BARBIERI N, BONCHI F, MANCO G. Topic-aware social influence propagation models[J]. Knowledge and Information Systems, 2013, 37(3): 555-584.

[15] LIN C X, MEI Q, HAN J. The joint inference of topic diffusion and evolution in social communities[C]∥Data Mining (ICDM), 2011 IEEE 11th International Conference on. Vancouver BC: IEEE, 2011: 378-387.

[16] WENG J, LIM E P, JIANG J. Twitterrank: finding topic sensitive influential twitterers[C]∥Proceedings of the third ACM International Conference on Web Search and Data Mining. New York: ACM, 2010: 261-270.

[17] KEMPE D, KIEINBERG J, TARDOS é. Maximizing the spread of influence through a social network[C]∥Proceedings of the nineth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York NY: ACM, 2003: 137-146.

An Evaluation of Microblog Users’ Influence Based on PageRank

Wang Xiao-tong

(School of Computers, Guangdong University of Technology, Guangzhou 510006, China)

Abstract:High-impact users of microblog play an significant role in information recommendation, marketing, public opinion analysis and other areas. Aiming at the existing approaches to users’ influence only considering the network topology and taking the users of microblog as the entry point, a new model for calculating users’ influence is proposed-UIRank model. This model gives adequate consideration to the interaction between users and determines the distribution of the value of UIRank according to the weight difference of different user behaviors. It is proved by the results of the experiments that the method for calculating the users’ influence proposed is more accurate and efficient.

Key words:social networks; user interaction behavior; network topology; user influence; influence algorithm

收稿日期:2015- 03- 03

基金項(xiàng)目:國家自然科學(xué)基金資助項(xiàng)目(61100148;61202269)

作者簡介:王曉彤(1989-)，男，碩士研究生，主要研究領(lǐng)域?yàn)樯缃痪W(wǎng)絡(luò)中的用戶影響力.

doi:10.3969/j.issn.1007- 7162.2016.03.009

中圖分類號:TP393

文獻(xiàn)標(biāo)志碼:A

文章編號:1007-7162(2016)02- 0049- 06