Google的成功意味著PageRank算法值得特別的關(guān)注。PageRank算法是少數(shù)幾個公開的排序算法之一。PageRank算法對數(shù)學要求很高，但可以做些簡單的解釋，以分析它對網(wǎng)絡(luò)空間的影響。搜索引擎的其他排序算法也可能獲得與PageRank算法相同的結(jié)果，盡管他們沒有公開任何與其相關(guān)的信息。HITS算法是另一個基于鏈接的排序算法，與PageRank算法形成鮮明對比，下面的引述概括了鏈接對于搜索引擎的價值。 “通過分析網(wǎng)頁間的鏈接關(guān)系，搜索引擎可以判定出一個網(wǎng)頁是關(guān)于什么的，也可以判斷它是否很重要并值得列入排序列表中去。”

搜索引擎在排序過程中不考慮鏈接因素，而使用一個基于關(guān)鍵詞詞頻的公式，該公式在潛在匹配文檔中統(tǒng)計以用戶為中心的查詢的關(guān)鍵詞的詞頻。例如，檢索“動物學”時，引擎可能返回文檔標題、頭部和正文或是在URL中出現(xiàn)該詞語的所有網(wǎng)頁。這種排序算法可能無法判定哪些是關(guān)于“動物學”的最權(quán)威的網(wǎng)頁，而只能判定哪些頁面中與“動物學”相關(guān)的詞語最多。但PageRank算法卻可以通過鏈接結(jié)構(gòu)，判別出哪個是最權(quán)威的網(wǎng)頁——排名位于最前面的那個，即擁有最多入鏈的網(wǎng)頁。這就使得引擎能夠返回一個真正的權(quán)威網(wǎng)頁，而不是一個類似于“動物學”課程表的網(wǎng)頁。

1998年Google的PageRank算法的設(shè)計者和奠基者Brin和Page將其核心部分公開。隨后，在1999年他們和Motwani、Winogriad對其進行了更為詳細地闡述。直到2004年，該算法仍在使用，只是作為一個更大規(guī)模的算法集的一部分，該算法集采用100多個指標來判定網(wǎng)頁是否和用戶的查詢相關(guān)，并對它們進行排序。Google官方聲明：“雖然我們有許多工程師在為全面提高Google的各個方面而努力，但PageRank算法仍然是我們網(wǎng)絡(luò)搜索工具技術(shù)的基礎(chǔ)。”下面是支撐PageRank算法的兩個基本理念：

·人鏈是衡量目標網(wǎng)頁重要性的很好的指標。

·源于重要網(wǎng)頁的人鏈比源于次要網(wǎng)頁的人鏈更能說明該網(wǎng)頁的重要性。

將對PageRank算法進行闡述。在這里，使用Google網(wǎng)站和其他地方所用的“投票”這一比喻代替原來的“隨機沖浪”一詞所表達的含義。

在一個簡單的基于鏈接的投票系統(tǒng)中，可以給每個網(wǎng)頁投票，并允許網(wǎng)頁將其一票平分后投給它所鏈接的網(wǎng)頁，最后統(tǒng)計每個網(wǎng)頁的最終票數(shù)便可形成一個排序系統(tǒng)。在這一過程中，擁有較多人鏈的網(wǎng)站能獲得較高的票數(shù)。然而，這個簡單的投票系統(tǒng)不足以說明問題。如受歡迎的列表網(wǎng)頁的入鏈很多，就會獲得很多投票，但該頁面只有一票，可平分給它所鏈接的目標網(wǎng)頁，這些目標網(wǎng)頁中可能含有有價值的內(nèi)容。重復(fù)這個投票過程，使得每個網(wǎng)頁在前一輪中獲得的票數(shù)平分給其目標網(wǎng)頁。然而遺憾的是，當投票系統(tǒng)陷入循環(huán)時，或遇到一個沒有出鏈的網(wǎng)頁時，投票的重復(fù)過程便無法進行下去了。

對此，Brin和Page提出的解決方案是，在每次投票時，網(wǎng)頁回收一部分票數(shù)，而不全部傳遞給它的鏈接目標網(wǎng)頁。他們建議保留15%的票數(shù)，這樣，每次投票時，網(wǎng)頁只將其85％的票數(shù)平分給其鏈接目標網(wǎng)頁，而另外15％的票數(shù)供系統(tǒng)中所有的URL平分。運用數(shù)學算法可以有效地實現(xiàn)這一投票系統(tǒng)。重復(fù)這樣的投票過程，直至所有網(wǎng)頁的票數(shù)都趨于穩(wěn)定，即在新的一輪投票中，網(wǎng)頁票數(shù)的變化很小，這樣，PageRank算法便誕生了。

有兩種PageRank算法和修正算法，修正后的算法有明顯的不同。實踐中，Google采用的可能是PageRank修正算法。第一種修正算法是由Lifantsel在2000年提出的，即將PageRank的投票統(tǒng)計建立在網(wǎng)站的基礎(chǔ)上，而不是對單個網(wǎng)頁進行投票統(tǒng)計。第二種修正算法是由Page、Brin、Motwain和Winograd于1999年提出的，即自動賦予一個網(wǎng)站的首頁較高的票數(shù)。Google似乎同時采用了這兩種修正算法，可能是與基于網(wǎng)頁的標準算法相結(jié)合，也可能是完全將其取代，但這些都只是猜測 。

最新評論