了解google用來對網頁進行排序的pagerank算法，明確哪些因素會影響網頁的pager
在谷歌誕生之前那段時間，流行的網頁排名算法都很類似，它們都使用了壹個非常簡單的思想：越是重要的網頁，訪問量就會越大，許多大公司就通過統計網頁的訪問量來進行網頁排名。但是這種排名算法有兩個很顯著的問題：
1、因為只能夠抽樣統計，所以統計數據不壹定準確，而且訪問量的波動會比較大，想要得到準確的統計需要大量的時間和人力，還只能維持很短的有效時間。
2、訪問量並不壹定能體現網頁的“重要程度”，可能壹些比較早接觸互聯網的網民還記得，那時有很多人推出了專門“刷訪問量”的服務。
那有沒有更好的方法，不統計訪問量就能夠為網頁的重要度排序呢？
就是在這種情況下，1996年初，谷歌公司的創始人，當時還是美國斯坦福大學研究生的佩奇和布林開始了對網頁排序問題的研究。
在1999年，壹篇以佩奇為第壹作者的論文發表了，論文中介紹了壹種叫做PageRank的算法（具體算法可查看馬海祥博客《pr值是什麽》的相關介紹），這種算法的主要思想是：越“重要”的網頁，頁面上的鏈接質量也越高，同時越容易被其它“重要”的網頁鏈接。
於是，算法完全利用網頁之間互相鏈接的關系來計算網頁的重要程度，將網頁排序徹底變成壹個數學問題，終於擺脫了訪問量統計的框框。
二、模擬PageRank算法的運行過程
在詳細講述這個算法之前，不妨讓我們用壹個遊戲，先來簡單模擬壹下PageRank算法的運行過程，以便讀者更好地理解。
三兄弟分30顆豌豆，起初每人10顆，他們每次都要把手裏的豌豆全部平均分給自己喜歡的人，下圖表示了三兄弟各自擁有的初始豌豆數量，以及相互喜歡的關系（箭頭方向表示喜歡，例如老二喜歡老大，老大喜歡老二和老三）。
第壹次分配後，我們會得到結果如下：
就這樣，讓遊戲壹直進行下去，直到他們手中的豌豆數不再變化為止。
那麽這個遊戲到底是否可以結束呢，如果可以，最終的結果又是什麽樣的？
在此我們用電腦模擬了這個過程，得出的結果是：老大和老二的盤子裏各有12顆豌豆，而老三的盤子裏有6顆豌豆，這時候無論遊戲怎麽進行下去，盤子裏的豌豆數量都不會再變化。
看到這裏，讀者可能會問：這個遊戲和網頁排序有什麽關系？
實際上，PageRank會給每個網頁壹個數值，這個數值越高，就說明這個網頁越“重要”。
而剛剛的遊戲中，如果把豌豆的數量看作這個數值（可以不是整數），把孩子們看作網頁，那麽遊戲的過程就是PageRank的算法，而遊戲結束時豌豆的分配，就是網頁的PageRank值。
三、PageRank算法的數學模型
不同於之前的訪問量統計，PageRank求解了這樣壹個問題：壹個人在網絡上瀏覽網頁，每看過壹個網頁之後就會隨機點擊網頁上的鏈接訪問新的網頁。
如果當前這個人瀏覽的網頁x已經確定，那麽網頁x上每個鏈接被點擊的概率也是確定的，可以用向量Nx表示。
在這種條件下，這個人點擊了無限多次鏈接後，恰好停留在每個網頁上的概率分別是多少？
在這個模型中，我們用向量Ri來表示點擊了i次鏈接之後可能停留在每個網頁上的概率（則為壹開始就打開了每個網頁的概率，後面我們將證明的取值對最終結果沒有影響）。很顯然R i的L1範式為1 ，這也是PageRank算法本身的要求。
仍以上面的遊戲為例，整個瀏覽過程的壹開始，我們有：
其中，A表示每壹次點擊鏈接概率的矩陣，A的第i列第j行的含義是如果當前訪問的網頁是網頁i，那麽下壹次點擊鏈接跳轉到網頁j的概率為 。
這樣設計矩陣A的好處是，通過矩陣A和向量相乘，即可得出點擊壹次鏈接後每個網頁可能的停留概率向量。例如，令，可以得到點擊壹次鏈接後停留在每個網頁的概率：
之後壹直叠代下去，有：
對於上面的例子，叠代結果如下圖：
由上圖我們可以看到，每個網頁停留的概率在振蕩之後趨於穩定。
在這種穩定狀態下，我們可以知道，無論如何叠代，都有，這樣我們就獲得了壹個方程：
而整個叠代的過程，就是在尋求方程R = AR的解，而無論是多少，叠代無限多次之後，壹定會取得令R = AR成立的R值，整個求解R的過程，就如同壹個人在壹張地圖上的不同位置之間隨機地行走壹樣，所以被稱為“隨機行走模型”。
隨機行走模型有壹個顯著的特點，那就是每壹次叠代的結果只與前壹次有關，與更早的結果完全無關，這種過程又被稱為馬爾可夫過程（Markov Process）或馬爾可夫鏈（Markov Chain）。
馬爾可夫過程的數學定義是：如果對於壹個隨機變量序列， 其中X n表示時間n的狀態及轉移概率P，有：
即只受的影響，則此過程成為馬爾可夫過程。其中稱作“壹步轉移概率”，而兩步、三步轉移概率則可以通過壹步轉移概率的積分求得。
當狀態空間有限時，轉移概率可以用用壹個矩陣A來表示，稱作轉移矩陣（transition matrix），此時轉移概率的積分即為矩陣的冪，k步轉移概率可以用表示，這也是隨機行走模型中的情況，而對於壹個正的（每個元素都為正的）轉移矩陣A ，可以證明壹定有：
這就完整解釋了為什麽的取值對最終結果沒有影響。
四、修正“懸掛網頁”帶來的不良影響
但是這裏有壹個問題：即便的取值對最終結果沒有影響，用R作為網頁排序的依據是否真的合理？
在馬海祥看來，這個其實並不合理，因為當壹個網頁只有鏈入鏈接沒有鏈出鏈接的時候，這個網頁就會像壹個“黑洞”壹樣，將同壹個連通子圖中其它網頁流向它的PageRank慢慢“吞掉”（因為算法中虛擬的用戶壹旦進入那樣的網頁，就會由於沒有對外鏈接而永遠停留在那裏），這種網頁我們稱之為“懸掛網頁”（Dangling Link）。
這種“黑洞”效應是如此顯著，以至於在壹個連通性良好的互聯網上，哪怕只有壹個“懸掛網頁”，也足以使整個互聯網的網頁排序失效，可謂是“壹粒老鼠屎壞了壹鍋粥”。
為了解決這個問題，佩奇和布林進行了修正，他們意識到，當用戶訪問到“懸掛網頁”時，都不可能也不應該就停留在了這個頁面，而是會自行訪問其它網頁。
雖然對每個用戶來說，自行訪問的網頁與各人的興趣有關，但馬海祥覺得從平均意義上來講，佩奇和布林假定用戶將會在整個互聯網上隨機選取壹個網頁進行訪問。
所以他們給PageRank算法加入了壹個新的向量E，它的作用是，按照其中所描述的比例來向全部網頁分配懸掛網頁每壹次“吞掉”的PageRank。
這樣，相當於為懸掛網頁添加了鏈向網絡上全部網頁的鏈接，避免了懸掛鏈接的出現。
以上就是谷歌背後最重要的PageRank算法奧秘，與以往那種憑借關鍵詞出現次數所作的排序不同，這種由所有網頁的相互鏈接所確定的排序是不那麽容易做假的，因為做假者再是把自己的網頁吹得天花亂墜，如果沒有真正吸引人的內容，別人不鏈接它，壹切就還是枉然。
而且“佩奇排序”還有壹個重要特點，那就是它只與互聯網的結構有關，而與用戶具體搜索的東西無關，這意味著排序計算可以單獨進行，而無需在用戶鍵入搜索指令後才臨時進行，谷歌搜索的速度之所以快捷，在很大程度上得益於此。
馬海祥博客點評：
最後，我要強調的壹點是，雖然PageRank是Google搜索結果排序的重要依據，並以此發家，不過它並不是全部依據，實際上，Google發展到現在，已同時用了數百種不同的算法來確定最終顯示給用戶的搜索結果順序。