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