淺析PageRank算法
作者：張洋
很早就對 Google 的 PageRank 算法很感興趣，但一直沒有深究，只有個輪廓性的概念。前幾天趁團隊 outing 的機會，在動車上看了一些相關的資料（PS：在動車上看看書真是一種享受），趁熱打鐵，將所看的東西整理成此文。
本文首先會討論搜索引擎的核心難題，同時討論早期搜索引擎關于結果頁面重要性評價算法的困境，借此引出 PageRank 產生的背景。第二部分會詳細討論 PageRank 的思想來源、基礎框架，并結合互聯網頁面拓撲結構討論 PageRank 處理 Dead Ends 及平滑化的方法。第三部分討論 Topic-Sensitive PageRank 算法。最后將討論對 PageRank 的 Spam 攻擊方法：Spam Farm 以及搜索引擎對 Spam Farm 的防御。
搜索引擎的難題
Google 早已成為全球最成功的互聯網搜索引擎，但這個當前的搜索引擎巨無霸卻不是最早的互聯網搜索引擎，在 Google 出現之前，曾出現過許多通用或專業領域搜索引擎。Google 最終能擊敗所有競爭對手，很大程度上是因為它解決了困擾前輩們的最大難題：對搜索結果按重要性排序。而解決這個問題的算法就是 PageRank。毫不夸張的說，是 PageRank 算法成就了 Google 今天的低位。要理解為什么解決這個難題如此重要，我們先來看一下搜索引擎的核心框架。
搜索引擎的核心框架
雖然搜索引擎已經發展了很多年，但是其核心卻沒有太大變化。從本質上說，搜索引擎是一個資料檢索系統，搜索引擎擁有一個資料庫（具體到這里就是 互聯網頁面），用戶提交一個檢索條件（例如關鍵詞），搜索引擎返回符合查詢條件的資料列表。理論上檢索條件可以非常復雜，為了簡單起見，我們不妨設檢索條 件是一至多個以空格分隔的詞，而其表達的語義是同時含有這些詞的資料（等價于布爾代數的邏輯與）。例如，提交“張洋博客”，意思就是“給我既含有‘張洋’ 又含有‘博客’詞語的頁面”，以下是 Google 對這條關鍵詞的搜索結果：
可以看到我的博客出現在第五條，而第四條是我之前在博客園的博客。
當然，實際上現在的搜索引擎都是有分詞機制的，例如如果以“張洋的博客”為關鍵詞，搜索引擎會自動將其分解為“張洋的博客”三個詞，而“的”作為停止詞（Stop Word）會被過濾掉。關于分詞及詞權評價算法（如 TF-IDF 算法）是一個很大的話題，這里就不展開討論了，為了簡單此處可以將搜索引擎想象為一個只會機械匹配詞語的檢索系統。
這樣看來，建立一個搜索引擎的核心問題就是兩個：1、建立資料庫；2、建立一種數據結構，可以根據關鍵詞找到含有這個詞的頁面。
第一個問題一般是通過一種叫爬蟲（Spider） 的特殊程序實現的（當然，專業領域搜索引擎例如某個學術會議的論文檢索系統可能直接從數據庫建立資料庫），簡單來說，爬蟲就是從一個頁面出發（例如新浪首 頁），通過 HTTP 協議通信獲取這個頁面的所有內容，把這個頁面 url 和內容記錄下來（記錄到資料庫），然后分析頁面中的鏈接，再去分別獲取這些鏈接鏈向頁面的內容，記錄到資料庫后再分析這個頁面的鏈接……重復這個過程，就 可以將整個互聯網的頁面全部獲取下來（當然這是理想情況，要求整個 Web 是一個強連通（Strongly Connected），并且所有頁面的 robots 協議允許爬蟲抓取頁面，為了簡單，我們仍然假設 Web 是一個強連通圖，且不考慮 robots 協議）。抽象來看，可以將資料庫看做一個巨大的 key-value 結構，key 是頁面 url，value 是頁面內容。
第二個問題是通過一種叫倒排索引（inverted index）的數據結構實現的，抽象來說倒排索引也是一組 key-value 結構，key 是關鍵詞，value 是一個頁面編號集合（假設資料庫中每個頁面有唯一編號），表示這些頁面含有這個關鍵詞。本文不詳細討論倒排索引的建立方法。
有了上面的分析，就可以簡要說明搜索引擎的核心動作了：搜索引擎獲取“張洋博客”查詢條件，將其分為“張洋”和“博客”兩個詞。然后分別從倒排 索引中找到“張洋”所對應的集合，假設是{1， 3， 6， 8， 11， 15}；“博客”對應的集合是{1， 6， 10， 11， 12， 17， 20， 22}，將兩個集合做交運算（intersection），結果是{1， 6， 11}。最后，從資料庫中找出1、6、11對應的頁面返回給用戶就可以了。
搜索引擎的核心難題
上面闡述了一個非常簡單的搜索引擎工作框架，雖然現代搜索引擎的具體細節原理要復雜的多，但其本質卻與這個簡單的模型并無二異。實際 Google 在上述兩點上相比其前輩并無高明之處。其最大的成功是解決了第三個、也是最為困難的問題：如何對查詢結果排序。
我們知道 Web 頁面數量非常巨大，所以一個檢索的結果條目數量也非常多，例如上面“張洋博客”的檢索返回了超過 260 萬條結果。用戶不可能從如此眾多的結果中一一查找對自己有用的信息，所以，一個好的搜索引擎必須想辦法將“質量”較高的頁面排在前面。其實直觀上也可以感 覺出，在使用搜索引擎時，我們并不太關心頁面是否夠全（上百萬的結果，全不全有什么區別？而且實際上搜索引擎都是取 top，并不會真的返回全部結果。），而很關心前一兩頁是否都是質量較高的頁面，是否能滿足我們的實際需求。
因此，對搜索結果按重要性合理的排序就成為搜索引擎的最大核心，也是 Google 最終成功的突破點。
早期搜索引擎的做法
不評價
這個看起來可能有點搞笑，但實際上早期很多搜索引擎（甚至包括現在的很多專業領域搜索引擎）根本不評價結果重要性，而是直接按照某自然順序（例 如時間順序或編號順序）返回結果。這在結果集比較少的情況下還說得過去，但是一旦結果集變大，用戶叫苦不迭，試想讓你從幾萬條質量參差不齊的頁面中尋找需 要的內容，簡直就是一場災難，這也注定這種方法不可能用于現代的通用搜索引擎。
基于檢索詞的評價
后來，一些搜索引擎引入了基于檢索關鍵詞去評價搜索結構重要性的方法，實際上，這類方法如 TF-IDF 算法在現代搜索引擎中仍在使用，但其已經不是評價質量的唯一指標。完整描述 TF-IDF 比較繁瑣，本文這里用一種更簡單的抽象模型描述這種方法。
基于檢索詞評價的思想非常樸素：和檢索詞匹配度越高的頁面重要性越高。“匹配度”就是要定義的具體度量。一個最直接的想法是關鍵詞出現次數越多 的頁面匹配度越高。還是搜索“張洋博客”的例子：假設A頁面出現“張洋”5次，“博客”10次；B頁面出現“張洋”2次，“博客”8次。于是A頁面的匹配 度為 5 + 10 = 15，B頁面為 2 + 8 = 10，于是認為A頁面的重要性高于B頁面。很多朋友可能意識到這里的不合理性：內容較長的網頁往往更可能比內容較短的網頁關鍵詞出現的次數多。因此，我們 可以修改一下算法，用關鍵詞出現次數除以頁面總詞數，也就是通過關鍵詞占比作為匹配度，這樣可以克服上面提到的不合理。
早期一些搜索引擎確實是基于類似的算法評價網頁重要性的。這種評價算法看似依據充分、實現直觀簡單，但卻非常容易受到一種叫“Term Spam”的攻擊。
Term Spam
其實從搜索引擎出現的那天起，spammer 和搜索引擎反作弊的斗法就沒有停止過。Spammer 是這樣一群人——試圖通過搜索引擎算法的漏洞來提高目標頁面（通常是一些廣告頁面或垃圾頁面）的重要性，使目標頁面在搜索結果中排名靠前。
現在假設 Google 單純使用關鍵詞占比評價頁面重要性，而我想讓我的博客在搜索結果中排名更靠前（最好排第一）。那么我可以這么做：在頁面中加入一個隱藏的 html 元素（例如一個 div），然后其內容是“張洋”重復一萬次。這樣，搜索引擎在計算“張洋博客”的搜索結果時，我的博客關鍵詞占比就會非常大，從而做到排名靠前的效果。更 進一步，我甚至可以干擾別的關鍵詞搜索結果，例如我知道現在歐洲杯很火熱，我就在我博客的隱藏 div 里加一萬個“歐洲杯”，當有用戶搜索歐洲杯時，我的博客就能出現在搜索結果較靠前的位置。這種行為就叫做“Term Spam”。
早期搜索引擎深受這種作弊方法的困擾，加之基于關鍵詞的評價算法本身也不甚合理，因此經常是搜出一堆質量低下的結果，用戶體驗大大打了折扣。而 Google 正是在這種背景下，提出了 PageRank 算法，并申請了專利保護。此舉充分保護了當時相對弱小 Google，也使得 Google 一舉成為全球首屈一指的搜索引擎。
PageRank 算法
上文已經說到，PageRank 的作用是評價網頁的重要性，以此作為搜索結果的排序重要依據之一。實際中，為了抵御 spam，各個搜索引擎的具體排名算法是保密的，PageRank 的具體計算方法也不盡相同，本節介紹一種最簡單的基于頁面鏈接屬性的 PageRank 算法。這個算法雖然簡單，卻能揭示 PageRank 的本質，實際上目前各大搜索引擎在計算 PageRank 時鏈接屬性確實是重要度量指標之一。
簡單 PageRank 計算
首先，我們將 Web 做如下抽象：1、將每個網頁抽象成一個節點；2、如果一個頁面A有鏈接直接鏈向B，則存在一條有向邊從A到B（多個相同鏈接不重復計算邊）。因此，整個 Web 被抽象為一張有向圖。
現在假設世界上只有四張網頁：A、B、C、D，其抽象結構如下圖：
顯然這個圖是強連通的（從任一節點出發都可以到達另外任何一個節點）。
然后需要用一種合適的數據結構表示頁面間的連接關系。其實，PageRank 算法是基于這樣一種背景思想：被用戶訪問越多的網頁更可能質量越高，而用戶在瀏覽網頁時主要通過超鏈接進行頁面跳轉，因此我們需要通過分析超鏈接組成的拓 撲結構來推算每個網頁被訪問頻率的高低。最簡單的，我們可以假設當一個用戶停留在某頁面時，跳轉到頁面上每個被鏈頁面的概率是相同的。例如，上圖中A頁面 鏈向B、C、D，所以一個用戶從A跳轉到B、C、D的概率各為1/3。設一共有N個網頁，則可以組織這樣一個N維矩陣：其中i行j列的值表示用戶從頁面j 轉到頁面i的概率。這樣一個矩陣叫做轉移矩陣（Transition Matrix）。下面的轉移矩陣M對應上圖：
然后，設初始時每個頁面的 rank 值為1/N，這里就是1/4。按A-D順序將頁面 rank 為向量v：
注意，M第一行分別是A、B、C和D轉移到頁面A的概率，而v的第一列分別是A、B、C和D當前的 rank，因此用M的第一行乘以v的第一列，所得結果就是頁面A最新 rank 的合理估計，同理，Mv 的結果就分別代表A、B、C、D新 rank：
然后用M再乘以這個新的 rank 向量，又會產生一個更新的 rank 向量。迭代這個過程，可以證明v最終會收斂，即v約等于 Mv，此時計算停止。最終的v就是各個頁面的 pagerank 值。例如上面的向量經過幾步迭代后，大約收斂在（1/4, 1/4, 1/5, 1/4），這就是A、B、C、D最后的 pagerank。
處理 Dead Ends
上面的 PageRank 計算方法假設 Web 是強連通的，但實際上，Web 并不是強連通（甚至不是聯通的）。下面看看 PageRank 算法如何處理一種叫做 Dead Ends 的情況。
所謂 Dead Ends，就是這樣一類節點：它們不存在外鏈。看下面的圖：
注意這里D頁面不存在外鏈，是一個 Dead End。上面的算法之所以能成功收斂到非零值，很大程度依賴轉移矩陣這樣一個性質：每列的加和為1。而在這個圖中，M第四列將全為0。在沒有 Dead Ends 的情況下，每次迭代后向量v各項的和始終保持為1，而有了 Dead Ends，迭代結果將最終歸零（要解釋為什么會這樣，需要一些矩陣論的知識，比較枯燥，此處略）。
處理 Dead Ends 的方法如下：迭代拿掉圖中的 Dead Ends 節點及 Dead Ends 節點相關的邊（之所以迭代拿掉是因為當目前的 Dead Ends 被拿掉后，可能會出現一批新的 Dead Ends），直到圖中沒有 Dead Ends。對剩下部分計算 rank，然后以拿掉 Dead Ends 逆向順序反推 Dead Ends 的 rank。
以上圖為例，首先拿到D和D相關的邊，D被拿到后，C就變成了一個新的 Dead Ends，于是拿掉C，最終只剩A、B。此時可很容易算出A、B的 PageRank 均為1/2。然后我們需要反推 Dead Ends 的 rank，最后被拿掉的是C，可以看到C前置節點有A和B，而A和B的出度分別為 3 和2，因此C的 rank 為：1/2 * 1/3 + 1/2 * 1/2 = 5/12；最后，D的 rank 為：1/2 * 1/3 + 5/12 * 1 = 7/12。所以最終的 PageRank 為（1/2, 1/2, 5/12, 7/12）。
Spider Traps 及平滑處理
可以預見，如果把真實的 Web 組織成轉移矩陣，那么這將是一個極為稀疏的矩陣，從矩陣論知識可以推斷，極度稀疏的轉移矩陣迭代相乘可能會使得向量v變得非常不平滑，即一些節點擁有很大 的 rank，而大多數節點 rank 值接近0。而一種叫做 Spider Traps 節點的存在加劇了這種不平滑。例如下圖：
D 有外鏈所以不是 Dead Ends，但是它只鏈向自己（注意鏈向自己也算外鏈，當然同時也是個內鏈）。這種節點叫做 Spider Trap，如果對這個圖進行計算，會發現D的 rank 越來越大趨近于1，而其它節點 rank 值幾乎歸零。
為了克服這種由于矩陣稀疏性和 Spider Traps 帶來的問題，需要對 PageRank 計算方法進行一個平滑處理，具體做法是加入“心靈轉移（teleporting）”。所謂心靈轉移，就是我們認為在任何一個頁面瀏覽的用戶都有可能以一個 極小的概率瞬間轉移到另外一個隨機頁面。當然，這兩個頁面可能不存在超鏈接，因此不可能真的直接轉移過去，心靈轉移只是為了算法需要而強加的一種純數學意 義的概率數字。
加入心靈轉移后，向量迭代公式變為：
其中β往往被設置為一個比較小的參數（0.2或更小），e為N維單位向量，加入e的原因是這個公式的前半部分是向量，因此必須將β/N轉為向量才能相加。這樣，整個計算就變得平滑，因為每次迭代的結果除了依賴轉移矩陣外，還依賴一個小概率的心靈轉移。
以上圖為例，轉移矩陣M為：
設β為0.2，則加權后的M為：
因此：
如果按這個公式迭代算下去，會發現 Spider Traps 的效應被抑制了，從而每個頁面都擁有一個合理的 pagerank。
Topic-Sensitive PageRank
其實上面的討論我們回避了一個事實，那就是“網頁重要性”其實沒一個標準答案，對于不同的用戶，甚至有很大的差別。例如，當搜索“蘋果”時，一 個數碼愛好者可能是想要看 iphone 的信息，一個果農可能是想看蘋果的價格走勢和種植技巧，而一個小朋友可能在找蘋果的簡筆畫。理想情況下，應該為每個用戶維護一套專用向量，但面對海量用戶 這種方法顯然不可行。所以搜索引擎一般會選擇一種稱為 Topic-Sensitive 的折中方案。Topic-Sensitive PageRank 的做法是預定義幾個話題類別，例如體育、娛樂、科技等等，為每個話題單獨維護一個向量，然后想辦法關聯用戶的話題傾向，根據用戶的話題傾向排序結果。
Topic-Sensitive PageRank 分為以下幾步：
1、確定話題分類。
一般來說，可以參考 Open Directory（DMOZ）的 一級話題類別作為 topic。目前 DMOZ 的一級 topic 有：Arts（藝術）、Business（商務）、Computers（計算機）、Games（游戲）、Health（醫療健康）、Home（居家）、 Kids and Teens（兒童）、News（新聞）、Recreation（娛樂修養）、Reference（參考）、Regional（地域）、Science（科 技）、Shopping（購物）、Society（人文社會）、Sports（體育）。
2、網頁 topic 歸屬。
這一步需要將每個頁面歸入最合適的分類，具體歸類有很多算法，例如可以使用 TF-IDF 基于詞素歸類，也可以聚類后人工歸類，具體不再展開。這一步最終的結果是每個網頁被歸到其中一個 topic。
3、分 topic 向量計算。
在 Topic-Sensitive PageRank 中，向量迭代公式為
首先是單位向量e變為了s。s是這樣一個向量：對于某 topic 的s，如果網頁k在此 topic 中，則s中第k個元素為1，否則為0。注意對于每一個 topic 都有一個不同的s。而s表示s中 1 的數量。
還是以上面的四張頁面為例，假設頁面A歸為 Arts，B歸為 Computers，C歸為 Computers，D歸為 Sports。那么對于 Computers 這個 topic，s就是：
而s=2。因此，迭代公式為：
最后算出的向量就是 Computers 這個 topic 的 rank。如果實際計算一下，會發現B、C頁在這個 topic 下的權重相比上面非 Topic-Sensitive 的 rank 會升高，這說明如果用戶是一個傾向于 Computers topic 的人（例如程序員），那么在給他呈現的結果中B、C會更重要，因此可能排名更靠前。
4、確定用戶 topic 傾向。
最后一步就是在用戶提交搜索時，確定用戶的 topic 傾向，以選擇合適的 rank 向量。主要方法有兩種，一種是列出所有 topic 讓用戶自己選擇感興趣的項目，這種方法在一些社交問答網站注冊時經常使用；另外一種方法就是通過某種手段（如 cookie 跟蹤）跟蹤用戶的行為，進行數據分析判斷用戶的傾向，這本身也是一個很有意思的話題，按時這個話題超出本文的范疇，不再展開細說。
針對 PageRank 的 Spam 攻擊與反作弊
上文說過，Spammer 和搜索引擎反作弊工程師的斗法從來就沒停止過。實際上，只要是算法，就一定有 spam 方法，不存在無懈可擊的排名算法。下面看一下針對 PageRank 的 spam。
Link Spam
回到文章開頭的例子，如果我想讓我的博客在搜索“張洋博客”時排名靠前，顯然在 PageRank 算法下靠 Term Spam 是無法實現的。不過既然我明白了 PageRank 主要靠內鏈數計算頁面權重，那么我是不是可以考慮建立很多空架子網站，讓這些網站都鏈接到我博客首頁，這樣是不是可以提高我博客首頁的 PageRank？很不幸，這種方法行不通。再看下 PageRank 算法，一個頁面會將權重均勻散播給被鏈接網站，所以除了內鏈數外，上游頁面的權重也很重要。而我那些空架子網站本身就沒啥權重，所以來自它們的內鏈并不能 起到提高我博客首頁 PageRank 的作用，這樣只是自娛自樂而已。
所以，Spam PageRank 的關鍵就在于想辦法增加一些高權重頁面的內鏈。下面具體看一下 Link Spam 怎么做。
首先明確將頁面分為幾個類型：
1、目標頁
目標頁是 spammer 要提高 rank 的頁面，這里就是我的博客首頁。
2、支持頁
支持頁是 spammer 能完全控制的頁面，例如 spammer 自己建立的站點中頁面，這里就是我上文所謂的空架子頁面。
3、可達頁
可達頁是 spammer 無法完全控制，但是可以有接口供 spammer 發布鏈接的頁面，例如天涯社區、新浪博客等等這種用戶可發帖的社區或博客站。
4、不可達頁
這是那些 spammer 完全無法發布鏈接的網站，例如政府網站、百度首頁等等。
作為一個 spammer，我能利用的資源就是支持頁和可達頁。上面說過，單純通過支持頁是沒有辦法 spam 的，因此我要做的第一件事情就是盡量找一些 rank 較高的可達頁去加上對我博客首頁的鏈接。例如我可以去天涯、貓撲等地方回個這樣的貼：“樓主的帖子很不錯！精彩內容：http://codinglabs.org”。我想大家一定在各大社區沒少見這種帖子，這就是有人在做 spam。
然后，再通過大量的支持頁放大 rank，具體做法是讓每個支持頁和目標頁互鏈，且每個支持頁只有一條鏈接。
這樣一個結構叫做 Spam Farm，其拓撲圖如下：
其中T是目標頁，A是可達頁，S是支持頁。下面計算一下 link spam 的效果。
設T的總 rank 為y，則y由三部分組成：
1、可達頁的 rank 貢獻，設為x。
2、心靈轉移的貢獻，為β/n。其中n為全部網頁的數量，β為轉移參數。
3、支持頁的貢獻：
設有m個支持頁，因為每個支持頁只和T有鏈接，所以可以算出每個支持頁的 rank 為：
則支持頁貢獻的全部 rank 為：
因此可以得到：
由于相對β，n非常巨大，所以可以認為β/n近似于0。 簡化后的方程為：
解方程得：
假設β為0.2，則1/(2β-β^2) = 2.77 則這個 spam farm 可以將x約放大2.7倍。因此如果起到不錯的 spam 效果。
Link Spam 反作弊
針對 spammer 的 link spam 行為，搜索引擎的反作弊工程師需要想辦法檢測這種行為，一般來說有兩類方法檢測 link spam。
網絡拓撲分析
一種方法是通過對網頁的圖拓撲結構分析找出可能存在的 spam farm。但是隨著 Web 規模越來越大，這種方法非常困難，因為圖的特定結構查找是時間復雜度非常高的一個算法，不可能完全靠這種方法反作弊。
TrustRank
更可能的一種反作弊方法是叫做一種 TrustRank 的方法。
說起來 TrustRank 其實數學本質上就是 Topic-Sensitive Rank，只不過這里定義了一個“可信網頁”的虛擬 topic。所謂可信網頁就是上文說到的不可達頁，或者說沒法 spam 的頁面。例如政府網站（被黑了的不算）、新浪、網易門戶首頁等等。一般是通過人力或者其它什么方式選擇出一個“可信網頁”集合，組成一個 topic，然后通過上文的 Topic-Sensitive 算法對這個 topic 進行 rank 計算，結果叫做 TrustRank。
TrustRank 的思想很直觀：如果一個頁面的普通 rank 遠高于可信網頁的 topic rank，則很可能這個頁面被 spam 了。
設一個頁面普通 rank 為P，TrustRank 為T，則定義網頁的 Spam Mass 為：(P – T)/P。
Spam Mass 越大，說明此頁面為 spam 目標頁的可能性越大。
總結
這篇文章是我對一些資料的歸納匯總，簡單介紹了 PageRank 的背景、作用、計算方法、變種、Spam 及反作弊等內容。為了突出重點我簡化了搜索引擎的模型，當然在實際中搜索引擎遠沒有這么簡單，真實算法也一定非常復雜。不過目前幾乎所有現代搜索引擎頁面 權重的計算方法都基于 PageRank 及其變種。因為我沒做過搜索引擎相關的開發，因此本文內容主要是基于現有文獻的客觀總結，稍加一點我的理解。
文中的圖使用 PGF/TikZ for Tex 繪制：http://www.texample.net/tikz/。
文中公式由 codecogs 在線 LaTeX 公式編輯器生成：http://www.codecogs.com/latex/eqneditor.php。