PageRank算法简介（PageRank算法）

PageRank算法简介（PageRank算法）

我们经常需要在网上去查一些东西，但是面对互联网的海量信息，究竟要优先显示哪一个结果呢？这就需要对网页进行一个排序，也就是今天要讲的，谷歌的网页排序算法 PageRank。

这里首先需要说明一点，PageRank 并不是第一个网页排名算法，但是它是网页排名算法的第一个出圈之作。

什么是 PageRank？

我们现在去网页上随便搜一个什么东西，比如搜一下 51CTO，（只是在这里举个例子，现在的网页排序已经不单纯是 PageRank 了）

有关 51CTO 的搜索结果从上边可以看到有2440000条，但是要优先显示哪些内容呢？怎么才能给出用户最可能想要的结果呢？

谷歌的创始人 Lawrence Page（拉里·佩奇）和 Sergey Brin（谢尔盖·布林）找到了一个完美的可以计算网页排名的数学模型。

如何计算 PageRank？

那如何获得网页排名呢？

假设互联网是一个有向图，在其基础上定义随机游走模型，即一阶马尔可夫链，表示网页浏览者在互联网上随机浏览网页的过程。假设浏览者在每个网页依照连接出去的超链接以等概率跳转到下一个网页，并在网上持续不断进行这样的随机跳转，这个过程形成一阶马尔可夫链。随着随机游走次数的增加，这个计算结果的数据会不断的趋于平稳，极限情况访问每个结点的概率收敛到平稳分布，这时各个结点的平稳概率值就是其 PageRank 值，表示结点的重要度。

现在我给出一个图结构，表示这里有 4 个页面，他们之间有某种程度上的互相链接跳转关系。

比如：

①页面有 1/2 的概率跳转到②页面，也有 1/2 的概率跳转到③页面。③页面各有 1/3 的概率跳转到①页面、②页面、④页面。②页面只能跳转到④页面。......

现在我们将各个页面之间的互相跳转关系画出来，做成成右边的这个概率转移矩阵。

我们用下面这个公式计算：

PR(k)=i∑n​L(i)PR(i)​

PR(i)表示指向结点k的结点集合L(i)表示结点i连出的有向边的个数

所以一次随机游走的计算过程如下：

转化成矩阵计算的话，结果就是下图这样的。就是用前一步的 PageRank 概率矩阵乘以页面的概率转移矩阵，就会得到当前步骤的 PageRank 概率矩阵。

通过多次迭代之后，这个值会趋近于平稳。也就是最终获得的 PageRank 概率矩阵，用结果矩阵作为网页的分数排名。

我们可以知道，一个网页，如果指向该网页的超链接越多，随机跳转到该网页的概率也就越高，该网页的 PageRank 值就越高，这个网页也就越重要。一个网页，如果指向该网页的 PageRank 值越高，随机跳转到该网页的概率也就越高，该网页的 PageRank 值就越高，这个网页也就越重要。PageRank 值依赖于网络的拓扑结构，一旦网络的拓扑（连接关系）确定，PageRank 值就确定。PageRank 的计算可以在互联网的有向图上进行，通常是一个迭代过程。先假设一个初始分布，通过迭代，不断计算所有网页的 PageRank 值，直到收敛为止。

一般在实际的生产环境中是做 8~10 次迭代即可。

数学定义

最后我们给出一个数学定义。

PageRank 的一般定义：

给定一个含有 n 个结点的任意有向图，在有向图上定义一个一般的随机游走模型，即一阶马尔可夫链。

一般的随机游走模型的转移矩阵由两部分的线性组合组成：

有向图的基本转移矩阵 M，表示从一个结点到其连出的所有结点的转移概率相等；完全随机的转移矩阵，表示从任意一个结点到任意一个结点的转移概率都是 1/n，线性组合系数为阻尼因子 d（0≤d≤1）。

这个一般随机游走的马尔可夫链存在平稳分布，记作 R。定义平稳分布向量 R 为这个有向图的一般 PageRank。R 由公式R=dMR+n1−d​1 决定，其中 1 是所有分量为 1 的 n 维向量。

一般 PageRank 的定义意味着互联网浏览者，按照以下方法在网上随机游走：在任意一个网页上，浏览者或者以概率 d 决定按照超链接随机跳转，这时以等概率从连接出去的超链接跳转到下一个网页；或者以概率（1−d）决定完全随机跳转，这时以等概率 1/n 跳转到任意一个网页。第二个机制保证从没有连接出去的超链接的网页也可以跳转出。这样可以保证平稳分布，即一般 PageRank 的存在，因而一般 PageRank 适用于任何结构的网络。

补充

后来又出现了 personalized page rank、heat-kernelpage rank 等等，感兴趣的可以自己去查阅。数学定义出自李航老师的《统计学习方法》。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。