佩奇排名介紹

佩奇排名是根據(jù)頁(yè)面之間的鏈接結(jié)構(gòu)計(jì)算頁(yè)面的值的一種算法。下面我們通過(guò)動(dòng)畫(huà)來(lái)理解進(jìn)行計(jì)算的具體流程。

假設(shè)一個(gè)正方形表示一個(gè) WEB 頁(yè)面，一個(gè)箭頭表示一個(gè)頁(yè)面之間的鏈接。

此圖表明下面 3 頁(yè)包含指向上面 1 頁(yè)的鏈接

在佩奇排名算法中，網(wǎng)頁(yè)指向的鏈接越多，頁(yè)面被確定為越重要。

因此，在這里，確定首頁(yè)最重要。

確定首頁(yè)最重要

實(shí)際上，每個(gè)頁(yè)面的重要性都是通過(guò)計(jì)算來(lái)量化的。

基本的計(jì)算方法思想

1.未鏈接的頁(yè)面分?jǐn)?shù)為 1

未鏈接的頁(yè)面分?jǐn)?shù)為 1

2.有鏈接的頁(yè)面得分為正在鏈接的頁(yè)面的總得分

有鏈接的頁(yè)面得分為正在鏈接的頁(yè)面的總得分

3.當(dāng)有多個(gè)網(wǎng)頁(yè)的鏈接時(shí)，鏈接分?jǐn)?shù)均勻分布

鏈接分?jǐn)?shù)均勻分布

4.來(lái)自高度鏈接網(wǎng)頁(yè)的鏈接具有很高的價(jià)值

該圖中心頁(yè)面有三個(gè)獨(dú)立頁(yè)面指向它的鏈接，所以它的分?jǐn)?shù)是 3 。

首頁(yè)有一個(gè)很大的分?jǐn)?shù)，因?yàn)殒溄邮菑姆謹(jǐn)?shù)為 3 的頁(yè)面指向它的。

在動(dòng)畫(huà)中的六個(gè)頁(yè)面中，判斷最上面的頁(yè)面是最重要的頁(yè)面----這是佩奇排名的基本思想。

基本的計(jì)算方法思想的循環(huán)問(wèn)題

如果按照順序來(lái)計(jì)算每個(gè)頁(yè)面的分?jǐn)?shù)時(shí)，那么就會(huì)出現(xiàn)問(wèn)題：以這種方式計(jì)算，它將無(wú)限循環(huán)，并且在循環(huán)中的頁(yè)面得分在任何地方都會(huì)很高。

循環(huán)的問(wèn)題可以通過(guò)“隨機(jī)游走模型”的計(jì)算方法來(lái)解決。

隨機(jī)游走模型

以小豬佩奇瀏覽網(wǎng)頁(yè)為例。

小豬佩奇開(kāi)始訪問(wèn)「五分鐘學(xué)算法」中有趣的頁(yè)面，那么從這個(gè)左下角頁(yè)面開(kāi)始。

它們跟隨一個(gè)鏈接并移動(dòng)到另外的一個(gè)頁(yè)面，看了一些之后，發(fā)現(xiàn)不敢興趣了，這樣就停止了瀏覽。

然后，又一天，它在小吳的推薦下，在完全不同的頁(yè)面進(jìn)行瀏覽，跟隨一個(gè)鏈接并移動(dòng)到另外的一個(gè)頁(yè)面，一旦失去興趣就停止瀏覽。

像這樣，重復(fù)從某個(gè)頁(yè)面開(kāi)始瀏覽，移動(dòng)幾頁(yè)后便停止的操作，如果從互聯(lián)網(wǎng)空間一側(cè)進(jìn)行觀察，就像網(wǎng)頁(yè)瀏覽的人：重復(fù)移動(dòng)頁(yè)面幾次后傳送到一個(gè)完全不同的頁(yè)面。

量化隨機(jī)游走模型

假設(shè)1 - α代表選擇當(dāng)前頁(yè)面中的一個(gè)鏈接的概率。

α代表該人將傳送到其他頁(yè)面的概率。

現(xiàn)在用隨機(jī)游走模型 處理上述的循環(huán)問(wèn)題。

如果總頁(yè)面訪問(wèn)次數(shù)達(dá)到1000次之后，使用百分比進(jìn)行表示：那么這個(gè)值就表示“在某個(gè)時(shí)間點(diǎn)查看頁(yè)面的概率”。

更實(shí)用的計(jì)算方法

如圖所示，現(xiàn)在來(lái)嘗試計(jì)算復(fù)雜的鏈接網(wǎng)絡(luò)中每個(gè)頁(yè)面的分?jǐn)?shù)。

現(xiàn)在均勻設(shè)置分?jǐn)?shù)，使總分加起來(lái)為 1 。而后根據(jù)網(wǎng)頁(yè)瀏覽者的移動(dòng)，來(lái)計(jì)算每個(gè)頁(yè)面的概率。

移動(dòng) n次時(shí)出現(xiàn)在 A 中的概率表示未PAn，移動(dòng) n 次時(shí)出現(xiàn)在 B 中的概率表示未PBn。

舉一個(gè)例子，在移動(dòng) 1 次之后求在 A 的概率PA 1。

在 C 選擇移動(dòng)的概率是1-α。

其中，移動(dòng)到 A 的一種場(chǎng)景是，C 中的佩奇選擇了移動(dòng)而不是傳送。另外，這里選擇了 A 而不是 B 作為目的地。

并且，根據(jù)上面的當(dāng)有多個(gè)網(wǎng)頁(yè)的鏈接時(shí)，鏈接分?jǐn)?shù)均勻分布這條規(guī)則，從 A 或 B 選擇 A 的概率是 0.5 。

因此，從 C 移動(dòng)到 A 的概率是PC0 ?? （1-α） ?? 0.5。

A 被選為傳送目標(biāo)的概率是 0.25

A 被選為傳送目標(biāo)的概率是 0.25 ，根據(jù)前面的理論：在 A、B、C、D 中小佩奇選擇傳送的概率為α。因此，通過(guò)傳送移動(dòng)到 A 的概率為α ?? 0.25。 所以，移動(dòng)一次后在 A 的概率為 PA1 = PC0 ?? （ 1 - α ) ?? 0.5 + α ?? 0.25

其中PC0 = 0.25，α = 0.15，代入計(jì)算后PA1 = 0.14375。

這樣，通過(guò)計(jì)算后 B 、 C 、D 頁(yè)的概率也更新了。

B 、 C 、D 頁(yè)的概率也更新了

上面在移動(dòng) 1 次之后這四個(gè)頁(yè)面的概率更新情況，根據(jù)上述相同的方法計(jì)算 2 次后小佩奇瀏覽在每個(gè)頁(yè)面的概率。

移動(dòng) 2 次后

同樣的，經(jīng)過(guò)大量的移動(dòng)，在每個(gè)頁(yè)面上的概率逐漸趨于固定值。當(dāng)數(shù)值固定是，計(jì)算也就完成了。