淺析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對應上圖：

M=⎡⎣⎢⎢⎢01/31/31/31/201/2000011/21/200⎤⎦⎥⎥⎥

然後，設初始時每個頁面的rank值為1/N，這裡就是1/4。按A-D順序将頁面rank為向量v：

v=⎡⎣⎢⎢⎢1/41/41/41/4⎤⎦⎥⎥⎥

注意，M第一行分别是A、B、C和D轉移到頁面A的機率，而v的第一列分别是A、B、C和D目前的rank，是以用M的第一行乘以v的第一列，所得結果就是頁面A最新rank的合理估計，同理，Mv的結果就分别代表A、B、C、D新rank：

Mv=⎡⎣⎢⎢⎢1/45/245/241/3⎤⎦⎥⎥⎥

然後用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）”。所謂心靈轉移，就是我們認為在任何一個頁面浏覽的使用者都有可能以一個極小的機率瞬間轉移到另外一個随機頁面。當然，這兩個頁面可能不存在超連結，是以不可能真的直接轉移過去，心靈轉移隻是為了算法需要而強加的一種純數學意義的機率數字。

加入心靈轉移後，向量疊代公式變為：

v′=(1−β)Mv+eβN

其中β往往被設定為一個比較小的參數（0.2或更小），e為N維機關向量，加入e的原因是這個公式的前半部分是向量，是以必須将β/N轉為向量才能相加。這樣，整個計算就變得平滑，因為每次疊代的結果除了依賴轉移矩陣外，還依賴一個小機率的心靈轉移。

以上圖為例，轉移矩陣M為：

M=⎡⎣⎢⎢⎢01/31/31/31/201/2000010001⎤⎦⎥⎥⎥

設β為0.2，則權重後的M為：

M=⎡⎣⎢⎢⎢04/154/154/152/502/500004/50004/5⎤⎦⎥⎥⎥

是以：

v′=⎡⎣⎢⎢⎢04/154/154/152/502/500004/50004/5⎤⎦⎥⎥⎥v+⎡⎣⎢⎢⎢1/201/201/201/20⎤⎦⎥⎥⎥

如果按這個公式疊代算下去，會發現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中，向量疊代公式為

v′=(1−β)Mv+sβ|s|

首先是機關向量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=⎡⎣⎢0110⎤⎦⎥

而|s|=2。是以，疊代公式為：

v′=⎡⎣⎢⎢⎢04/154/154/152/502/500004/50004/5⎤⎦⎥⎥⎥v+⎡⎣⎢⎢01/101/100⎤⎦⎥⎥

最後算出的向量就是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為：

(1−β)ym+βn

則支援頁貢獻的全部rank為：

m(1−β)((1−β)ym+βn)

是以可以得到：

y=m(1−β)((1−β)ym+βn)+x+βn

由于相對β，n非常巨大，是以可以認為β/n近似于0。 簡化後的方程為：

y=m(1−β)((1−β)ym)+x

解方程得：

y=x12β−β2

假設β為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/。

參考文獻

[1] Anand Rajaraman, Jeffrey D. Ullman, Mining of Massive Datasets. 2010-2011

[2] S. Brin and L. Page, “Anatomy of a large-scale hypertextual web search engine,” Proc. 7th Intl. World-Wide-Web Conference, pp. 107–117, 1998.

[3] A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Weiner, “Graph structure in the web,” Computer Networks 33:1–6, pp. 309–320, 2000.

[4] T.H. Haveliwala, “Topic-sensitive PageRank,” Proc. 11th Intl. World-Wide-Web Conference, pp. 517–526, 2002

[5] Z. Gy¨ongi, H. Garcia-Molina, and J. Pedersen, “Combating link spam with trustrank,” Proc. 30th Intl. Conf. on Very Large Databases, pp. 576–587, 2004.