這個學期選了數據挖掘的課程，期末要做一個關於鏈接分析算法的報告，這是PR算法的小結。
PageRank
這個學期選了數據挖掘的課程，期末要做一個關於鏈接分析算法的報告，這是PR算法的小結。
算法
PR算法基於等級權威的思想，及不僅考慮指向該網頁的鏈接數，同時也考慮指向該網頁網站的重要程度。
PR算法是一種靜態的網頁評級方法，因為它為每個網頁離線計算PR值，與查詢內容無關。計算出的PR值即可作為網頁排序的依據。
從權威的時角來説，PR值應體現以下的兩點：
- 從一個網頁指向另一個網頁的鏈接是一種對目標網站權威性的隱含認可，也就是説，指向一個網頁的連接數越多，該網頁的PR值也就越高；
- 指向某個網頁w的網頁本身也具有PR值。在現實生活中，我們知道被一個高權威的人認可的事比被一個低權威的人認可的更具有可信度。因此，如果一個網頁被其他具有高PR值的網頁認可，那麼該網頁的PR值也應該較高。
根據以上的思想，我們可以推導出計算PR值的公式。將網頁之間的鏈接關係看作一個有向圖G(V, E)，其中V是所有節點（即網頁）的集合，E是所有有向邊（即超鏈接）的集合。假設 |V|=n，PR值的定義如下:
\[P(i) = \sum\limits_{(j,i)\in E} \frac{P(j)}{O_j} \]
其中，\(O_j\)為網頁的鏈出鏈接數目。根據線性代數的知識，以上的式子可以寫成矩陣的形式。
不妨用P表示PR值的列向量，令A為圖G的鄰接矩陣，有：
\[A = \left \{ \begin{array}{c} \frac{1}{O_i} , (i,j)\in E \\ 0, \text{其他} \end{array} \right. \]
於是可以寫出如下的形式：
\[P = A^T P \]
顯然，P是特徵值1對應的特徵向量。然而在Web圖中上訴的等式並不一定有效。為了改進這個等式，這裏用馬爾科夫鏈來重新推導這個等式。
在馬爾科夫鏈模型中，每張網頁都被認為是一個狀態，每個狀態有一定概率向另一個狀態轉移，也就是説將網頁瀏覽看作一個隨機過程。它將用户隨機瀏覽網頁的行為看作馬爾科夫鏈中一個狀態向另一個狀態的轉移
\[\left[ \begin{matrix} A_{11} & A_{12} & \cdots & A_{1n} \\ A_{21} & A_{22} & \cdots & A_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ A_{n1} & A_{n2} & \cdots & A_{nn} \\ \end{matrix} \right] \]
其中，\(A_{ij}\)為正在瀏覽網頁i的用户瀏覽網頁j的概率。可見這裏矩陣A的定義與前面的相同。
如果A每一行元素的和為1，那麼就可以稱A是一個馬爾科夫鏈的隨機轉移矩陣。但是這個條件在很多情況下並不成立，因為很多網頁並沒有鏈出鏈接，那麼在A對應行上的元素全為0。首先不妨假設A是一個隨機轉移矩陣，那麼在經過k次狀態轉移後的概率分佈為：
\[p_k = A^Tp_{k-1} \]
根據隨機過程的知識，如果矩陣A是不可約的且是非週期的，那麼該馬爾科夫鏈會收斂到一個概率分佈，且這個概率分佈是唯一的。即
\[\lim_{k \to \infty} p_k = \pi \]
\(\pi\)體現了一個用户瀏覽某個網頁的長期概率，這個概率越高説明該網頁的權威越高。於是在PageRank算法中，我們可以將此處的\(\pi\)作為PR值的向量P，於是我們又得到了
\[P = A^T P \]
但是在現實中，Web中的網頁並不能滿足以上的條件。
首先，由於很多網頁沒有鏈出鏈接，A常常不是一個隨機轉移矩陣。為了解決這個問題，我們可以將矩陣A中全0行的元素替換為\(1/n\)，即將沒有鏈出鏈接的網頁鏈接到其他所有網頁。記轉換後的矩陣為\(\overline{A}\)，此時的矩陣\(\overline{A}\)就是一個隨機轉移矩陣。
第二，矩陣\(\overline{A}\)常常不是不可約的，這就意味這圖G不是強連通圖。實際上，並不能保證Web中的任意兩個網頁之間可以鏈接起來。
最後，\(\overline{A}\)不是非週期的。這是因為在網頁中常有經過幾次鏈接後回到原網頁的情況。在馬爾科夫鏈中，這就意味着從狀態i開始經過若干次轉移後總是回到狀態i。顯然這不是我們想要的效果。
為了解決以上的兩個問題，可以給每個網頁增加一個以轉移概率\(1-d\)指向所有網頁的鏈接。也就是説，在用户瀏覽一個網頁時，他隨機選擇一個鏈出鏈接進行瀏覽的概率是d，而不點擊頁面中的鏈接跳到另一個網頁繼續瀏覽的概論是1-d。這樣一來，Web圖就變為強連通的。且從狀態i出發回到狀態i就有了各種不同的路徑，也就是説該馬爾科夫鏈成為了非週期的。
此時，PR值的計算公式為
\[P = ((1-d)\frac{E}{n} + d \overline{A}^T)P \]
其中E為元素全為1的n階方陣，稱d為衰減係數，取值在0到1之間。
現實世界中的網頁有很多，將PR值計算至收斂需要很大的代價。實際上我們只關注網頁的排序情況，只需要迭代到一個可以接受的程度即可。
優缺點
PageRank算法的一大優點是PR值都被離線計算並保存下來，而不是在用户進行搜索時再進行計算，可以提升查詢的效率。
另一個優點是它有一定的反作弊能力。一個網頁的擁有者很難將指向自己網頁的鏈接添加到其他重要網頁中。
但是魔高一尺道高一丈，還是有辦法認為提升PR值。在一些重要網頁的評論區中附上一些“殭屍”網頁的地址，這些“殭屍”網頁中有指向目標網頁的鏈接，這樣就能達到提升PR值的效果。
另一個缺點在於該算法沒有考慮時間，往往一個網頁存在的時間越久，指向它的鏈接就越多。也就是説PR值的計算對舊的網頁更加有利，使得一些新的高質量網頁在搜索中不能獲得高的排名。
由於PageRank算法非查詢相關的特性，查詢結果有可能發生偏離。
