基于改進(jìn)PageRank算法的微博用戶影響力排序研究

丁溫雪，徐家興，朱顥東

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

?

基于改進(jìn)PageRank算法的微博用戶影響力排序研究

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

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

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

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

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

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

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

1 相關(guān)技術(shù)

Larry Page和Sergey Brin認(rèn)為網(wǎng)頁之間通過超鏈接相互連接，互聯(lián)網(wǎng)上不計(jì)其數(shù)的網(wǎng)頁就構(gòu)成了一張超大的圖.用戶從全部網(wǎng)頁中隨機(jī)選擇一個(gè)網(wǎng)頁進(jìn)行瀏覽，通過超鏈接在網(wǎng)頁上不斷跳轉(zhuǎn)到每個(gè)網(wǎng)頁時(shí)，都會(huì)有兩種選擇：①到此結(jié)束；②繼續(xù)選擇一個(gè)鏈接瀏覽.因此，計(jì)算一張網(wǎng)頁，例如網(wǎng)頁A的等級(jí)的標(biāo)準(zhǔn)公式如式(1).

(1)

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

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

(2)

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

(3)

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

假設(shè)從每個(gè)點(diǎn)開始的概率都是相同的

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

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

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

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

對于PageRank來說，因?yàn)槊總€(gè)節(jié)點(diǎn)的初始訪問概率相同，所以所有節(jié)點(diǎn)的初始訪問概率都是1/n(n是節(jié)點(diǎn)總數(shù)).雖然隨機(jī)游走模型考慮到用戶的實(shí)際需求，但是卻忽略了網(wǎng)頁之間內(nèi)容的相關(guān)性，容易造成主題漂移現(xiàn)象.

2 算法改進(jìn)

2.1 主題相似度

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

(4)

在式(4)中，網(wǎng)頁ui和網(wǎng)頁vi的內(nèi)容相似度權(quán)值，由W(ui,vi)表示；詞語ti在網(wǎng)頁u中的詞項(xiàng)權(quán)值，由W′(i,u)表示；詞語ti在網(wǎng)頁v中的詞項(xiàng)權(quán)值，由W′(i,v)表示.

利用計(jì)算公式(5)，計(jì)算出網(wǎng)頁內(nèi)容相似度在公式(7)中所占的比重.

(5)

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

2.2 時(shí)間因子

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

(6)

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

2.3 改進(jìn)的PageRank算法

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

(7)

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

表1 用戶數(shù)據(jù)統(tǒng)計(jì)情況

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

3.1 實(shí)驗(yàn)準(zhǔn)備

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

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

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

3)收聽關(guān)系：用戶UID、粉絲ID；

4)關(guān)注關(guān)系：用戶UID、關(guān)注ID.

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

實(shí)驗(yàn)環(huán)境設(shè)置：

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

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

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

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

8大主題經(jīng)典的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房地產(chǎn)0.6890.7240.7960.824美食0.6750.7280.7870.795

3.2 實(shí)驗(yàn)結(jié)果與分析

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

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

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

最后，經(jīng)過隨機(jī)抽樣，對頁面排序結(jié)果進(jìn)行評價(jià).為了均衡準(zhǔn)確率和召回率兩個(gè)評價(jià)指標(biāo)，通過做實(shí)驗(yàn)的方法得知，當(dāng)特征項(xiàng)的個(gè)數(shù)取值為10的時(shí)候，不僅運(yùn)算量較小，而且查準(zhǔn)率和召回率(又稱為查全率)達(dá)到一個(gè)最優(yōu)的效果，此時(shí)，準(zhǔn)確率達(dá)到92.88%，召回率達(dá)到83.48%.

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

4 結(jié)束語

針對傳統(tǒng)的PageRank算法本身存在的問題，文章提出了一種基于改進(jìn)PageRank算法的微博用戶影響力排序的研究方法.通過對相關(guān)主題權(quán)值和時(shí)間因子等因素進(jìn)行分析計(jì)算，為用戶影響力排序提供了一種參考方法.在不同主題的復(fù)雜因素的環(huán)境中將它與其他PageRank算法進(jìn)行對比試驗(yàn)，通過數(shù)據(jù)計(jì)算比較，發(fā)現(xiàn)四種算法的準(zhǔn)確率對比明顯，改進(jìn)后的算法計(jì)算出的用戶影響力排序結(jié)果均優(yōu)于現(xiàn)有的用戶影響力相關(guān)改進(jìn)算法，結(jié)果更加貼近現(xiàn)實(shí)，表明了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ìn)[J].計(jì)算機(jī)工程,2010, 36(22):291-292.

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

[4] 張金鵬,黃賢英.基于語義的文本相似度算法研究及應(yīng)用[D].重慶: 重慶理工大學(xué), 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] 曹姍姍,王沖.基于網(wǎng)頁鏈接與用戶反饋的PageRank算法改進(jìn)研究[J].計(jì)算機(jī)科學(xué),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] 李稚楹，楊武.基于網(wǎng)頁內(nèi)容和內(nèi)容反饋的網(wǎng)頁排序PageRank算法研究[D].重慶:重慶理工大學(xué),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.

責(zé)任編輯：時(shí) 凌

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.

國家自然科學(xué)基金項(xiàng)目(61201447).

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

1008-8423(2016)03-0256-05

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

TP301

A