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);        }        //当没