一. PageRank相關的定義

  1. term spam
    指頁面中隱藏大量與網頁內容無關的詞語, 只是為了在各種排序中排名優先. 因此, 僅僅依賴網頁中關鍵詞的統計來為網頁進行排序是容易被誤導的.
  2. spam farm
    指的是作弊者用很多的作弊網頁指向作弊者自己的某個核心網頁, 來提高作弊網頁的入度. 因此, 只依賴入度來為網頁也是排序不靠譜的.
  3. PageRank算法
    是Google創始人拉里·佩奇和謝爾蓋·布林於1997年構建早期的搜索系統原型時提出的鏈接分析算法. 該算法大大改進了當時網頁排序的可靠性.
    在接下去的討論中, PageRank代表了一個算法, 也可以理解成一個函數. 也就是說我們有一個網站A, 通過PageRank我們可以給出一個得分, 即score = PageRank(A) . 同時, PageRank函數給出的得分也常常被稱為PageRank值.

二. PageRank算法

1. PageRank算法核心思想

一個網頁的重要性和價值, 應該由其他網頁對它的評價決定, 而不是由網頁自身所含有的信息來決定.
因此, 算法把一個結點指向另外一個結點的有向邊視作是投票. 而且, 不是所有的投票都是等價值的, 來自那些得分較高的重要結點的投票價值更高.
PageRank算法是一個需要多輪迭代直到收斂的算法.

2. 基本的算法描述

1)在初始階段:網頁通過鏈接關係構建起Web圖,每個頁面設置相同的PageRank值,通過若干輪的計算,會得到每個頁面所獲得的最終PageRank值。隨着每一輪的計算進行,網頁當前的PageRank值會不斷得到更新。

2)在一輪中更新頁面PageRank得分的計算方法:在一輪更新頁面PageRank得分的計算中,每個頁面將其當前的PageRank值平均分配到本頁面包含的出鏈上,這樣每個鏈接即獲得了相應的得分。而每個頁面將所有指向本頁面的入鏈所傳入的得分求和,即可得到新的PageRank得分。當每個頁面都獲得了更新后的PageRank值,就完成了一輪PageRank計算。

3. 計算表達式

我們假設有如下一個網頁鏈接關係, 用鄰接鏈表的表示方式是
A: B, C, D
B: A, D
C: A
D: B, C

我們假設每個結點初始的得分值都是一樣的, 因此A=B=C=D=0.25, 我們用一個列向量v = (1/4, 1/4, 1/4, 1/4)’來表示所有結點目前的PageRank值.

我們根據鄰接鏈表的鏈接關係, 可以畫出如下的一個轉移矩陣M.
其中, 第一列代表A會把它的得分均分給B, C, D三個結點, 因此每個結點擁有0.33的權重. 第一行代表着A結點能夠從B, C結點得到的得分權重是0.5和1, 也就是說B會把自己一半的得分投給A, 而C會把自己所有的得分都投給A.

在第一輪迭代之後, 生成的v = M • v, 其中v代表v = (1/4, 1/4, 1/4, 1/4)’初始的列向量, v代表第一輪結束以後所有結點的得分列向量, 並且將作為算法下一輪的輸入.

4. 改進: 解決流量旋渦(終止點)問題

問題: 如果圖中存在着一個沒有出度, 但是有入度的結點. 那麼由於它不斷地吸收別的結點傳入的得分, 而不把得分投給別人, 最終會使得整個圖結構中, 最後其他結點的得分都趨於0 , 而這個結點趨近於1;
還有一種情況是, 稱作”採集器陷阱”的結構, 即有入度的一個子圖沒有出度. 進來的PageRank值都在這個子圖內循環和積累, 導致這個子圖如果被看成結點, 那麼它會有接近1的重要性.

我們使用一個叫抽稅法(taxation) 的技巧來改進PageRank.

v’ = βMv + (1-β)e/n

這裏, β可以取0.2左右的數值. e代表的是和v相同維度數的單位向量.
內涵: 把1 – β的得分作為抽稅, 平均分配給所有結點. 這樣能夠緩解流量旋渦的問題, 讓其他結點能獲得一定的得分.

5. 在搜索引擎中的實際使用

PageRank得出的重要性值是網頁排序中的一個重要屬性, 但是不是唯一的.
首先, 網頁至少要包含查詢中一個keyword, 一般要能夠排在前10的話, 必須包含所有的搜索詞項. 同時, 如果關鍵詞出現在網頁的標題, head meta標籤中, 那麼也會提高排名.

三. 計算問題

1. 一般情形下PageRank算法開銷分析

1)時間開銷: 算法主要時間開銷將會是每輪迭代中做Mv的矩陣乘法上, 這是O(V2)的時間開銷(V代表圖中結點個數, 下同), 再乘上算法需要迭代k輪完成收斂, 因此PageRank的時間開銷是O(kV2). 不過, 一般來說, 這個收斂需要次數k會是在10~100之間的數值, 不會特別大.

2)空間開銷: 算法最大的空間開銷來自於存儲整個M矩陣到內存中, 這是O(n2)的空間開銷. 因此如果假設有10^6個結點的圖, 需要的M矩陣大小是10^12, 按照int型4byte來存儲, 這相當於4TB的內存開銷, 這是任何單機都無法承受的空間開銷.

2. 對空間開銷的優化辦法

由於M矩陣的空間開銷過大, 必須考慮對其的優化存儲. 已知大多數情況下, M矩陣十分稀疏, 那麼我們可以使用鄰接鏈表或者類似形式, 只存儲非零元素的值.

比如, 在Python中, 可以通過構造字典數據類型來實現.

G = {1: [2, 3, 4], 2: [1, 4], 3: [1], 4: [2, 3]}
G[1] = [2, 3, 4]表示結點1和2, 3, 4是有一條有向邊.

實際運算中, 為了提高運算速度, 我們會以鄰接鏈表形式存儲兩個linkIn, linkOut兩個圖, 方便運算中的快速調用.

linkOut = {1: [2, 3, 4], 2: [1, 4], 3: [1], 4: [2, 3]}
linkIn = {1: [2,3], 2: [1,4], 3: [1,4], 4: [1, 2]}

那麼這種情形下, 空間開銷就是O(V+E)的, 因為鄰接鏈表存儲了所有的點和有向邊. 在稀疏圖中, O(V+E)往往遠小於O(V^2).

3. 對時間開銷的優化辦法

為了實現從O(V^2)下降到O(V+E)的優化, 我們需要重新定義一般PageRank中的Mv矩陣乘法操作.

我們知道, Mv乘法實際上完成的目的是算出v*列向量, 也就是每個結點新的PageRank值. 按照之前所述, 我們有如下觀察:

Observation : 結點的新PageRank值 = Σ (來源結點的PageRank值 • 本結點所分享到的權重)

因此, 做常規矩陣乘法中遍歷所有元素的做法是非常浪費的行為. 我們可以直接利用linkIn字典找到指向本結點的所有結點, 並用linkOut字典獲取本結點所分享到的權重值.

v* += 1/len(linkOut[fromNode]) * v[fromNode]
說明: v*是本結點新的PageRank值, 1/len(linkOut[fromNode])代表獲取本結點所分享到的權重值, v[fromNode]獲取來源結點的PageRank值.

由此, 我們的時間開銷變成了O(V + E), 在稀疏圖中, 這樣的時間開銷遠比O(V^2)小.

備註: 項目代碼https://github.com/imcheney/NetworkMining/blob/master/core/MyPageRank.py