PageRank 演算法的複雜程度怎麼樣？

01-03

我來科普一下Google的PageRank演算法吧！

不對之處，還望大家指教啦。

在PageRank發明之前，搜索引擎採用的還是最原始的關鍵字匹配技術，於是呢在搜索結果中經常會遇到「掛羊頭賣狗肉」的垃圾網站，對這些網站，當時的Yahoo採用還是人工清理的方法。這時候Google的兩位創始人Page和Brin就在想，有沒有一種演算法，能夠給出網頁重要性的排序呢？這樣就可以優先推薦重要網頁，而讓那些垃圾網頁石沉大海了。

Page和Brin發現，網頁的超鏈接結構中就蘊含了重要程度的信息。由於一個網頁的超鏈接指向的主要是與其內容相關的網頁，那麼我們不難想像，如果有許多網頁都同時指向某一個網頁，這個網頁就一定非常重要。

我們將互聯網想像成一個流網路，網路的節點就是一個個網頁，如果兩個網頁間存在超鏈接的關係，那麼它們之間就存在一條有向的連邊。想像存在一種貨幣，它們在這個流網路上隨機地流動，在任意時刻，每個網頁上都會有貨幣流入，也會有貨幣流出，當最終達到穩定時，將每個網頁持有的貨幣存量，或者說「財富」的多寡由大到小排序，就得到了網頁重要性的排序PageRank。我們發現排在前面的主要是被較多引用的網頁，當然有幸被重要網頁引用的網頁也會得到較大的PageRank值。

當然我們還要考慮這樣一種情況，如果遇到不引用任何其他網頁的「鐵公雞」，或者網頁A僅引用B，B僅引用C，C又僅引用A的「小團體」，貨幣只會流入不會流出，他們會積累大量的貨幣，但顯然他們不一定是最重要的。

為避免這樣的情況發生，PageRank還使貨幣可以以概率e跳到系統中的任意其他節點。或者我們可以想像系統中存在一個「中央政府」，它在每一時刻都從各個網頁節點的「財富」中征繳比例為e的「稅金」，然後再平均分給每一個網頁。

好啦，規則就是這樣，那各個網頁的PageRank值怎麼計算呢？

設 $x_{i}$ 為各個節點（網頁）的貨幣存量，並令 $sum_{1}^{N}{x_{i} }=1$ ，其中N為節點數。

$frac{dx_{i} }{dt} =F_{in}-F_{out}$ ，其中 $F_{in}$ 表示貨幣流入量， $F_{out}$ 表示貨幣流出量。進而：

$frac{dx_{i} }{dt}=(1-e)(p_{i1}x_{1}+p_{i2}x_{2}+cdot cdot cdot +p_{iN}x_{N})+frac{e}{N}-(1-e) x_{i}-ex_{i}$

其中， $p_{ij}$ 為貨幣有 $j$ 節點流向 $i$ 節點的概率，顯然 $p_{ij}$ 等於1/ $j$ 節點的連邊數。

於是， $(1-e)(p_{i1}x_{1}+p_{i2}x_{2}+cdot cdot cdot +p_{iN}x_{N})$ 為貨幣流入量中的從其他節點流入節點 $i$ 部分， $frac{e}{N}$ 為由「中央政府」贈與的部分（我們已令 $sum_{1}^{N}{x_{i} }=1$ ）， $(1-e) x_{i}$ 為貨幣流出量中由 $i$ 流向其他節點部分， $ex_{i}$ 為「上繳」的「稅金」。

化簡上式可得：

$frac{dx_{i} }{dt}=(1-e)(p_{i1}x_{1}+p_{i2}x_{2}+cdot cdot cdot +p_{iN}x_{N})+frac{e}{N}-x_{i}$

我們令 $X=(x_{1},...,x_{N})^{T}$ ， $A=left( p_{ij} ight)$ ， $1=(1,...,1)^{T}$ ，則有

$frac{dX}{dt}=(1-e)AX+frac{e}{N}1-X =((1-e)A-I)X+frac{e}{N}1$

求方程的穩定解，即讓 $frac{dX}{dt}=0$ ，得到：

$X=(I-(1-e)A)^{-1} frac{e}{N}1$

由於 $X$ 的列和為1，所以上式存在更簡單的解法：

$X=(1-e)AX+frac{e}{N}1 =((1-e)A+frac{e}{N}1_{N imes N} )X=UX$

$UX=X$ ，因此 $X$ 為矩陣 $U$ 特徵值1的特徵向量，可以快速求解。

所以，大家看到了，PageRank非常簡單。正如另一位知友所說：

主要的挑戰來自海量的數據

PR演算法模型十分簡單，簡單說來就是求Markov轉移概率矩陣，通過迭代求該矩陣的最大特徵值。引入阻尼係數主要是為了提供一個PR的下限，使「零鏈入頁面」也有其網頁價值（PR值）。不得不承認PR是一個天才級別的演算法，因為其核心簡單、實現容易，即使放到海量數據的今天，PR也能夠很容易在並行框架下實現。不過Google早就大幅降低PR在其SEO中的地位，主要問題還是PR值本身能夠反映出的網頁價值不精確。在各行業越來越注重精準營銷的今天，PR註定要被淘汰，這也是為什麼TR能夠逐步取代PR在SEO地位的原因了。

記得演算法是求Markov鏈的轉移概率矩陣，再求其平穩分布，演算法簡單，但海量數據計算難。

大概就是迭代求矩陣的最大特徵值, 只是為了收斂和穩定, 加入了阻尼因子.

拋開PageRank的演算法複雜度不談，PageRank這個演算法其實還是挺有意思的，因此最近寫了一篇有關PageRank的文章：Graph Analysis and Its Application，介紹了經典的PageRank演算法和原理。也會介紹圖上的聚集係數（Clustering Coefficient），連通分支（Connected Component），強連通分支（Strongly Connected Component）等內容。

一點兒都不複雜，但是作用也非常有限，不要相信 Google 對用戶宣稱的那樣神奇。

pagerank演算法實現本身不難，10分鐘也就寫出來了，海量數據的時候會相對麻煩一點，但有hadoop之類的工具也不難實現。

PR是個簡單有效的演算法，內涵比較有意思，現在改進演算法也很多了，例如trustrank等。

PageRank在演算法和數學上並不複雜，具體描述可見http://en.wikipedia.org/wiki/PageRank 。在做web級別的計算時，主要的挑戰來自海量的數據，需要有大規模並行計算技術的支持。因為PageRank存在的缺陷，現已為更高級的模型（可參見HITS和TrustRank）取代。

PageRank演算法本身很容易理解，但求解過程、結果唯一與穩定的證明比較複雜，需要一定的數學功底

PageRank的求解就是求鏈接矩陣的特徵向量，小量數據可以使用冪運算迭代的方式求解，大數據集的話需要採用分解矩陣等並行計算方式進行處理。

基本知識點包括線性代數，圖論，馬爾可夫等概率的知識，數值計算等

現在Google用的專家維護的決策樹來調整排序 PR影響越來越小

現在都讓站長們不要太關注PR值了，但是流量交易里PR值還是個很重要的參考因素。