:::
PageRank網頁排名演算法 - 教育百科
| P | |
| a | |
| g | |
| e | |
| R | |
| a | |
| n | |
| k | |
| 網 | |
| 頁 | |
| 排 | |
| 名 | |
| 演 | |
| 算 | |
| 法 |
國家教育研究院辭書
基本資料
| 英文： | PageRank |
| 作者： | 葉鎮源 |
| 日期： | 2012年10月 |
| 出處： | 圖書館學與資訊科學大辭典 |
辭書內容
|
名詞解釋： PageRank是一種計算網頁名次排行的演算法，由Google的創辦人Larry Page和Sergey Brin於1996年在史丹佛大學（Stanford University）就讀博士班時研發，也是Google搜尋引擎用來決定網頁重要性、據此將最相關且可靠度高的網頁呈現在搜尋結果頂端的核心技術。PageRank源於文獻引用（citation）的計數法則，其根本概念是將網頁的超連結（hyperlink）當作評估網頁重要程度的投票機制，換句話說，當網頁A有一正向連結（forward link）連到網頁B時，表示網頁A投票給網頁B。由此可知，一個網頁的重要程度是依其所得到的票數來決定：若某網頁擁有的反向連結（backlink）數目越多，即投票給它的網頁越多，則該網頁的重要性就越高。但是，單單考慮網頁的反向連結數目是不夠的。舉例來說，某個網頁同時擁有來自Yahoo首頁和其他名不見經傳的網站連過來的連結，此時Yahoo的投票較有價值，原因是一般認為Yahoo首頁的重要度高於其他網頁。基於上述說明，若網頁T1, T2, …, Tn是具有正向連結至網頁A的網頁集合，A的PageRank值PR(A)計算如下： PR(Ti)是Ti的PageRank值；C(Ti)是Ti的正向連結數目。PR(Ti)/C(Ti)說明A從Ti得到的PageRank值與其正向連結數目成反比，也就是說，Ti的PageRank值是平均分配給所有正向連結所指向的網頁，並非只獨厚網頁A。實數d介於0和1之間，稱為阻尼係數（damping factor），通常設定成0.85。理論上，PageRank屬於隨機漫步（random walk）的使用者瀏覽行為模型。假想有一個使用者正在隨機瀏覽某個網頁，且經由網頁上的正向連結不斷擴展開啟其他網頁，而在某時間點隨機跳到另一個新的網頁，重複前述相同的動作。此時，網頁的PageRank值即是假想使用者瀏覽到某個網頁的機率。Eq. (1)中的(1−d)則是該隨機瀏覽者在觀看某個網頁後，決定不依循其正向連結連至其他網頁，而是隨機開啟任意網頁進行瀏覽的可能性。一般來說，網頁PageRank值的計算是由power method經過遞迴的方式求得。若x是一n´1維的向量，x(k)代表所有n個網頁在第k時間點的PageRank值，且所有網頁的PageRank值之和等於n，換句話說，[1]1´n x = n，PageRank的定義如下： 其中E是一n´n維的矩陣，其所有元素值皆為1/n，即E = [1/n]n´n；R是一n´n維的矩陣，其元素值rij如下定義：到目前為止皆假設所有網頁至少有一個正向連結，也就是說C(i)不等於0。然而現實世界中存在某些網頁沒有任何正向連結連至其他網頁，此時假設那些網頁皆有一假想的正向連結連至其他所有網頁，Eq. (3)調整如下： 由Eq. (2)可知，當n的值越大時，PageRank的運算量也相對地提高。目前沒有人確切地知道全球資訊網的網頁數量，但是根據Google公布的資料顯示，全球資訊網的網頁數量（即n的值）已遠超過1,000,000,000,000。若用此數字推算，PageRank的計算相當於求解維度為1012´1012之矩陣的特徵向量（eigenvector）。無疑地，這將是全世界最大的矩陣計算。最後，值得一提的是，Eq. (2)中的E可進一步表示成下式：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. |
|
|
參考資料： 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網頁排名演算法 |
| 授權資訊： | 資料採「 創用CC-姓名標示- 禁止改作 臺灣3.0版授權條款」釋出 |
貓頭鷹博士