丁溫雪，徐家興，朱顥東

(鄭州輕工業(yè)學院 計算機與通信工程學院，河南 鄭州 450002)

?

基于改進PageRank算法的微博用戶影響力排序研究

丁溫雪，徐家興，朱顥東*

(鄭州輕工業(yè)學院 計算機與通信工程學院，河南 鄭州 450002)

針對傳統(tǒng)的PageRank算法中存在主題漂移和偏重舊網頁的弊端，提出了一種基于改進PageRank算法的微博用戶影響力排序方法——TSPR算法.該算法將時間因素作為橫向標度，采用TF-IDF方法計算網頁間的相似度，并具體分析某個時間段用戶搜索主題相似度的變化.通過計算網頁PR值的大小，從而對微博用戶影響力進行排序.仿真實驗結果表明，該算法改善了微博用戶影響力排序效果，與此同時，提高了搜索質量和準確率.

PageRank算法；時間因子；主題相似度；用戶影響力排序

截至2016年6月，CNNIC發(fā)布的報告[1]中指出，我國網民規(guī)模達到7.10億，半年共計新增網民2 132萬人，半年增長率為3.1%，較2015年下半年增長率有所提升.互聯網技術發(fā)展迅猛，微博早已成為人們進行信息交流的重要平臺.經典的PageRank算法[2]忽視了用戶的個性化需求，網絡的內容和結構是不斷變化的，用戶實際訪問時常常忽略時間因素，這是不符合用戶行為規(guī)律的.如何根據用戶實際需求與搜索主題相似度這兩種因素，從而改進PageRank算法對重要網頁進行排序成為了重點研究的問題.

目前，眾多專家學者運用PageRank算法的相關改進算法對微博用戶影響力進行排名.在國內，隨著互聯網技術的普及，面對大規(guī)模的用戶群.陳淑鑫等[3]通過分析傳統(tǒng)的本體映射方法及相似度計算方法無法處理模糊信息的缺陷提出了一種新的基于向量空間模型的模糊概念相似度計算方法.實驗結果表明，該方法有效地處理了模糊信息間的相似度問題.黃賢英等[4]提出基于語義的文本相似度算法.不同格式的文本類型對文本相似度算法的適用能力也各不相同，因此他們分別給出了短文本詞性切分、關鍵詞權值計算、詞性空間相似度計算、中/英文本相似度計算的方法進行研究，有效地識別了“僵尸”用戶.在國外，針對傳統(tǒng)的PageRank算法沒有考慮主題對排序結果的影響，W.Gang,W.Yimin等[5]在主題相似度方面進行了改進，該方法不但把網絡的拓撲結構作為度量基礎，還加入了上下文相關性和主題敏感度等相關影響因素，最后，通過大量的仿真實驗，驗證了他們的假設.Weng J等[6]提出了TwitterRank算法，不但考慮了網絡結構與用戶交互，而且還分析了主題的相似性，并將它與現有的算法進行對比，綜合所有獲取到的主題計算出每個Twitter用戶的影響力之和，從而達到對Twitter用戶的影響力排序的目的.

針對傳統(tǒng)PageRank算法中存在的缺陷，本文提出了一個基于網頁質量、時間因子不斷更新[7]、分析網頁主題相關[8]的內容的改進型PageRank算法.

1 相關技術

Larry Page和Sergey Brin認為網頁之間通過超鏈接相互連接，互聯網上不計其數的網頁就構成了一張超大的圖.用戶從全部網頁中隨機選擇一個網頁進行瀏覽，通過超鏈接在網頁上不斷跳轉到每個網頁時，都會有兩種選擇：①到此結束；②繼續(xù)選擇一個鏈接瀏覽.因此，計算一張網頁，例如網頁A的等級的標準公式如式(1).

(1)

式(1)中，n表示全部網頁的總數量，PR(A)表示其中的一張網頁(例如網頁A)的PR值，PR(Pi)表示鏈接到A的網頁Pi的值，C(Pi)表示網頁Pi的出棧鏈接數量.為避免網頁之間出現懸掛鏈接而導致穩(wěn)態(tài)概率無法收斂的情況，在這里，引入阻尼系數d(0

隨機游走模型定義參見文獻[9].假設用戶以相等的概率在當前頁面的所有超鏈接中隨機選擇一個鏈接繼續(xù)瀏覽.當經過很多次游走之后，每個網頁被用戶訪問到的概率就會趨向于一個穩(wěn)定值.算法迭代關系式如下所示：

(2)

式(2)中，in(i)表示指向網頁i的網頁集合，out(j)表示網頁j指向的網頁集合.斯坦福大學的Haveliwala于2002年在《Topic-sensitivepagerank》一文中提出了PersonalRank算法.用user節(jié)點和item節(jié)點替換式(1)中的網頁節(jié)點就可以計算出每個user和每個item在全局的重要性，從而給出全局的排名，然而，需要計算行為節(jié)點相對于某一個用戶節(jié)點u的相關性.該算法能夠為用戶個性化所有相關行為進行排序.它的迭代公式如下：

(3)

式(3)中，用ri替換了1/n，也就是說從不同點開始的概率不同.u表示推薦的目標用戶，這樣使用上式計算的就是所有頂點相對于頂點u的相關度.PersonalRank算法[10]執(zhí)行步驟的偽代碼如下：

假設從每個點開始的概率都是相同的

Step1：初始化每個節(jié)點的初始概率值，如果對用戶u進行推薦，則令u對應的節(jié)點的初始訪問概率為1，其他節(jié)點的初始訪問概率為0，然后再使用迭代公式計算.

Step2：從用戶u對應的節(jié)點開始游走，每到一個節(jié)點都以1-d的概率停止游走并從u重新開始.

Step3：以d的概率繼續(xù)游走，從當前節(jié)點指向的節(jié)點中按照均勻分布隨機選擇一個節(jié)點往下游走.

Step4：經過很多輪游走之后，每個頂點被訪問到的概率也會收斂，趨于某個穩(wěn)定值.

對于PageRank來說，因為每個節(jié)點的初始訪問概率相同，所以所有節(jié)點的初始訪問概率都是1/n(n是節(jié)點總數).雖然隨機游走模型考慮到用戶的實際需求，但是卻忽略了網頁之間內容的相關性，容易造成主題漂移現象.

2 算法改進

2.1 主題相似度

在當前的基于PageRank的改進算法中，楊武等[11]運用改進的空間向量模型，即TF-IDF公式，計算出存在鏈接關系的網頁u和網頁v分別關于詞語ti的權值W′(i,u)和W′(i,v).將網頁內容定義為向量空間模型中的向量，本文采用余弦向量度量法，從而計算出各微博在內容上的相似性.因此，相似度權值計算公式如式(4).

(4)

在式(4)中，網頁ui和網頁vi的內容相似度權值，由W(ui,vi)表示；詞語ti在網頁u中的詞項權值，由W′(i,u)表示；詞語ti在網頁v中的詞項權值，由W′(i,v)表示.

利用計算公式(5)，計算出網頁內容相似度在公式(7)中所占的比重.

(5)

在式(5)中，Wuivi表示用戶vi在用戶ui的所有出度中，內容相似度所占據的權重；Oui表示用戶ui指向用戶vi的集合，k∈Oui.

2.2 時間因子

一般地，用網頁被搜索引擎搜索到的數目來表示網頁本身存在的時間長短，針對PageRank算法中存在的偏重舊網頁、忽視新的有價值網頁的現象，論文結合時間反饋因子，計算公式如式(6).

(6)

式(6)中，T作為網頁被搜索引擎搜索到的周期次數.Wt為網頁的時間反饋因子.e作為常數，它的取值為e=(1-d)/n，它與搜索引擎訪問到的網頁總數目n有關，還受到式(1)中d的影響.一般而言，搜索引擎的搜索周期是15～30d.假如一個網頁在網絡中存在的時間愈久，相應的，它在每個搜索周期里被訪問到的概率愈大.換言之，單個網頁的存在時間與搜索引擎訪問到其的次數是成正比的.

2.3 改進的PageRank算法

本文提出了一種TSPR算法(TimeandSimilarityPageRankAlgorithm)，將此算法運用到微博用戶影響力排序中，觀察排序結果.在研究微博用戶影響力排序中，考慮到主題相似度和時間因子在計算PR值時所占比重不同.因此，引入比例系數α、β，且α+β=1.計算公式如(7).

(7)

式(7)中，TSPR(ui)表示微博用戶影響力計算的PR值.微博總數越大，用戶之間的交互性越多，網頁之間的相似度就越高，這在一定程度上避免了主題漂移問題.該算法結合時間反饋因子，攻克了提取網頁發(fā)布時間的瓶頸，能更準確地判斷網頁不斷更新的日期.網頁PR值的大小受網頁發(fā)布時間長短影響，這有利于舊網頁沉淀、新網頁迅速上浮.這有效地抑制了“僵尸用戶”現象.

表1 用戶數據統(tǒng)計情況

3 實驗

3.1 實驗準備

由于新浪對微博做了爬蟲設置，限制了一個小時內每個IP地址對它的訪問量.調用官方API獲得的數據噪聲小，處理起來比較方便.本文采用新浪微博作為實驗數據平臺，結合廣度優(yōu)先算法和深度優(yōu)先算法，一層一層的獲取用戶及用戶之間的數據.其中新浪微博的各個模塊共劃分成12類主題，主要包括科技、體育、文化、天氣、房地產、電影、教育、政治、生物、明星.本文是從2016年1月1日至當年的2月15日采集到的數據.將部分用戶微博信息作為研究數據，數據包括用戶集U，微博數據集Z，微博網頁集θj，微博文本集X等.數據存儲內容主要有：

1)用戶信息：用戶UID，用戶昵稱，性別，所在地，創(chuàng)建微博的時間，用戶主頁URL，粉絲數，關注數，微博數；

2)微博信息：微博MID，發(fā)布時間，微博內容，微博來源，轉發(fā)數，評論數，被贊數，發(fā)表用戶UID，微博所屬主題；

3)收聽關系：用戶UID、粉絲ID；

4)關注關系：用戶UID、關注ID.

由于新浪微博的限制，每個用戶最多只能獲取到200個關注人的信息，因此搜集到的好友關系不是很全面.把所有的搜集到的微博用戶數據進行合并，并用爬蟲工具簡單清洗，去掉重復項.最終獲得的用戶數據統(tǒng)計情況如表1所示.

實驗環(huán)境設置：

1)硬件方面：1臺惠普服務器，3.4 GHz Intel i7-4790,1 TB硬盤和2臺惠普 PC 3.6 GHz Intel 處理器，4 G內存，500 G硬盤.

2)軟件方面：Win7操作系統(tǒng)，Matlab仿真工具，MySQL 5.5 數據庫.

圖1 參數值α的取值對微博用戶查詢結果前30項數據中位置P的影響Fig.1 The parameter valueα value impact on micro-blog query results before the 30 position in the P data

圖2 改進前后的PageRank算法的精確度對比Fig.2 The accuracy comparison of the PageRank algorithm before and after the improvement

8大主題經典的PageRank算法WPR算法Timed-PageRank算法TSPR算法星座0.8200.8840.8900.940教育0.8300.9400.9000.970電影0.5410.5830.6240.660科技0.5160.5200.5400.560旅游0.5000.5120.5200.530汽車0.5400.5310.5290.563房地產0.6890.7240.7960.824美食0.6750.7280.7870.795

3.2 實驗結果與分析

3.2.1 參數取值 初始化每個節(jié)點的初始概率值，則令初始訪問概率為0.經過數據計算，當α=0.1，β=0.9時，即，用戶主題相似度比重很小，時間因子的比重很大，此時，用戶想要搜索到的微博用戶之間的相似度小，時間周期長；反之，當α=0.9，β=0.1時，所要查找的微博用戶比較靠前，但此時都是一些舊的微博用戶，新用戶的很少參與到影響力排序的結果中，因此，二者都達不到微博用戶影響力的真實排序的目的.然而，當文章取α=0.6，β=0.4時，微博用戶在查詢結果前topk[12](在這里，k取30)中的位置P是最靠前的，從而求出比例系數的取值.實驗對比結果如圖1所示.

3.2.2 準確率對比 為了獲得本文提出的相似度權值和時間因子等因素對改進型TSPR算法性能的影響，將文章改進型的TSPR算法與其他基于PageRank的相關算法作比較.例如：經典的PageRank算法、WPR算法[13]、Timed-PageRank算法[14]，把這4種算法放在一起分別作對比.運用Matlab工具進行仿真實驗.取搜索到的前600項數據作為標準結果集.對要查找的網頁主題與實際查詢到的網頁進行相關性分析.本文利用查準率(又稱為準確率)作為衡量查詢結果的質量標準.由于用戶習慣性關注前50頁的查詢結果，因此文章選擇前50項作為樣本，實驗對比結果如表2所示.

通過仿真實驗對比結果，發(fā)現改進的TSPR算法在各類主題的查詢中，查準率均高于其他三類算法，各類主題相關的查全率均在50%以上.其中，關于星座、教育方面的查詢率分別高達94%、97%，這是跟用戶的行為習慣及用戶經常進行話題互動緊密結合的；在科技、旅游等方面，用戶很少進行交互活動，因此查詢率也就相對較低.然而，TSPR算法與其他四種基于PageRake算法進行比較，均優(yōu)于其他算法.

最后，經過隨機抽樣，對頁面排序結果進行評價.為了均衡準確率和召回率兩個評價指標，通過做實驗的方法得知，當特征項的個數取值為10的時候，不僅運算量較小，而且查準率和召回率(又稱為查全率)達到一個最優(yōu)的效果，此時，準確率達到92.88%，召回率達到83.48%.

3.2.3 滿意度調查 從計算機學院隨機選擇60名研究生對本文提出的TSPR算法進行滿意度調查.對采集的結果采用評分制.非常滿意得6分，比較滿意得4分，感覺一般得2分.從圖中可以看出，改良之后的PageRank算法的準確度比原始的PageRank算法高得多，從而證明了其優(yōu)越性.

4 結束語

針對傳統(tǒng)的PageRank算法本身存在的問題，文章提出了一種基于改進PageRank算法的微博用戶影響力排序的研究方法.通過對相關主題權值和時間因子等因素進行分析計算，為用戶影響力排序提供了一種參考方法.在不同主題的復雜因素的環(huán)境中將它與其他PageRank算法進行對比試驗，通過數據計算比較，發(fā)現四種算法的準確率對比明顯，改進后的算法計算出的用戶影響力排序結果均優(yōu)于現有的用戶影響力相關改進算法，結果更加貼近現實，表明了TSPR算法的有效性和可行性.

[1] CNNIC.Statistical Report on the Development of the thirty-seventh China Internet Network[R].Beijing：China Internet Network Information Center，2016:75-76.

[2] 王德廣,周志剛,梁旭.PageRank算法的分析及其改進[J].計算機工程,2010, 36(22):291-292.

[3] 張凌宇, 陳淑鑫, 張光妲，等.一種基于向量空間模型的模糊本體映射方法[J].計算機應用研究,2014,31(5):1459-1462.

[4] 張金鵬,黃賢英.基于語義的文本相似度算法研究及應用[D].重慶: 重慶理工大學, 2014.

[5] WU G,WEI YM.Arnoldi versus GMRES for computing pageRank: A theoretical contribution to google′s pageRank problem[C]//Proceedings of the 4th ProQuest,USA IEEE,2012:192-199.

[6] 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,ACM,2010:261-270.

[7] WANG X T,HAO Z F.Analyzing the influence of social network users combined with the time factor[D]. Guangdong: Guangdong University of Technology，2015:15-41.

[8] PENG W,WANG J,ZHAO B,et al.Identification of Protein Complexes Using Weighted PageRank-Nibble Algorithm and Core-Attachment Structure[J]. IEEE/ACM Transactions on Computational Biology & Bioinformatics,2015,12(1):179-192.

[9] 曹姍姍,王沖.基于網頁鏈接與用戶反饋的PageRank算法改進研究[J].計算機科學,2014,41(12):179-182.

[10] CHEN X,WANG P,QIN Z,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.

[11] 李稚楹，楊武.基于網頁內容和內容反饋的網頁排序PageRank算法研究[D].重慶:重慶理工大學,2012.

[12] SILBERSTEIN A S,BRAYNARD R,ELLIS C,et al.A Sampling-Based Approach to Optimizing Top-k Queries in Sensor Networks[J].Icde,2013:68-68.

[13] WANG C H,ZHU J P.Improved inequality transfer weight PageRank algorithm[J].Computer Engineering & Design,2010,31(10):2231-2230.

[14] GANESH V.Timed PageRank and branching heuristics in CDCL SAT solvers[J].Banff International Research Station for Mathematical Innovation & Discovery,2014,24(1):11-29.

責任編輯：時 凌

Research on Ranking of Micro-blog Users′ Influence Based on Improved PageRank Algorithm

DING Wenxue，XU Jiaxing，ZHU Haodong*

(School of Computer and Communication Engineering,Zhengzhou University of Light Industry,Zhengzhou 450002,China)

Aiming at the shortcomings of the traditional PageRank algorithm,a kind of ranking method based on improved algorithm(TSPR) was proposed.In this algorithm, the time factor is used as the scale,the TF-IDF method is used to calculate the similarity between web pages,and the variation of the similarity between the users in a certain period of time is analyzed.By calculating the PR value of the Web page,micro-blog users′ influence is ranked.The simulation results show that the proposed algorithm can improve the ranking effect of micro-blog users and enhance the quality and accuracy of the search.

PageRank algorithm;time factor;topic similarity;ranking of users′ influence

2016-08-11.

國家自然科學基金項目(61201447).

丁溫雪(1988- )，女，碩士生，主要從事智能信息處理、模式識別研究；*

1008-8423(2016)03-0256-05

10.13501/j.cnki.42-1569/n.2016.09.004

TP301

A