資料挖掘十大算法翻譯——6PageRank

1 總覽

PageRank是由Sergey Brin和Larry Page在1998年4月的第七屆國際全球廣域網會議（WWW7）中提出的。它是一個使用超連結的搜尋排序算法。基于這個算法，他們穿在了Google搜素引擎，并且取得了巨大的成功。現在，每個搜尋引擎都有自己的基于超連結的排序算法。

PageRank産生一個網頁的靜态排行，也就是說PageRank離線的計算每個頁面，并且不依賴于查詢。通過使用大量的連結結構作為單個頁面的衡量标準，這個算法利用了Web的民主特性。PageRank的精髓就是通過把從x頁面到Y頁面的一個連結，作為x頁面給y頁面的投票。然而，PageRank不僅僅隻是單純的統計票數，或者一個頁面收到的連結數。它也分析透出票的頁面。如果投出票的頁面本身是重要的，那麼它會使得它投票的對象也是重要的。這就是在社交網絡中的“rank prestige(威望等階)”的思想。

2 算法

現在我們介紹PageRank公式。首先我們先成熟一些Web頁面的額内容。

頁面i的傳入連結接(in-link)：從其他頁面指向頁面i的超連結。通常而言，從同一個站點的連結不被考慮。

頁面i的對外連結接(out-link)：從頁面i指向其他頁面的超級連結。一般而言，不考慮同一個站點的連結。

下面這些基于rank prestige[86]的思想可以用來驅動PageRank算法:

1. 從一個頁面指向另一個頁面的超連結是一種暗含的權威的轉移。是以，頁面i收到的in-link越多，頁面i的prestige（威望）就越高

2. 指向頁面i的頁面也有他們自己的威望分數。擁有較高威望的頁面的投票比擁有較少威望的頁面的投票更重要。簡而言之，被重要的頁面指向的頁面也是重要的。

根據社交網絡中的威望等級，頁面i的重要性（這裡是i的PageRank分數）是由所有指向i的頁面所決定的。因為一個頁面可能指向其他的很多頁面，它的“威望”應夠由它指向的頁面來共享。

為了使用公式表達這個思想，我們把Web作為一個有向圖G=（V,E）這裡的V是頂點，也就是所有頁面的集合。E是圖的有向邊，也就是所有超連結。這裡讓所有頁面的總數設為n（n=|V|）第i個頁面的PageRank分數由下面的式子定義。

P(i)=∑(j,i)∈EP(j)Oj

這裡的Oj是頁面j的out-link的數量。數學上而言，我們有n個含有n個線性方程的未知數。我們可以用一個矩陣來代表所有的等式。設P是PageRank值的n維列限量，有如下表示：

P=（P(1),P(2),…,P(n)）T

設A是我們的圖的鄰接矩陣

Aij={1/Oi,0,if(i,j)∈Eotherwise

我們把n個等式的系統寫作

P=ATP

（3）

這是特征系統的特征值方程，這裡的解P是特征值為1的特征向量。由于這是一個循環的定義，我們使用一個疊代的算法來解決它。事實證明，如果條件滿足，1

是最大的特征值，并且PageRank向量P是主特征向量；

Power iteration(幂疊代)[30]是一個用來找到P的有名的數學方法。

然而問題在于由于Web圖不滿足條件，等式（3）是不重複的。事實上等式（3）也可以由Markov chain（馬爾科夫鍊）得到。然後從馬爾科夫鍊中得到的一些理論就可以被使用。在擴張Web圖使得它滿足條件之後，下面的等式就産生了：

P=(1−d)e+dATP

這裡的e是所有1’s的列向量。這樣，我們得到了每個頁面i的PageRank公式：

P(i)=(1−d)+d∑j=1nAjiP(j)

這是公式等加油在原始的PageRank論文中給出的公式：

P(i)=(1−d)+d∑(j,i)∈EP(j)Oj

參數d被稱為damping factor（尼阻因素），它的值介于0和1之間，在論文[10,52]使用的中d=0.85。

可以使用幂疊代的方法來計算PageRank的值，這樣會得到特征值為1的特征向量。這個算法非常簡單，可以從Fig4 表4中看到。我們可以從任何的指定的PageRank的初始值開始。如果結果變動不多，那麼疊代就救贖。在Fig4中，如果1-殘餘向量的範式小于預定的門檻值e那麼疊代就結束。

由于在Web搜尋中，我們感興趣的是網頁的排名，是以這個算法最終是否收斂我們是不關心的。這樣就可以使用更少的疊代。在[10]中，一個擁有322百萬，3.22億連結的資料庫，經過了52次疊代就達到了可以接受的效果。

3 PageRank的未來

自從在論文[10,61]中提出了PageRank算法，研究者就可以提出了很多的加強的模型，和替代模型，用于提高他的計算，增加暫時的次元[91]。Liu，Langville和Meyer的書中包括了一些PageRank的升讀分析和其他幾個基于連結的算法。