Pagerank的简单理解

作为全球最大最好用的搜索引擎Google，大家都想知道它使用的是什么算法把网页搜索做的那么流畅。当然我们无从得知其具体做法，但其中的核心思想还是可以去窥探一二的。

如果说百度更懂中文，那么谷歌就更懂我。当然，大家都想要一个更懂自己的搜索引擎。那么谷歌是如何做到更懂你的呢，其中最著名的算法就是佩奇排名了(PageRank)。第一次听到这个名词的时候以为这个 Page 就是网页的意思，后来才知道这个算法是谷歌创始人之一的拉里·佩奇(Larry Page)来命名的。这个算法的主要作用就是分析网页的相关性和重要性，下面我们就一起来看一看其中的核心思想。

首先我们假设有四个网页，刚开始他们都没有链接到任何其他网页，也没有被其他网页链接，如下图所示。那么所有网页的rank值记为 $PR()=0$，而所有网页连接到其他网页的概率也为0，而总值我们设置为 1 。

好了，那如果现在的链接和被链接情况如下图所示的话，我们就可以用一个矩阵来表示它们之间的关系，其中列表示该网页连接到其他网页的概率，行则表示其他网页链接到此网页的情况。

从图中可以看出 A 页面把唯一的链接给了 B ，而 B 页面同时链接了 D 和 C ，C 页面同时链接了 A 和 D，D 页面则同时链接了 B 和 A。 如果我们把每一个链接都打分，然后每一个页面链接出去的分数总和为 1 的话，就得到如下图所示：

那么用矩阵表示如下：

\begin{align} \begin{bmatrix} 0 & 0 & 1/2 & 1/2 \\ 1 & 0 & 0 & 1/2 \\ 0 & 1/2 & 0 & 0 \\ 0 & 1/2 & 1/2 & 0 \end{bmatrix} \end{align}

从矩阵表示中可以看出，每一列的和都为 1，表示每个网页链接到其他网页的总概率为 1。也就是说如果你现在在网页 B，那么你有 50% 的概率连接到网页 C 和 D。

那么，我们如何计算每一个网页的 $PR$ 值的。到此我们只有了一个表示网页之间互相链接情况的矩阵，那么还需要一个初始的网页打分矩阵，然后就可以去计算更新各个网页的 $PR$ 值了。这里为了讨论的简单，用如下 $R_0$ 矩阵来表示每个网页初始的受欢迎程度:

\begin{align} \begin{bmatrix} 0.25 \\ 0.25 \\ 0.25 \\ 0.25 \end{bmatrix} \end{align}

然后使用链接矩阵和初始 $R_0$ 矩阵相成就可以得到第一次循环的 $R_1$ 矩阵：

\begin{align} \begin{bmatrix} 0 & 0 & 1/2 & 1/2 \\ 1 & 0 & 0 & 1/2 \\ 0 & 1/2 & 0 & 0 \\ 0 & 1/2 & 1/2 & 0 \end{bmatrix} \begin{bmatrix} 0.25 \\ 0.25 \\ 0.25 \\ 0.25 \end{bmatrix} = \begin{bmatrix} 0.25 \\ 0.375 \\ 0.125 \\ 0.25 \end{bmatrix} \end{align}

从中我们看出，网页 B 打了最高的分数，因为有两个网页链接给了它，而且其中一个网页把给了它百分百的链接。而网页 C 是最低分，它的唯一链接来自于 B，而 B 同样也链接给了 D，网页 A 和 D 的分数相同都是初始值 0.25。现在我们把 $R_0=R_1$，再一次进行上面的循环，然后再把得到的 $R_1$ 赋值给 $R_0$ … 这样一直循环下去就会看到 $R_0$ 会逼近一个值。如果我们把初始的链接矩阵用 $A$ 来表示，那么这个过程可以表示为如下极限：

\begin{align} \lim\limits_{n\rightarrow\infty}{A^nR_0}= \begin{bmatrix} 0.217 \\ 0.348 \\ 0.174 \\ 0.261 \end{bmatrix} \end{align}

从中我们可以看出 网页 A 虽然和 网页 D 有相同的链接数，但他们来自不同质量的网页，网页 D 其中一个链接是网页 B 给的，而网页 B 是 $PR$ 最高也就是质量最高的网页。因此不仅仅是链接数决定了这个网页的打分，更重要的是链接的质量。即使你的网页被很多网页所链接，并不代表它被谷歌承认的概率的高一点，如果都是垃圾链接的话可能就一文不值了。

个人的一点理解，也只能当做饭后的谈资或者一点回味了。