PageRank 計算博客園用戶排名

PageRank 通過網頁與網頁之間的鏈接關系計算各網頁權重，一般權重高的網頁特點是：鏈接向它的網頁數量多、鏈向它的網頁其權重也較高。PageRank 就是通過這樣的連接關系，一輪輪迭代計算后得出各網頁的權重。

思路拓展一下，其實人與人之間也是連接著的，在社會的人際關系網中，每個人的社會地位和身價也是不同的。以微博為例，我們都有關注者和粉絲（類似網頁之間的鏈接），可以發現所謂的“大V”基本上粉絲數量多，并且粉絲里不乏很多其他“大V”，所以這個帳號的價值就大。

同樣博客園也具有類似的社交關系，用戶可以選擇“關注的人”以及“關注我的人”，理論上是可以用 PageRank 算法算出哪些用戶更受大家歡迎，于是本文代大家八卦了一下，文章較長，只想看排名的同學請直接拉到末尾。。。

PageRank 算法簡介

1. 數學模型

《數學之美》第10章的延伸閱讀部分，對 PageRank 的計算方法進行了簡單介紹，但原書有些錯誤，修改后描述如下：

我們設向量 B 為第一、第二…第N個網頁的網頁排名

矩陣 A 代表網頁之間的權重輸出關系，其中 amn 代表第 m 個網頁向第 n 個網頁的輸出權重。

輸出權重計算較為簡單：假設 m 一共有10個出鏈，指向 n 的一共有2個，那么 m 向 n 輸出的權重就為 2/10。

現在問題變為：A 是已知的，我們要通過計算得到 B。

假設 Bi 是第 i 次迭代的結果，那么

初始假設所有網頁的排名都是 1/N （N為網頁總數量），即

通過上述迭代計算，最終 Bi 會收斂，即 Bi 無限趨近于 B，此時 B = B × A。

2. 具體示例

假設有網頁A、B、C、D，它們之間的鏈接關系如下圖所示

計算 B1 如下：

不斷迭代，計算結果如下：

第 1次迭代: 0.125, 0.333, 0.083, 0.458 第 2次迭代: 0.042, 0.500, 0.042, 0.417 第 3次迭代: 0.021, 0.431, 0.014, 0.535 第 4次迭代: 0.007, 0.542, 0.007, 0.444 第 5次迭代: 0.003, 0.447, 0.002, 0.547 第 6次迭代: 0.001, 0.549, 0.001, 0.449 第 7次迭代: 0.001, 0.449, 0.000, 0.550 第 8次迭代: 0.000, 0.550, 0.000, 0.450 第 9次迭代: 0.000, 0.450, 0.000, 0.550 第10次迭代: 0.000, 0.550, 0.000, 0.450 ... ...

我們可以發現，A 和 C 的權重變為0，而 B 和 D 的權重也趨于在 0.5 附近擺動。從圖中也可以觀察出：A 和 C 之間有互相鏈接，但它們又把權重輸出給了 B 和 D，而 B 和 D之間互相鏈接，并不向 A 或 C 輸出任何權重，所以久而久之權重就都轉移到 B 和 D 了。

PageRank 的改進

上面是最簡單正常的情況，考慮一下兩種特殊情況：

第一種情況是，B 存在導向自己的鏈接，迭代計算過程是：

第 1次迭代: 0.125, 0.583, 0.083, 0.208 第 2次迭代: 0.042, 0.833, 0.042, 0.083 第 3次迭代: 0.021, 0.931, 0.014, 0.035 第 4次迭代: 0.007, 0.972, 0.007, 0.014 第 5次迭代: 0.003, 0.988, 0.002, 0.006 第 6次迭代: 0.001, 0.995, 0.001, 0.002 第 7次迭代: 0.001, 0.998, 0.000, 0.001 第 8次迭代: 0.000, 0.999, 0.000, 0.000 第 9次迭代: 0.000, 1.000, 0.000, 0.000 第10次迭代: 0.000, 1.000, 0.000, 0.000 ... ...

我們發現最終 B 權重變為1，其它所有網頁的權重都變為了0 =。=!

第二種情況是 B 是孤立于其它網頁的，既沒有入鏈也沒有出鏈，迭代計算過程是：

第 1次迭代: 0.125, 0.000, 0.125, 0.250 第 2次迭代: 0.063, 0.000, 0.063, 0.125 第 3次迭代: 0.031, 0.000, 0.031, 0.063 第 4次迭代: 0.016, 0.000, 0.016, 0.031 第 5次迭代: 0.008, 0.000, 0.008, 0.016 第 6次迭代: 0.004, 0.000, 0.004, 0.008 第 7次迭代: 0.002, 0.000, 0.002, 0.004 第 8次迭代: 0.001, 0.000, 0.001, 0.002 第 9次迭代: 0.000, 0.000, 0.000, 0.001 第10次迭代: 0.000, 0.000, 0.000, 0.000 ... ...

我們發現所有網頁權重都變為了0 =。=!

出現這種情況是因為上面的數學模型出現了問題，該模型認為上網者從一個網頁瀏覽下一個網頁都是通過頁面的超鏈接。想象一下正常的上網情景，其實我們在看完一個網頁后，可能直接在瀏覽器輸入一個網址，而不通過上一個頁面的超鏈接。

我們假設每個網頁被用戶通過直接訪問方式的概率是相等的，即 1/N，N 為網頁總數，設矩陣 e 如下：

設用戶通過頁面超鏈接瀏覽下一網頁的概率為 α，則直接訪問的方式瀏覽下一個網頁的概率為 1 - α，改進上一節的迭代公式為：

通常情況下設 α 為0.8，上一節”具體示例”的計算變為如下：

迭代過程如下：

第 1次迭代: 0.150, 0.317, 0.117, 0.417 第 2次迭代: 0.097, 0.423, 0.090, 0.390 第 3次迭代: 0.086, 0.388, 0.076, 0.450 第 4次迭代: 0.080, 0.433, 0.073, 0.413 第 5次迭代: 0.079, 0.402, 0.071, 0.447 第 6次迭代: 0.079, 0.429, 0.071, 0.421 第 7次迭代: 0.078, 0.408, 0.071, 0.443 第 8次迭代: 0.078, 0.425, 0.071, 0.426 第 9次迭代: 0.078, 0.412, 0.071, 0.439 第10次迭代: 0.078, 0.422, 0.071, 0.428 第11次迭代: 0.078, 0.414, 0.071, 0.437 第12次迭代: 0.078, 0.421, 0.071, 0.430 第13次迭代: 0.078, 0.415, 0.071, 0.436 第14次迭代: 0.078, 0.419, 0.071, 0.431 第15次迭代: 0.078, 0.416, 0.071, 0.435 第16次迭代: 0.078, 0.419, 0.071, 0.432 第17次迭代: 0.078, 0.416, 0.071, 0.434 第18次迭代: 0.078, 0.418, 0.071, 0.432 第19次迭代: 0.078, 0.417, 0.071, 0.434 第20次迭代: 0.078, 0.418, 0.071, 0.433 ... ...

PageRank 算法實現

互聯網的網頁數量是 Billion 級別的，所以不可能一下子初始化矩陣 A ，試想一下 10億 × 10億 的矩陣是什么概念！

這時就用到稀疏矩陣了，定義稀疏矩陣的結構如下（其實是稀疏矩陣的一行）：

public class SparseMatrix<T>{    public SparseMatrix(T head, double rank)    {        Head = head;        LinkedItems = new List<T>();        Rank = rank;    }    /// <summary>    ///     稀疏矩陣頭    /// </summary>    public T Head { get; PRivate set; }    public double Rank { get; set; }    /// <summary>    ///     稀疏矩陣鏈接的項目    /// </summary>    public List<T> LinkedItems { get; set; }    public void AddLink(T linkedItem)    {        LinkedItems.Add(linkedItem);    }}

第一節中的鏈接示例圖，就可以用如下代碼表示：

Dictionary<char, SparseMatrix<char>> matrix = new Dictionary<char, SparseMatrix<char>> {    {'A', new SparseMatrix<char>('A', 0.25){LinkedItems = new List<char>{'B', 'C', 'D'}}},    {'B', new SparseMatrix<char>('B', 0.25){LinkedItems = new List<char>{'D'}}},    {'C', new SparseMatrix<char>('C', 0.25){LinkedItems = new List<char>{'A', 'D'}}},    {'D', new SparseMatrix<char>('D', 0.25){LinkedItems = new List<char>{'B'}}}};

通過稀疏矩陣計算，與原先的整個矩陣行列式計算有較大不同，計算次序已經發生了變化。原先矩陣是一行乘以權重的豎列，稀疏矩陣則變為類似于按原先矩陣的豎列與權重相乘。矩陣運算中當然不允許 1 × N 矩陣與 1 × N 矩陣相乘的情況，我們能做的就是先將一項項算好，比如先算 A 這一行，算出 A 給 B、C、D輸出多少權重，在一個類似字典類型的數據結構里，給 B、C和 D 各加上一筆，像是一個 Map-Reduce 過程。

public class MapReduce<T>{    private readonly Dictionary<T, double> _map;    public MapReduce()    {        _map = new Dictionary<T, double>();    }    public double Reduce(T key, double value)    {        if (_map.ContainsKey(key))        {            _map[key] += value;            return _map[key];        }        _map.Add(key, value);        return value;    }    public double GetOrSetDefaultValue(T key)    {        if (_map.ContainsKey(key))            return _map[key];        _map.Add(key, 0.0);        return 0.0;    }}

PageRank 設計如下：

public class PageRank<T>{    private MapReduce<T> _mapReduce;    private readonly double _stayProbability;    private readonly double _averageRank;    /// <summary>    ///     /// </summary>    /// <param name="totalCount">項目總數</param>    /// <param name="stayProbability">保持留在某個項目, 不跳轉的概率</param>    public PageRank(int totalCount, double stayProbability = 0.8)    {        _mapReduce = new MapReduce<T>();        _stayProbability = stayProbability;        _averageRank = 1.0 / totalCount;    }    /// <summary>    ///     計算下一輪PageRank    /// </summary>    public void NextCircle()    {        _mapReduce = new MapReduce<T>();    }    /// <summary>    ///     計算一條行列式    /// </summary>    /// <param name="sparseMatrix">稀疏矩陣</param>    public void Calc(SparseMatrix<T> sparseMatrix)    {        var outputRank = 1.0 / sparseMatrix.LinkedItems.Count;        foreach (var item in sparseMatrix.LinkedItems)        {            _mapReduce.Reduce(item,                _stayProbability * outputRank * sparseMatrix.Rank);        }        //當沒