Google(谷歌)使用PageRank算法給搜索結(jié)果排序的原理

時(shí)間：2022-05-29 03:30:01 | 來源：網(wǎng)絡(luò)營銷

時(shí)間：2022-05-29 03:30:01 來源：網(wǎng)絡(luò)營銷

一個(gè)正常的搜索引擎，其核心功能自然是網(wǎng)頁搜索，那搜索結(jié)果應(yīng)該怎樣排序才最好呢？實(shí)際上，在谷歌主導(dǎo)互聯(lián)網(wǎng)搜索之前，人們?yōu)榇藗噶四X筋。

當(dāng)時(shí)人們認(rèn)為，通過判斷能夠得知哪個(gè)網(wǎng)頁更重要，對搜索引擎的發(fā)展十分有幫助，很顯然搜索引擎應(yīng)該把重要的網(wǎng)頁放到搜索結(jié)果中比較靠前的地方。這個(gè)問題看起來很容易，但是解決的方法卻沒有想象的那么簡單。

一、網(wǎng)頁排名和谷歌算法的誕生

在谷歌誕生之前那段時(shí)間，流行的網(wǎng)頁排名算法都很類似，它們都使用了一個(gè)非常簡單的思想：越是重要的網(wǎng)頁，訪問量就會(huì)越大，許多大公司就通過統(tǒng)計(jì)網(wǎng)頁的訪問量來進(jìn)行網(wǎng)頁排名。但是這種排名算法有兩個(gè)很顯著的問題：

1、因?yàn)橹荒軌虺闃咏y(tǒng)計(jì)，所以統(tǒng)計(jì)數(shù)據(jù)不一定準(zhǔn)確，而且訪問量的波動(dòng)會(huì)比較大，想要得到準(zhǔn)確的統(tǒng)計(jì)需要大量的時(shí)間和人力，還只能維持很短的有效時(shí)間。

2、訪問量并不一定能體現(xiàn)網(wǎng)頁的“重要程度”，可能一些比較早接觸互聯(lián)網(wǎng)的網(wǎng)民還記得，那時(shí)有很多人推出了專門“刷訪問量”的服務(wù)。

那有沒有更好的方法，不統(tǒng)計(jì)訪問量就能夠?yàn)榫W(wǎng)頁的重要度排序呢？

就是在這種情況下，1996年初，谷歌公司的創(chuàng)始人，當(dāng)時(shí)還是美國斯坦福大學(xué)研究生的佩奇和布林開始了對網(wǎng)頁排序問題的研究。

在1999年，一篇以佩奇為第一作者的論文發(fā)表了，論文中介紹了一種叫做PageRank的算法（具體算法可查看億企邦《pr值是什么》的相關(guān)介紹），這種算法的主要思想是：越“重要”的網(wǎng)頁，頁面上的鏈接質(zhì)量也越高，同時(shí)越容易被其它“重要”的網(wǎng)頁鏈接。

于是，算法完全利用網(wǎng)頁之間互相鏈接的關(guān)系來計(jì)算網(wǎng)頁的重要程度，將網(wǎng)頁排序徹底變成一個(gè)數(shù)學(xué)問題，終于擺脫了訪問量統(tǒng)計(jì)的框框。

二、模擬PageRank算法的運(yùn)行過程

在詳細(xì)講述這個(gè)算法之前，不妨讓我們用一個(gè)游戲，先來簡單模擬一下PageRank算法的運(yùn)行過程，以便讀者更好地理解。

三兄弟分30顆豌豆，起初每人10顆，他們每次都要把手里的豌豆全部平均分給自己喜歡的人，下圖表示了三兄弟各自擁有的初始豌豆數(shù)量，以及相互喜歡的關(guān)系（箭頭方向表示喜歡，例如老二喜歡老大，老大喜歡老二和老三）。

第一次分配后，我們會(huì)得到結(jié)果如下：

就這樣，讓游戲一直進(jìn)行下去，直到他們手中的豌豆數(shù)不再變化為止。

那么這個(gè)游戲到底是否可以結(jié)束呢，如果可以，最終的結(jié)果又是什么樣的？

在此我們用電腦模擬了這個(gè)過程，得出的結(jié)果是：老大和老二的盤子里各有12顆豌豆，而老三的盤子里有6顆豌豆，這時(shí)候無論游戲怎么進(jìn)行下去，盤子里的豌豆數(shù)量都不會(huì)再變化。

看到這里，讀者可能會(huì)問：這個(gè)游戲和網(wǎng)頁排序有什么關(guān)系？

實(shí)際上，PageRank會(huì)給每個(gè)網(wǎng)頁一個(gè)數(shù)值，這個(gè)數(shù)值越高，就說明這個(gè)網(wǎng)頁越“重要”。

而剛剛的游戲中，如果把豌豆的數(shù)量看作這個(gè)數(shù)值（可以不是整數(shù)），把孩子們看作網(wǎng)頁，那么游戲的過程就是PageRank的算法，而游戲結(jié)束時(shí)豌豆的分配，就是網(wǎng)頁的PageRank值。

三、PageRank算法的數(shù)學(xué)模型

不同于之前的訪問量統(tǒng)計(jì)，PageRank求解了這樣一個(gè)問題：一個(gè)人在網(wǎng)絡(luò)上瀏覽網(wǎng)頁，每看過一個(gè)網(wǎng)頁之后就會(huì)隨機(jī)點(diǎn)擊網(wǎng)頁上的鏈接訪問新的網(wǎng)頁。

如果當(dāng)前這個(gè)人瀏覽的網(wǎng)頁x已經(jīng)確定，那么網(wǎng)頁x上每個(gè)鏈接被點(diǎn)擊的概率也是確定的，可以用向量Nx表示。

在這種條件下，這個(gè)人點(diǎn)擊了無限多次鏈接后，恰好停留在每個(gè)網(wǎng)頁上的概率分別是多少？

在這個(gè)模型中，我們用向量Ri來表示點(diǎn)擊了i次鏈接之后可能停留在每個(gè)網(wǎng)頁上的概率（則為一開始就打開了每個(gè)網(wǎng)頁的概率，后面我們將證明的取值對最終結(jié)果沒有影響）。很顯然R i的L1范式為1 ，這也是PageRank算法本身的要求。

仍以上面的游戲?yàn)槔麄€(gè)瀏覽過程的一開始，我們有：

其中，A表示每一次點(diǎn)擊鏈接概率的矩陣，A的第i列第j行的含義是如果當(dāng)前訪問的網(wǎng)頁是網(wǎng)頁i，那么下一次點(diǎn)擊鏈接跳轉(zhuǎn)到網(wǎng)頁j的概率為 。

這樣設(shè)計(jì)矩陣A的好處是，通過矩陣A和向量相乘，即可得出點(diǎn)擊一次鏈接后每個(gè)網(wǎng)頁可能的停留概率向量。例如，令，可以得到點(diǎn)擊一次鏈接后停留在每個(gè)網(wǎng)頁的概率：

之后一直迭代下去，有：

對于上面的例子，迭代結(jié)果如下圖：

由上圖我們可以看到，每個(gè)網(wǎng)頁停留的概率在振蕩之后趨于穩(wěn)定。

在這種穩(wěn)定狀態(tài)下，我們可以知道，無論如何迭代，都有，這樣我們就獲得了一個(gè)方程：

而整個(gè)迭代的過程，就是在尋求方程R = AR的解，而無論是多少，迭代無限多次之后，一定會(huì)取得令R = AR成立的R值，整個(gè)求解R的過程，就如同一個(gè)人在一張地圖上的不同位置之間隨機(jī)地行走一樣，所以被稱為“隨機(jī)行走模型”。

隨機(jī)行走模型有一個(gè)顯著的特點(diǎn)，那就是每一次迭代的結(jié)果只與前一次有關(guān)，與更早的結(jié)果完全無關(guān)，這種過程又被稱為馬爾可夫過程（Markov Process）或馬爾可夫鏈（Markov Chain）。

馬爾可夫過程的數(shù)學(xué)定義是：如果對于一個(gè)隨機(jī)變量序列， 其中X n表示時(shí)間n的狀態(tài)及轉(zhuǎn)移概率P，有：

即只受的影響，則此過程成為馬爾可夫過程。其中稱作“一步轉(zhuǎn)移概率”，而兩步、三步轉(zhuǎn)移概率則可以通過一步轉(zhuǎn)移概率的積分求得。

當(dāng)狀態(tài)空間有限時(shí)，轉(zhuǎn)移概率可以用用一個(gè)矩陣A來表示，稱作轉(zhuǎn)移矩陣（transition matrix），此時(shí)轉(zhuǎn)移概率的積分即為矩陣的冪，k步轉(zhuǎn)移概率可以用表示，這也是隨機(jī)行走模型中的情況，而對于一個(gè)正的（每個(gè)元素都為正的）轉(zhuǎn)移矩陣A ，可以證明一定有：

這就完整解釋了為什么的取值對最終結(jié)果沒有影響。

四、修正“懸掛網(wǎng)頁”帶來的不良影響

但是這里有一個(gè)問題：即便的取值對最終結(jié)果沒有影響，用R作為網(wǎng)頁排序的依據(jù)是否真的合理？

在億企邦看來，這個(gè)其實(shí)并不合理，因?yàn)楫?dāng)一個(gè)網(wǎng)頁只有鏈入鏈接沒有鏈出鏈接的時(shí)候，這個(gè)網(wǎng)頁就會(huì)像一個(gè)“黑洞”一樣，將同一個(gè)連通子圖中其它網(wǎng)頁流向它的PageRank慢慢“吞掉”（因?yàn)樗惴ㄖ刑摂M的用戶一旦進(jìn)入那樣的網(wǎng)頁，就會(huì)由于沒有對外鏈接而永遠(yuǎn)停留在那里），這種網(wǎng)頁我們稱之為“懸掛網(wǎng)頁”（Dangling Link）。

這種“黑洞”效應(yīng)是如此顯著，以至于在一個(gè)連通性良好的互聯(lián)網(wǎng)上，哪怕只有一個(gè)“懸掛網(wǎng)頁”，也足以使整個(gè)互聯(lián)網(wǎng)的網(wǎng)頁排序失效，可謂是“一粒老鼠屎壞了一鍋粥”。

為了解決這個(gè)問題，佩奇和布林進(jìn)行了修正，他們意識(shí)到，當(dāng)用戶訪問到“懸掛網(wǎng)頁”時(shí)，都不可能也不應(yīng)該就停留在了這個(gè)頁面，而是會(huì)自行訪問其它網(wǎng)頁。

雖然對每個(gè)用戶來說，自行訪問的網(wǎng)頁與各人的興趣有關(guān)，但億企邦覺得從平均意義上來講，佩奇和布林假定用戶將會(huì)在整個(gè)互聯(lián)網(wǎng)上隨機(jī)選取一個(gè)網(wǎng)頁進(jìn)行訪問。

所以他們給PageRank算法加入了一個(gè)新的向量E，它的作用是，按照其中所描述的比例來向全部網(wǎng)頁分配懸掛網(wǎng)頁每一次“吞掉”的PageRank。

這樣，相當(dāng)于為懸掛網(wǎng)頁添加了鏈向網(wǎng)絡(luò)上全部網(wǎng)頁的鏈接，避免了懸掛鏈接的出現(xiàn)。

以上就是谷歌背后最重要的PageRank算法奧秘，與以往那種憑借關(guān)鍵詞出現(xiàn)次數(shù)所作的排序不同，這種由所有網(wǎng)頁的相互鏈接所確定的排序是不那么容易做假的，因?yàn)樽黾僬咴偈前炎约旱木W(wǎng)頁吹得天花亂墜，如果沒有真正吸引人的內(nèi)容，別人不鏈接它，一切就還是枉然。

而且“佩奇排序”還有一個(gè)重要特點(diǎn)，那就是它只與互聯(lián)網(wǎng)的結(jié)構(gòu)有關(guān)，而與用戶具體搜索的東西無關(guān)，這意味著排序計(jì)算可以單獨(dú)進(jìn)行，而無需在用戶鍵入搜索指令后才臨時(shí)進(jìn)行，谷歌搜索的速度之所以快捷，在很大程度上得益于此。

億企邦點(diǎn)評：

最后，我要強(qiáng)調(diào)的一點(diǎn)是，雖然PageRank是Google搜索結(jié)果排序的重要依據(jù)，并以此發(fā)家，不過它并不是全部依據(jù)，實(shí)際上，Google發(fā)展到現(xiàn)在，已同時(shí)用了數(shù)百種不同的算法來確定最終顯示給用戶的搜索結(jié)果順序。