QRCode

PageRank網頁排名演算法

PageRank

葉鎮源
2012年10月
圖書館學與資訊科學大辭典

名詞解釋:

PageRank是一種計算網頁名次排行的演算法,由Google的創辦人Larry PageSergey Brin1996年在史丹佛大學(Stanford University)就讀博士班時研發,也是Google搜尋引擎用來決定網頁重要性、據此將最相關且可靠度高的網頁呈現在搜尋結果頂端的核心技術。

PageRank源於文獻引用(citation)的計數法則,其根本概念是將網頁的超連結(hyperlink)當作評估網頁重要程度的投票機制,換句話說,當網頁A有一正向連結(forward link)連到網頁B時,表示網頁A投票給網頁B。由此可知,一個網頁的重要程度是依其所得到的票數來決定:若某網頁擁有的反向連結(backlink)數目越多,即投票給它的網頁越多,則該網頁的重要性就越高。但是,單單考慮網頁的反向連結數目是不夠的。舉例來說,某個網頁同時擁有來自Yahoo首頁和其他名不見經傳的網站連過來的連結,此時Yahoo的投票較有價值,原因是一般認為Yahoo首頁的重要度高於其他網頁。

基於上述說明,若網頁T1, T2, …, Tn是具有正向連結至網頁A的網頁集合,APageRankPR(A)計算如下:

Eq. (1)

PR(Ti)TiPageRank值;C(Ti)Ti的正向連結數目。PR(Ti)/C(Ti)說明ATi得到的PageRank值與其正向連結數目成反比,也就是說,TiPageRank值是平均分配給所有正向連結所指向的網頁,並非只獨厚網頁A。實數d介於01之間,稱為阻尼係數(damping factor),通常設定成0.85

理論上,PageRank屬於隨機漫步(random walk)的使用者瀏覽行為模型。假想有一個使用者正在隨機瀏覽某個網頁,且經由網頁上的正向連結不斷擴展開啟其他網頁,而在某時間點隨機跳到另一個新的網頁,重複前述相同的動作。此時,網頁的PageRank值即是假想使用者瀏覽到某個網頁的機率。Eq. (1)中的(1d)則是該隨機瀏覽者在觀看某個網頁後,決定不依循其正向連結連至其他網頁,而是隨機開啟任意網頁進行瀏覽的可能性。

一般來說,網頁PageRank值的計算是由power method經過遞迴的方式求得。若x是一n´1維的向量,x(k)代表所有n個網頁在第k時間點的PageRank值,且所有網頁的PageRank值之和等於n,換句話說,[1]1´n x = nPageRank的定義如下:


Eq. (2)

其中E是一n´n維的矩陣,其所有元素值皆為1/n,即E = [1/n]n´nR是一n´n維的矩陣,其元素值rij如下定義:


Eq. (3)

到目前為止皆假設所有網頁至少有一個正向連結,也就是說C(i)不等於0。然而現實世界中存在某些網頁沒有任何正向連結連至其他網頁,此時假設那些網頁皆有一假想的正向連結連至其他所有網頁,Eq. (3)調整如下:


Eq. (4)

Eq. (2)可知,當n的值越大時,PageRank的運算量也相對地提高。目前沒有人確切地知道全球資訊網的網頁數量,但是根據Google公布的資料顯示,全球資訊網的網頁數量(即n的值)已遠超過1,000,000,000,000。若用此數字推算,PageRank的計算相當於求解維度為1012´1012之矩陣的特徵向量(eigenvector)。無疑地,這將是全世界最大的矩陣計算。

最後,值得一提的是,Eq. (2)中的E可進一步表示成下式:


Eq. (5)

v是一n´1維的向量,v = [1/n]n´1。此時,向量v代表著某個使用者對於所有n個網頁的喜好程度皆相同。當按照不同喜好程度調整v中元素的值時,PageRank可呈現出個人化網頁排名的效果。因此,v又稱作個人化向量(personalization vector)。

參考資料:

Brin, S., & Page, L. (1998). The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems, 30(1-7), 107-117.

PageRank網頁排名演算法

PageRank

PageRank 進行詞彙精確檢索結果
出處/學術領域 英文詞彙 中文詞彙
PageRank網頁排名演算法 進行詞彙精確檢索結果
出處/學術領域 中文詞彙 英文詞彙

引用網址: