昨天在Google黑板報上讀到了一篇介紹Page Rank的文章，最讓我感興趣的是它的數(shù)學模型。Google 的創(chuàng)始人之一拉里?佩奇在談到怎么想到網(wǎng)頁排名算法時說：“當時我們覺得整個互聯(lián)網(wǎng)就像一張大的圖 （Graph），每個網(wǎng)站就像一個節(jié)點，而每個網(wǎng)頁的鏈接就像一個弧。我想，互聯(lián)網(wǎng)可以用一個圖或者矩陣描述，我也許可以用這個發(fā)現(xiàn)做個博士論文?！?/p>
事實上，“Google 的兩個創(chuàng)始人拉里?佩奇 （Larry Page ）和謝爾蓋?布林 (Sergey Brin) 把這個問題變成了一個二維矩陣相乘的問題，并且用迭代的方法解決了這個問題?！敝劣谒麄兪侨绾伟堰@個問題轉(zhuǎn)化成矩陣相乘的，文中并沒有詳細介紹。我google了一下，發(fā)現(xiàn)了這兩人在斯坦福大學的博士論文，文中介紹了PageRank的數(shù)學定義：
We assume page A has pages T1...Tn which point to it (i.e., are citations). The parameter d is a damping factor which can be set between 0 and 1. We usually set d to 0.85. There are more details about d in the next section. Also C(A) is defined as the number of links going out of page A. The PageRank of a page A is given as follows:
PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))
Note that the PageRanks form a probability distribution over web pages, so the sum of all web pages" PageRanks will be one.
假設指向頁面A的頁面有T1...Tn共n個頁面，C(Ti)指的是頁面Ti指向外界的鏈接數(shù)，d是一個常數(shù)。PR(Ti)/C(Ti)指的是頁面Ti本身的PageRank分配給A的一份。(1-d)只是為了讓所有網(wǎng)頁的PageRank服從概率分布。這個公式具體的解釋可以參考這個鏈接。
因為一開始所有的頁面并沒有PageRank，所以這個公式需要迭代多次才能使PageRank值穩(wěn)定下來。黑板報的這篇文章提到這點時說到：“他們先假定所有網(wǎng)頁的排名是相同的，并且根據(jù)這個初始值，算出各個網(wǎng)頁的第一次迭代排名，然后再根據(jù)第一次迭代排名算出第二次的排名。他們兩人從理論上證明了不論初始值如何選取，這種算法都保證了網(wǎng)頁排名的估計值能收斂到他們的真實值?！?/p>
好了公式有了，但好像還是看不出和矩陣有什么關系。實際上，每一個網(wǎng)頁都對應于一個二維矩陣的第i行和第i列，如果網(wǎng)頁j指向網(wǎng)頁i，并且網(wǎng)頁i是網(wǎng)頁j的n個鏈接之一，則矩陣的第i行第j列的值就為1/n，否則就為0。這也就是黑板報的文章提到的“如果我們假定有十億個網(wǎng)頁，那么這個矩陣就有一百億億個元素?！碑斎贿@個矩陣中大部分元素都為0，所以“拉里和謝爾蓋兩人利用稀疏矩陣計算的技巧，大大的簡化了計算量，并實現(xiàn)了這個網(wǎng)頁排名算法?！?/p>
矩陣建立之后，PageRank值其實就是這個矩陣的主特征向量。具體的例子可以參考這篇PDF文檔。當時看到這里我就納悶，既然是特征向量為什么不直接計算反而要迭代呢，后來一想怎么求10億*10億的矩陣的特征向量，可能還是迭代計算簡單方便。
不管具體的實現(xiàn)怎樣，這個算法真正的突破在于文中所說的，“網(wǎng)頁排名的高明之處在于它把整個互聯(lián)網(wǎng)當作了一個整體對待。它無意識中符合了系統(tǒng)論的觀點。相比之下，以前的信息檢索大多把每一個網(wǎng)頁當作獨立的個體對待，很多人當初只注意了網(wǎng)頁內(nèi)容和查詢語句的相關性，忽略了網(wǎng)頁之間的關系?！眱晌粍?chuàng)始人的數(shù)學建模能力和想象力在這里發(fā)揮了關鍵作用。
回想前些天，孟巖老師貼了兩篇文章探討數(shù)學的重要性：數(shù)學與算法隨想和技術圖書與數(shù)學教育 。大家還在對數(shù)學的重要性爭論不休，PageRank這個例子相信很有說服力。對于數(shù)學的作用，我很喜歡這篇文章中的比喻：一個運動員總要進行跑步和負重訓練以增強體質(zhì)磨練心智；和運動員一樣，計算機專業(yè)的學生也應該通過數(shù)學思維的磨練以增強從細節(jié)中抽象的能力以及解決問題的創(chuàng)造力。
來自：http://blog.csdn.net/rideronstorm/archive/2006/02/28/612151.aspx
