PageRank

主要理解以下三点即可：

• 当一个网页被更多网页所链接时，其排名会越靠前；
• 排名高的网页应具有更大的表决权，即当一个网页被排名高的网页所链接时，其重要性也应对应提高。
• 先有鸡还是先有蛋问题

对于上面这三点个直觉，PageRank算法所建立的模型非常简单：一个网页的排名等于所有链接到该网页的网页的加权排名之和：

表示第个网页的PageRank值，用以衡量每一个网页的排名；若排名越高，则其PageRank值越大。网页之间的链接关系可以表示成一个有向图代表了网页链接到了网页; 为网页的出度，也可以看作网页的外链数。
假定为维PageRank值向量，为有向图所对应的转移矩阵，

n个等式（1）可以改写为矩阵相乘：

但是，为了获得某个网页的排名，而需要知道其他网页的排名，这不就等同于“是先有鸡还是先有蛋”的问题了么？幸运的是，PageRank采用power iteration方法破解了这个问题怪圈。本质就是给一个初始值，而后迭代至收敛。

PageRank 的简化模型

我假设一共有 4 个网页 A、B、C、D。它们之间的链接信息如图所示：

这里有两个概念你需要了解一下。出链指的是链接出去的链接。入链指的是链接进来的链接；实际上就是图论里的出度与入度。比如图中 A 有 2 个入链，3 个出链。在上面那个例子中，如果要对A进行估计，那么要找到A的入度集合，有B和C，但是B的出度有两个，因此对A的贡献只有１／２，对于C来说全部出度都给了Ａ。这样，我们可以得到 A、B、C、D 这四个网页的转移矩阵 ：

我们假设 A、B、C、D 四个页面的初始影响力都是相同的，即：

进行第一次转移之后，各页面的影响力 w1 变为：

然后我们再用转移矩阵乘以 w1 得到 w2 结果，直到第 n 次迭代后 wn 影响力不再发生变化，可以收敛到 (0.3333，0.2222，0.2222，0.2222），也就是对应着 A、B、C、D 四个页面最终平衡状态下的影响力。
　　你能看出 A 页面相比于其他页面来说权重更大，也就是 PR 值更高。而 B、C、D 页面的 PR 值相等。针对这个网页权重的计算模型还不够完善，主要有两个问题：

等级泄露

1. 等级泄露（Rank Leak）：如果一个网页没有出链，就像是一个黑洞一样，吸收了其他网页的影响力而不释放，最终会导致其他网页的 PR 值为 0。可以按照上面的计算公式，初始设置为1/4，经过一次更新后就变为了原来的一半，而C一直没有贡献，所以对应的那一列为0，多次迭代后也会导致其它页面为0 。

   等级沉没

2. 等级沉没（Rank Sink）：如果一个网页只有出链，没有入链（如下图所示），计算的过程迭代下来，会导致这个网页的 PR 值为 0（也就是不存在公式中的 V）。这种情况看上去感觉影响小一点，只是自己页面最后变为0。
   实际上也是为了解决一些特殊的情况，比如之前在朴素贝叶斯里，或者是TF－IDF里都加了平滑，就是为了避免因为一个特殊例子使得整个式子的计算结果为0 。

   PageRank 的随机浏览模型

   为了解决简化模型中存在的等级泄露和等级沉没的问题，拉里·佩奇提出了 PageRank 的随机浏览模型。他假设了这样一个场景：用户并不都是按照跳转链接的方式来上网，还有一种可能是不论当前处于哪个页面，都有概率访问到其他任意的页面，比如说用户就是要直接输入网址访问其他页面，虽然这个概率比较小。
   所以他定义了阻尼因子 d，这个因子代表了用户按照跳转链接来上网的概率，通常可以取一个固定值 0.85，而 1-d=0.15 则代表了用户不是通过跳转链接的方式来访问网页的，比如直接输入网址。

因为加入了阻尼因子 d，一定程度上解决了等级泄露和等级沉没的问题， 只要阻尼因子不为1，则最后计算的肯定不为0。