20世紀90年代，谷歌公司上市并很快成為具影響力的搜索引擎。谷歌的脫穎而出要歸功于它所提供的搜索結果總會把一些“好東西”排在前面，方便用戶搜索。與此形成強烈對比的是，如果利用其它搜索引擎，你需要遍歷所有搜索結果（包含很多無關信息），從而得到你想獲取的信息和資源。谷歌背后的神奇之處就在于PageRank算法。PageRank算法將每個網頁的重要性進行量化，從而使其具有可排序性（建立了偏序關系），這樣使用戶更早地獲取到重要、相關的網頁信息。
我們如果能了解PageRank的計算方法，就可以合理的設計網頁，從而獲取更多的訪問量和點擊量。事實也是如此，由于谷歌在搜索方面的主導地位，它的排序系統對于整個互聯網的發展和架構起到了重要的影響。這篇文章將解釋谷歌計算網頁重要性排序的核心思想。這個核心思想又必然地成為了線性代數的華麗的應用。
一個搜索引擎需要做以下三件事情：
本文著重分析第三步。在一個互連的網絡中，如何定義并且合理量化網頁的重要性呢？
在這一部分，我們用“重要性得分”或者“得分”來度量某個網頁的在網絡中的重要性。顯然，重要性得分一定是一個非負實數。我們的核心思想是：給定任意一個網頁，它的得分應該和其他網頁與其鏈接的鏈接數緊密相關（更準確地說是正相關）。這些鏈接被稱為該給定網頁的后向鏈接。可以想象，這樣一來，整個網絡形成了一種民主投票機制：網頁得票數越多（后向鏈接數越多），它就將被視為越重要。
不失一般性地，我們考查某一個包含n個網頁的網絡，每個網頁按序號記為正整數k，1<=k<=n. 如圖2.1給出了一個例子，該網絡包含四個網頁，箭頭從1指向4代表網頁1有到網頁4的鏈接，其他箭頭同理。這樣的網在數學上是一個有向圖。網頁k的得分記為xk，則xk是一個非負實數，并且xj>xk表示網頁j的重要性高于網頁k。注意到xj=0表示網頁j具有低的重要性得分。
根據我們的核心思想（給定任意一個網頁，它的得分應該和其他網頁與它鏈接的鏈接數成正相關），我們很容易想到用網頁k的后向鏈接數作為網頁k的重要性得分。因此，在圖2.1所給的例子中，我們有x1=2,x2=1,x3=3,x4=2。排序后可知，網頁3重要，網頁1和4并列第二，網頁2不重要。可以想象，網頁k的一個后向鏈接就好比是對于網頁k的重要性的一票。
然而，這種簡單粗暴的方法忽略了一個對于排序算法來說非常重要的特性，即，給定網頁k，來自一個重要性很高的網頁的鏈接會比一個來自不太重要的網頁的鏈接更多地提升網頁k的重要性。比如，對于你的個人主頁，來自雅虎網頁的鏈接應該比一個來自www.kurtbryan.com網頁的鏈接更大程度上提升你個人主頁的重要性。再比如，對于圖2.1所示的網絡中，網頁1和網頁4都有兩個后向鏈接：網頁1的后向鏈接來自網頁4和看起來比較重要的網頁3，網頁4的后向鏈接來自網頁2和相對不那么重要的網頁1. 由此，我們得到的重要性排序結果應該網頁1高于網頁4。
為了引入這個重要思想，我們重新定義重要性計算公式。對于網頁j，其重要性得分定義為其所有后向鏈接網頁的得分的總和。舉個例子，我們重新考慮圖2.1所示的網絡。網頁1的得分為x1=x3+x4。注意到，由于x3和x4又同時依賴于x1，因此這種定義方式看起來是一種自引用的模式。正如在一項選舉中，我們不希望某一個候選人僅僅通過給其他人投更多的票數來間接地得到更多的影響力。同樣地，我們不希望一個網頁僅僅簡單地通過鏈接了更多其他的網頁而獲取額外的影響力（或者說重要性）。因此我們還需對剛剛的定義稍作修改。假設網頁j包含nj個鏈接，其中一個鏈接指向網頁k，那么這個鏈接將對網頁k的重要性得分貢獻xj/nj，而不是xj。由此，我們正式給出重要性得分的定義。對于一個包含n個網頁的網絡，記Lk ? {1,2,…,n}為具有指向網頁k的鏈接的網頁的集合，即Lk為網頁k的后向鏈接網頁的集合。那么對于每一個k，我們定義其重要性得分。
其中nj為網頁j的出度個數（注意到，nj一定是正整數，因為j屬于Lk）。同時我們還假設，自環不會對重要性得分有貢獻。也就是說，如果回到我們的比喻中，在這樣一個民主投票機制下，我們不允許自投票。
下面，讓我們將定義用在圖2.1的例子中去。我們很容易得到如下方程組，
接下來，我們開始使用高級的數學工具了—線性代數和矩陣，這將會使整個事情變得簡明、優美、清晰，我們定義重要性得分向量x=[x1 x2 x3 x4]T, 我們很容易將上面的方程組寫成矩陣的形式Ax=x，其中
熟悉線性代數的讀者們會豁然開朗（不熟悉的讀者可以回顧：方陣A的特征值λ和特征向量x滿足方程Ax=λx，其中x不等于0向量），所有求解的重要性得分向量就是在求解矩陣A的特征值為1的特征向量。我們將這樣的矩陣A稱為給定網絡的鏈接矩陣。
利用線性代數的知識（計算A-I的行列式，令行列式=0，求解特征根，再求解每一個特征根對應的齊次方程組），我們很容易求解A的特征值為1所對應的特征向量，為任意實數倍的[12 4 9 6]T。由于任意非0實數倍的特征向量還是特征向量，因此我們可以規定將重要性得分向量按照一范數歸一化，使分量的和為1. 在這個例子中，x1=12/31=0.386, x2=4/31=0.129, x3=9/31=0.290, x4=6/31=0.194. 注意到這種計算方式和簡單的統計后向鏈接數大不相同。另一個值得注意的方面是，表面上來看，被其他所有網頁鏈接的網頁3，出乎意料地，不是具有高重要性得分的網頁。為了理解這個現象，我們需要注意到網頁3僅僅鏈接網頁1，所以網頁3會將所有得票匯集貢獻給網頁1，這樣的一種“間接”投票（或者說影響）使得網頁1得到更高的票數（重要性得分）。
然而，在這個例子中，鏈接矩陣A具有特征值為1的特征向量并不是巧合。在數學上，我們可以嚴格證明，對于沒有孤立點（出度為0的網頁節點）的網，其鏈接矩陣A是一定存在特征值為1的特征向量的。這是由于鏈接矩陣的列和為1導致的！下面我們來嚴格證明這個優美的結論。首先我們需要給出馬爾科夫鏈中的一個定義：
定義2.1 一個方陣被稱為列隨機矩陣當且僅當它的所有元素都為非負且列和（按列加和所有元素）為1。
我們下面來證明定理1.
定理1. 任意列隨機矩陣A都有特征值為1的特征向量。
證明：我們要想辦法利用到列和為1這一重要性質。注意到，列和為1這一性質用矩陣乘法做形式化可以得到ATe=e,
其中e為全1列向量。這意味著ATx=x有非零解，等價于(AT-I)x=0有非零解，等價于det(AT-I)=0,
等價于det(A-I)=0,
等價于Av=v有非零解，即A有特征值為1的特征向量。證畢。證明過程中如果利用A和AT的具有相同的特征向量（本質上由于行列式按行展開和列展開會具有相同的多項式形式）的這一結論可以簡化證明。
在后面的討論中，我們用V1(A)來表示列隨機矩陣A的特征值為1所對應的特征向量所張成的特征空間。
利用式(2.1)來定義給定網頁在網絡中的重要性得分會存在兩個問題：1.網頁排序不；2.存在孤立節點。
網頁排序不
到目前為止，在我們所做的一切假定和定義下，如果所得到的特征空間的維數為1（即，該特征空間的基的個數為1），那么我們就可以通過歸一化找到一個特征向量作為重要性得分向量，這是我們期待的好情況，圖2.1所示的網正是如此。但是，情況并不總是這樣。事實上可以證明對于一個強連接的網（任意兩個節點在有限步可達），這樣的解是的。
我們容易找出網頁排序不的例子（鏈接矩陣的特征值為1所對應的特征空間維數大于1）：
對于這樣的鏈接矩陣A，我們可以計算V1(A)是二維的，它的兩個基分別是x=[?,?, 0, 0, 0]T, y=[0, 0, ?, ?, 0]T. 事實并不是只有兩種排序那么簡單，注意到基間的任意線性組合(lambda x + mu y, lambda,mu屬于數域K)還是屬于V1(A)（線性空間的封閉性），這樣我們就會得到無窮且不可數的排序，而且選擇哪一種排序更好并不顯然！
更一般地，對于一個無向網W來說，假設它是由r個不連通子網組成，分別記為W1,…,Wr,那么就有dim(V1(A))>=r, 因此就導致有無窮多個特征向量可以成為重要性得分向量。這在直觀上也很容易理解：對于這r個互相不連通的子網絡來說，各自成體系，要比較來自兩個子網絡的網頁重要性自然很困難。
為數學的崇尚者，我們需要把這種直觀轉化成嚴格的數學證明。假設給定網W有n個網頁，包含r個子網絡W1,…,Wr. 記ni為Wi所包含的網頁個數。因此該網W的鏈接矩陣就形如一個分塊對角結構
其中Ai為Wi的鏈接矩陣，每個Ai是ni x ni的列隨機矩陣，因此每個Ai都有的特征值為1所對應的歸一化后的特征向量vi屬于Rni，我們將它們拼接在一塊可以得到整個矩陣A的特征值為1的一系列特征向量。
很容易證明這些特征向量wi是線性無關的，因此整個特征空間V1(A)至少是由這些特征向量張成的，即V1(A)>=r。
孤立點
另一個問題就是孤立點的存在。如果一個網中存在孤立點，那么這個網所對應的鏈接矩陣就包含一個或者多個全零列。在這種情況下，我們稱A為列次隨機，即它的列和都是小于或者等于1的。可以證明這樣矩陣的特征值都是小于或等于1的。然而，孤立點的存在不會阻礙我們利用類似的方法對網頁進行排序。其中涉及到的一些困難，本文不予論述了。
對于一個包含幾十億網頁的網絡來說，為鏈接矩陣計算一次特征向量需要大量的計算資源。因此我們設計的算法好可以只產生的網頁排名。但是通常情況下，網是不連通的，包含很多的彼此不連通的子網絡，根據前面的分析，對于這樣的網絡鏈接矩陣的特征值為1的特征向量有無窮多個。這就帶來了技術上的矛盾和困難。
下面我們會針對這個問題，引入一個調整方案，從而有效的克服這個困難。這個方案實際上是Perron-Frobenius定理的特例。
改進鏈接矩陣A
對于包含n個網頁的網絡，我們定義S是n階方陣，每個元素都是1/n. 很容易證明S矩陣是列隨機矩陣，并且V1(S)是一維的。我們定義矩陣M為
其中0<=m<=1. M矩陣其實就是A和S的加權平均。m是超參，谷歌原始的設置是0.15. 對于任意0<=m<=1, M是列隨機矩陣，我們還可以證明對于任意0
在實際應用中，我們并不總需要得到精確的重要性得分，只就意味著，我們不需要利用傳統計算特征值的方法來得到重要性得分向量。事實上我們可以利用冪方法來計算M矩陣特征向量的數值解。該方法的思想如下：初始化x0, 開始進行迭代xk=Mx(k-1)… 當k趨于無窮大時，xk就可以作為M的大特征值對應的特征向量。
為了利用冪方法，我們需要知道，除1以外，M的的其他所有特征值的絕對值都小于1. 我們下面來通過兩個定理說明利用冪方法的合理性。
定理4. M是n階正列隨機矩陣，V是Rn的一個子空間，V={v, \sum_j{v_i}=0}. 對于任意v屬于V，我們有Mv也屬于V，且
其中c滿足
證明略。
定理5. 任意正列隨機矩陣M都有的正向量q滿足Mq=q, 其中q的一范數為1. q可以通過計算
對于任意初始化x0，x0是正向量且滿足x0的一范數為1。
證明：
x0是Rn空間的正向量，且滿足x0的一范數為1. 則x0=q+v其中v屬于V。因此我們有
又因為
其中0<=c<1. 所以，
因此limk Mkx0 = q.
我們推導了PageRank的排序公式和算法原理，對于網頁排序不的情況，給出了改進方案。后給出了一種數值結算重要性得分的算法，并說明算法的合理性。從這些嚴謹的證明推導中，我們可以看到谷歌驚人的價值來源于背后漂亮優美的數學原理，這是數學思想的又一次完美體現！
本站文章版權歸原作者及原出處所有 。內容為作者個人觀點， 并不代表本站贊同其觀點和對其真實性負責，本站只提供參考并不構成任何投資及應用建議。本站是一個個人學習交流的平臺，網站上部分文章為轉載，并不用于任何商業目的，我們已經盡可能的對作者和來源進行了通告，但是能力有限或疏忽，造成漏登，請及時聯系我們，我們將根據著作權人的要求，立即更正或者刪除有關內容。本站擁有對此聲明的最終解釋權。
