正文

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

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


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

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

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

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

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


上一章目錄下一章

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