PageRank算法淺析
基于鏈接的排序算法似乎已廣泛應用到各種商業搜索引擎中。為了讓設計出來的網站能夠在各種搜索引擎中獲得較高排名,設計者們應該知道這些算法的原理。Google的成功意味著PageRank算法值得特別的關注。PageRank算法是少數幾個公開的排序算法之一。PageRank算法對數學要求很高,但可以做些簡單的解釋,以分析它對網絡空間的影響。搜索引擎的其他排序算法也可能獲得與PageRank算法相同的結果,盡管他們沒有公開任何與其相關的信息。HITS算法是另一個基于鏈接的排序算法,與PageRank算法形成鮮明對比,下面的引述概括了鏈接對于搜索引擎的價值。 “通過分析網頁間的鏈接關系,搜索引擎可以判定出一個網頁是關于什么的,也可以判斷它是否很重要并值得列入排序列表中去。”
搜索引擎在排序過程中不考慮鏈接因素,而使用一個基于關鍵詞詞頻的公式,該公式在潛在匹配文檔中統計以用戶為中心的查詢的關鍵詞的詞頻。例如,檢索“動物學”時,引擎可能返回文檔標題、頭部和正文或是在URL中出現該詞語的所有網頁。這種排序算法可能無法判定哪些是關于“動物學”的最權威的網頁,而只能判定哪些頁面中與“動物學”相關的詞語最多。但PageRank算法卻可以通過鏈接結構,判別出哪個是最權威的網頁——排名位于最前面的那個,即擁有最多入鏈的網頁。這就使得引擎能夠返回一個真正的權威網頁,而不是一個類似于“動物學”課程表的網頁。
1998年Google的PageRank算法的設計者和奠基者Brin和Page將其核心部分公開。隨后,在1999年他們和Motwani、Winogriad對其進行了更為詳細地闡述。直到2004年,該算法仍在使用,只是作為一個更大規模的算法集的一部分,該算法集采用100多個指標來判定網頁是否和用戶的查詢相關,并對它們進行排序。Google官方聲明:“雖然我們有許多工程師在為全面提高Google的各個方面而努力,但PageRank算法仍然是我們網絡搜索工具技術的基礎。”下面是支撐PageRank算法的兩個基本理念:
·人鏈是衡量目標網頁重要性的很好的指標。
·源于重要網頁的人鏈比源于次要網頁的人鏈更能說明該網頁的重要性。
青青電商將對PageRank算法進行闡述。在這里,思億歐使用Google網站和其他地方所用的“投票”這一比喻代替原來的“隨機沖浪”一詞所表達的含義。
在一個簡單的基于鏈接的投票系統中,可以給每個網頁投票,并允許網頁將其一票平分后投給它所鏈接的網頁,最后統計每個網頁的最終票數便可形成一個排序系統。在這一過程中,擁有較多人鏈的網站能獲得較高的票數。然而,這個簡單的投票系統不足以說明問題。如受歡迎的列表網頁的入鏈很多,就會獲得很多投票,但該頁面只有一票,可平分給它所鏈接的目標網頁,這些目標網頁中可能含有有價值的內容。重復這個投票過程,使得每個網頁在前一輪中獲得的票數平分給其目標網頁。然而遺憾的是,當投票系統陷入循環時,或遇到一個沒有出鏈的網頁時,投票的重復過程便無法進行下去了。
對此,Brin和Page提出的解決方案是,在每次投票時,網頁回收一部分票數,而不全部傳遞給它的鏈接目標網頁。他們建議保留15%的票數,這樣,每次投票時,網頁只將其85%的票數平分給其鏈接目標網頁,而另外15%的票數供系統中所有的URL平分。運用數學算法可以有效地實現這一投票系統。重復這樣的投票過程,直至所有網頁的票數都趨于穩定,即在新的一輪投票中,網頁票數的變化很小,這樣,PageRank算法便誕生了。
有兩種PageRank算法和修正算法,修正后的算法有明顯的不同。實踐中,Google采用的可能是PageRank修正算法。第一種修正算法是由Lifantsel在2000年提出的,即將PageRank的投票統計建立在網站的基礎上,而不是對單個網頁進行投票統計。第二種修正算法是由Page、Brin、Motwain和Winograd于1999年提出的,即自動賦予一個網站的首頁較高的票數。Google似乎同時采用了這兩種修正算法,可能是與基于網頁的標準算法相結合,也可能是完全將其取代,但這些都只是猜測。