正文

PageRank——讓谷歌騰飛的技術(shù)(4)

改變未來的九大算法 作者:(美)約翰·麥考密克


下圖就是個例子。圖中有A、B、C、D、E五個網(wǎng)頁。如果從A開始,我們可以通過A訪問B,然后又從B訪問E,而從E我們又能點回A,也就是回到了出發(fā)點。這也意味著A、B和E三個網(wǎng)頁組成了一個循環(huán)。

看來,在遇到循環(huán)時,目前“權(quán)重值”的定義(將超鏈接把戲和權(quán)重把戲結(jié)合起來)就碰到大麻煩了。看看在這個特例中會發(fā)生什么事情。網(wǎng)頁C和D沒有鏈入鏈接,因此其權(quán)重值為1。網(wǎng)頁C和D都鏈向網(wǎng)頁A,因此A的權(quán)重值是網(wǎng)頁C和D權(quán)重值的和,也就是1+1=2。B網(wǎng)頁從A獲得的權(quán)重值為2,而E又從B獲得權(quán)重值2。(這里談到的情況都由上圖左側(cè)部分所體現(xiàn)。)但現(xiàn)在A的權(quán)重值要更新了:A從C和D各得到權(quán)重值1,但也從E得到權(quán)重值2,相加為4。于是B的權(quán)重值也需要更新:從A獲得權(quán)重值4。然后E的權(quán)重值也要更新,它從B獲得了權(quán)重值4。(現(xiàn)在談到的情況都由上圖右側(cè)部分所體現(xiàn)。)依此類推:于是A的權(quán)重值變?yōu)?,B為6,E為6,于是A的權(quán)重值變?yōu)?……你懂了吧?隨著循環(huán)進行,網(wǎng)頁的權(quán)重值會一直增加。

這樣計算權(quán)重值,會產(chǎn)生“雞生蛋,還是蛋生雞”的問題。如果我們知道A網(wǎng)頁真正的權(quán)重值,我們就能計算B網(wǎng)頁和E網(wǎng)頁的權(quán)重值。而如果我們知道B網(wǎng)頁和E網(wǎng)頁真正的權(quán)重值,我們就能計算A網(wǎng)頁的權(quán)重值。但由于這些網(wǎng)頁彼此依賴,似乎這樣計算根本行不通。

幸運的是,我們可以通過被稱為隨機訪問者把戲(the random surfer trick)的技術(shù)解決這個“雞生蛋,還是蛋生雞”的問題。注意:對隨機訪問者把戲的初始描述,和到目前為止探討的超鏈接及權(quán)重把戲沒有任何關(guān)聯(lián)。一旦了解了隨機訪問者把戲的基本原理,我們就會做一些分析,揭示其令人矚目的品質(zhì):隨機訪問者把戲結(jié)合了超鏈接及權(quán)重把戲令人喜愛的屬性,但在出現(xiàn)超鏈接循環(huán)時也行得通。

這個把戲從假想一個隨機訪問互聯(lián)網(wǎng)的人開始。確切地說,訪問者隨機從萬維網(wǎng)上的一個網(wǎng)頁開始訪問,然后檢查該網(wǎng)頁上的所有超鏈接,之后隨機挑選出其中一個超鏈接進行點擊。用戶再檢查打開的新網(wǎng)頁,隨機選擇一個超鏈接打開。這個過程會持續(xù)進行,每一個網(wǎng)頁都是通過隨機選擇前一個網(wǎng)頁上的鏈接打開的。上圖就是個例子。在這個例子中,我們假設(shè)整個萬維網(wǎng)只有16個網(wǎng)頁。框代表網(wǎng)頁,箭頭代表網(wǎng)頁之間的超鏈接。其中標記了四個網(wǎng)頁以便稍后進行參考。被訪問者訪問的網(wǎng)頁用灰色表示,黑色箭頭代表訪問者點擊的超鏈接,虛線箭頭代表隨機重新開始訪問,這個在之后會講到。


上一章目錄下一章

Copyright ? 讀書網(wǎng) ranfinancial.com 2005-2020, All Rights Reserved.
鄂ICP備15019699號 鄂公網(wǎng)安備 42010302001612號