基于PageRank算法的網(wǎng)絡關鍵節(jié)點查找

楊蓉蓉++王勤穎++劉鳳鳴

摘要：本文基于新浪微博平臺，以天貓雙十一狂歡夜為主題收集數(shù)據(jù)，根據(jù)用戶之間的轉(zhuǎn)發(fā)關系構建社交網(wǎng)絡，然后利用PageRank算法找出網(wǎng)絡中的關鍵節(jié)點。

關鍵詞：PageRank；層次分析法；關鍵節(jié)點

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2017）04-0226-02

1 概述

2016年11月10日晚20：30，2016雙十一天貓晚會落戶于深圳大運中心體育館舉行，由浙江衛(wèi)視承辦，張靚穎、蔡依林、Rain、TFBPYS等大咖紛紛加入。綜藝內(nèi)容、明星游戲、移動購物三位一體，用全新體驗為億萬觀眾上演了一場邊看邊剁手的互動娛樂盛宴。

數(shù)據(jù)顯示長達4小時的雙11直播晚會，收視率高達23%。根據(jù)阿里方面透露，雙11晚會硬廣收入利潤將以紅包的形式回饋消費者。此外，阿里巴巴集團旗下大文娛版塊，包括合一集團（優(yōu)酷土豆）、天貓魔盒、蝦米音樂、UC瀏覽器、天貓客戶端等平臺，都將組成2016雙11晚會的聯(lián)動直播矩陣[1]。

微博用戶“天貓雙11狂歡夜”是天貓雙11全球狂歡夜晚會的官方微博，該博在11月10日晚發(fā)布大量微博直播晚會現(xiàn)場，包括晚會明星陣容和節(jié)目抽獎等。許多新浪微博用戶對官微發(fā)布的微博進行轉(zhuǎn)發(fā)，同時眾多微博大V用戶和普通用戶展開話題討論。

本文收集2016年11月10日至11日與“天貓雙11狂歡夜”話題相關的微博數(shù)據(jù)，根據(jù)用戶之間的轉(zhuǎn)發(fā)關系構建社交網(wǎng)絡，使用Gephi軟件繪制網(wǎng)絡結構圖，然后使用PageRank算法計算每個節(jié)點的PR值，從而找出其中的關鍵節(jié)點。

2 國內(nèi)外研究現(xiàn)狀

PageRank算法最早是由Sergey Brin 和 Larry Page 在《The Anatomy of a Large-Scale Hypertextual Web Search Engine》一文中提出的[2]，它借鑒引文分析的思想，建立在隨即沖浪者模型之上，對網(wǎng)頁進行評價，為每個網(wǎng)頁賦予一個衡量其重要性的PR值，并最后應用于檢索結果的排序。

PageRank的基本思想主要來自文獻引文分析，一篇學術論文的重要性及質(zhì)量可以通過其他學術論文對其進行引用的數(shù)量來衡量，被引用得越多，重要性越高。PageRank應用傳統(tǒng)的文獻引文分析思想，提出一個假設，認為網(wǎng)頁的重要性和質(zhì)量可以通過其他網(wǎng)頁對其鏈接的數(shù)量來衡量。

PageRank算法通過網(wǎng)頁之間的鏈接來評價網(wǎng)頁的重要性，能夠在一定程度上避免和減少人為因素對排序結果的影響。該算法采用離線計算方式，與查詢無關，因此響應速度較高。PageRank采用均分策略，一個網(wǎng)頁的引用越多，被引用網(wǎng)頁所獲得的PR值就越少[3]。因此，算法可以有效避免為了提高搜索排名而故意使用鏈接的行為。

PageRank算法在Google搜索引擎獲得成功運用，足以證明該算法的高效性和有效性，但是算法也存在一些缺點，會導致主題漂移問題[4]，而且偏重舊網(wǎng)頁，舊的頁面等級會比新網(wǎng)頁要高，但事實上很多新網(wǎng)頁的重要性是遠高于舊網(wǎng)頁的，同時也忽視了用戶的個性化問題，所以算法仍有很大的改進余地。

算法的改進可以歸納為兩類[5]，一類是基于算法理論的改進，轉(zhuǎn)化為求解矩陣特征向量的問題，比如Power算法、GMRES算法和Power Amoldi算法等；另一類是針對互聯(lián)網(wǎng)實際應用的特點而進行的改進，比如針對解決主題漂移問題提出的Topic Sensitive PageRank算法，針對時間問題戚春華等人提出了具有時間反饋的PageRank改進算法。

3 PageRank算法

對于某個互聯(lián)網(wǎng)網(wǎng)頁A來說，該網(wǎng)頁PageRank的計算基于以下兩個基本假設：（1）數(shù)量假設：在Web圖模型中，如果一個頁面節(jié)點接收到的其他網(wǎng)頁指向的入鏈數(shù)量越多，那么這個頁面越重要。（2）質(zhì)量假設：指向頁面A的入鏈質(zhì)量不同，質(zhì)量高的頁面會通過鏈接向其他頁面?zhèn)鬟f更多的權重。所以越是質(zhì)量高的頁面指向頁面A，則頁面A越重要。

根據(jù)以上兩個假設，一個頁面的PageRank是由其他頁面的PageRank計算得到的，如果給每個頁面一個隨機的PageRank值（非0），通過迭代計算來不斷地更新每個頁面節(jié)點的PageRank值，直到PageRank值穩(wěn)定為止，我們就得到所有節(jié)點的PageRank值。PageRank的計算公式為：

[PRi=1-dN+dpjPRjLpj]

其中，PRi是網(wǎng)頁i的PageRank值，PRj是網(wǎng)頁j的PageRank值，pj表示研究的網(wǎng)頁，N為頁面總數(shù)，L（pj）是pj網(wǎng)頁鏈出頁面的數(shù)量，d為阻尼系數(shù)，表示用戶隨機跳轉(zhuǎn)到一個頁面的概率，通常取0.85，能夠避免PR值沉淀現(xiàn)象。

4 PageRank算法應用

數(shù)據(jù)內(nèi)容包括微博內(nèi)容、創(chuàng)建時間、微博來源、微博地址、用戶昵稱、粉絲數(shù)、性別、地域、認證類型、是否轉(zhuǎn)發(fā)、原微博內(nèi)容、原微博來源、原微博創(chuàng)建時間和原微博用戶昵稱共14項。由于我們獲取的數(shù)據(jù)中沒有關注、點贊和收藏的數(shù)據(jù)，所以無法對UserRank算法進行仿真實驗，因此，我們選擇根據(jù)用戶之間的轉(zhuǎn)發(fā)關系，構建用戶社交網(wǎng)絡。用戶1發(fā)布一條微博，用戶2轉(zhuǎn)發(fā)該微博，那么就有一條由用戶2指向用戶1的有向邊，基于該原則根據(jù)每條數(shù)據(jù)構建節(jié)點和有向邊，從而形成轉(zhuǎn)發(fā)網(wǎng)絡。然后，依據(jù)該網(wǎng)絡結構，以0.85阻尼系數(shù)運行PageRank算法，根據(jù)每個節(jié)點的PR值找出其中的關鍵節(jié)點。

由于雙十一狂歡夜晚會時間為10日晚八點半，所以對我們獲取的關于“天貓雙十一狂歡夜”的所有數(shù)據(jù)進行數(shù)據(jù)清理，只留下2016年11月10日和11日的微博數(shù)據(jù)，然后從中篩選出發(fā)布人為普通用戶以及微博認證類型為名人認證、媒體認證和企業(yè)認證的數(shù)據(jù)。有些用戶盡管發(fā)布了一條微博，但是并沒有其他用戶對該微博進行轉(zhuǎn)發(fā)，基于轉(zhuǎn)發(fā)關系構建網(wǎng)絡時，該用戶會成為離群點，所以刪除該類數(shù)據(jù)。對于一個用戶發(fā)布的不同微博，不同的轉(zhuǎn)發(fā)用戶對每條微博的轉(zhuǎn)發(fā)都考慮在內(nèi)，如果用戶2對用戶1發(fā)布對兩條微博都進行了轉(zhuǎn)發(fā)，那么只有一條由用戶2指向用戶1對有向邊。根據(jù)上述條件，對數(shù)據(jù)進行清理之后最后有效數(shù)據(jù)共計1302條?；谶@1302條數(shù)據(jù)，逐條查找，在Gephi中構建節(jié)點和有向邊，形成網(wǎng)絡如圖1所示。其中，藍色節(jié)點為普通用戶，紅色節(jié)點為名人認證用戶，黃色節(jié)點為企業(yè)認證用戶，綠色節(jié)點為媒體認證用戶。

為了直觀觀察，采用Fruchterman Reingold布局模式改變網(wǎng)絡視圖如圖2所示。在Gephi軟件中基于該網(wǎng)絡運行PageRank算法，計算每個節(jié)點的PR值。

5 結論

在Gephi中構建的網(wǎng)絡共有268個節(jié)點259條邊，每個節(jié)點的PR值按照降序排列，前15個節(jié)點的PR值如圖3所示。取PR值為前5%的用戶作為關鍵用戶，共計13名用戶。那么在“天貓雙十一狂歡夜”話題中，關鍵用戶為天貓雙11狂歡夜晚會官微、娛樂潮流情報、搶紅包狂歡、天貓、魷魚子、KatyPerry、優(yōu)酷、香港爆料王、Astro12-girls、蘇寧易購、老高電商圈子、微博電視和7公主的日常。

圖3 PR值最高的15個節(jié)點的PR值

參考文獻：

[1] 2016雙十一天貓晚會11月10日晚20：30直播 浙江衛(wèi)視承辦

http：//www.tianqi.com/news/160607.html

[2] 黃德才，戚華春.PageRank算法研究[J].計算機工程，2006（2）：145-162.

[3] 吳淑燕，徐濤.PageRank算法的原理簡介[J].圖書情報工作，2003（2）：55-60.