谷歌页面排名算法 – 未完

一、 PageRank 算法原理

一个合格的收索引擎，它所具备的最基础的功能便是网页搜索，根据用户给出的关键字查询出最匹配，最能满足用户需求的页面。那么搜索引擎到底应该如何排序才好呢？

这在谷歌引领互联网搜索引擎之前，人们为此伤透脑筋，想出了一些最初的办法。

人们认为，应该如何得知哪个网页是最重要的这件事，应该由顾客自己来决定，如果计算得出哪个网页更重要，那么它就应该排在靠前的位置，这个问题看似容易，但实则解决方式并没有想象中的那么简单。

在网页排名算法诞生初期，人们对页面排序的想法以及实现策略基本一致。

他们为每一个页面设置一个数值，它的初始值为零，将他们不进行排序放入到页面列表里，这时页面是无序的。

之后，每个链接被打开的时候，将这个数值增加 1 。那么在一段时间后，每个页面属于自己的数值都发生了一些变换。

于是算法根据每个页面数值大小将他们排序，数值越大的页面就排在前面。

这里人们用到了一个非常简单的思想：越是重要的页面，那么它的访问量便越大，许多页面排序算法的实现者利用这个共同点将页面进行排名，这样的算法虽然简单，但也面临着巨大的问题。

1. 因为在排序算法应用的初期，由于每个页面的访问量初始值都为零。所以整个页面列表是无序的，导致每个页面被访问的概率相同。同时，质量较低的页面可能排在质量较高页面的前面。且由于用户访问页面的可能性，排名越靠前的页面越可能被访问到这一特性，导致质量较低的页面访问量增加，从而直接让质量较低的页面更进一步靠前。
2. 访问量不一定能够直接体现网页的重要程度，因为很有可能被一些人恶意访问，以刷访问量的形式提高某些特性网页的权重，从而使其排名靠前。

就是因为从前的页面排序算法存在这些大大小小的缺陷，当时还在美国斯坦福大学的谷歌公司创始人，对这个问题进行了研究。

他曾发布过一篇叫做 页面排名算法的论文对他的算法进行了介绍，主要应用到的思想是：

被越多页面引用的页面越重要，且越重要的页面其引用的页面的链接质量越高，同时越更容易被其他重要的网页所引用，权重更高。

由于算法完全是利用网页与网页之间的链接关系来计算网页重要程度的，而算法则是一个数学问题。自此之后，由访问量来计算网页重要程度方法被彻底摆脱。

PageRank 算法的核心原理是：

在互联网中，如果一个网页被其他很多网页所链接，那么说明该网页是非常重要的，那么它的排名就会越靠前。越是排名考前的网页所引用的网页可信度越高，越重要。

如果我们用一张图表示的话：

如果 PageA有一个箭头指向了 PageB，那么我们说 PageA中有一条 PageB的超链接。那么用户访问 PageA时就有跳转到 PageB的可能性。并且此时 PageB是被 PageA需要的。

我们称 PageA有一条 出链指向 PageB。

且 PageB有一条来自于 PageA的 入链。

即：

• 出链：从自身出去的链。
• 入链：从外部引入自身的链。

由此我们可以得出：

图中 PageA有三条出链，和一条入链。

由数学表达式可以表现为：

其中，表达式左侧结果值代表页面影响力，也就是页面排名。

• PR(u)是页面 u的分值，也就是排名。
• Bu为页面 u的入链集合。
• 网页 v 是网页 u 的任意一个入链。
• PR(v) 是网面 v 的分值。
• L(v) 是网页 v 的出链数量。
• 网页 v 带给网页 u 的分值就是 PR(v) / L(v)。
• 那么 PR(u) 就等于所有的入链分值之和。

从以上公式，我们可以假设一点：

每个页面若有 n个出链页面，那么从这个页面到达所有出链页面的可能性是相等的。

例如图中 PageA拥有三个出链页面，分别为： PageB、 PageC、 PageE。

那么当用户访问 PageA时，我们假设跳转其三个出链页面的可能性相等，且都为 1/3。

那么我们可以尝试计算一下 PageA的分值是多少：

由图可得 PageA的入链页面，也就是引用 PageA的页面仅有一个即 PageC

而 PageC有两个出链，也就是它引用了两个页面。

所以到达 PageA得可能性为 1/2。

根据这个方法，我们可以把每个页面到每个页面的可能性，通过一个表格来统计： PageA PageB PageC PageD PageE PageA

01/31/301/3 PageB

00010 PageC

1/20001/2 PageD

00001 PageE

01/201/20

之后，我们可以将表换转换成一个二维矩阵：

double[][] matrix = new double[][]{
    {0,(double) 1/3,(double)1/3,0,(double) 1/3},
    {0,0,0,1,0},
    {0.5,0,0,0,0.5},
    {0,0,0,0,1},
    {0,0.5,0,0.5,0}
};

double[] defaultWeight = double[]{0.2,0.2,0.2,0.2};

同时，由于五个页面在未经过排序时，用户访问他们的概率都相等，均为 1/5。

我们可以通过概率计算方式将他们相乘，得出迭代一次后的结果。

同理可以得出迭代第二次的结果 I(2)以及 I(3)一直到某个数 I(n)。

并且佩奇和布林已经证实过，无论网页初始值设置为多少，最终经过数次迭代计算，就可以保证网页分值收敛到一个小的范围区间内，直到收敛到一个确定的值。或者说 I(n)将不再变化。

之后我们便可以将每个页面的分值作为比重进行排序。

二、算法实现

第四章描述了 Google页面排序算法的思想以及算法工作流程。

主要是利用了 量化网页重要程度的分值变量，使用 PR表示页面重要程度，即一个网页的 PR越大，则该网站越为重要。

那么可以在以上基础上，对算法进行简单实现。

我们假设有四个网页的关系扑朔图如下：

可以得出：

row => colABCDA01/31/31/3B1/2001/2C0001D0100

于是可以转化为一个二维矩阵：

final double[][] matrix = new double[][] {
    {0,(double)1/3,(double)1/3,(double)1/3},
    {0.5,0,0,0.5},
    {0,0,0,1},
    {0,1,0,0}
};

double[] defaultWeight = double[]{0.2,0.2,0.2,0.2};

根据公式，如果要计算某一页面的分值，应该逐次计算自己的每个入链页面的 PR分值除以出链数量之后相加。

得出第一轮的该页面分值，每轮将计算页面个数次。

且需要计算 n次，直到数值趋于一个阈值，也就是数值固定。

private void calRank() {
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix.length; j++) {
            if (matrix[j][i] != 0) {
                backUpRank[i] += rank[j] * matrix[j][i];
            }
        }
    }
    rank = backUpRank;
    backUpRank = new double[]{0,0,0,0};
}

可以选择使用一个循环和定时器进行计算，直到结果趋于一个固定数值。

for (;;) {
    calRank();
    System.out.println("rank = " + Arrays.toString(rank));
}

运行结果：

由运行结果观察得知，在计算初期每个页面的分值飘忽不定。

但在运行了一段时间后，各页面分值渐渐趋于固定，即可认为 PR收敛。

• A： 0.20
• B： 0.4
• C： 0.066
• D： 0.333

由此我们可以断定，页面 B的分值最高，应该排在第一位，并且这也符合我们对页面关系网络图的直观感受。

三、算法隐患

论文第四和第五章中介绍到的 PageRank页面排序算法的原理以及基本实现均为简化版本，是算法设计初期。

在后续的应用中也出现了一些问题，主要分为两类：

• 等级泄露
• 等级沉没

1. 等级泄露

例如，如果一个网页没有出链，仅有入链。则会导致它一直吸收其他页面的分值不释放。最终将其他所有页面的分值吸收掉并彻底变为 0，这样的情况叫做等级泄露。

我们将刚刚的实例做简单修改：

将页面节点 D的出链删除，也就是删除链 D -> B。

于是代码中的二维矩阵会发生一些变化，我们略做修改。

final double[][] matrix = new double[][] {
    {0,(double)1/3,(double)1/3,(double)1/3},
    {0.5,0,0,0.5},
    {0,0,0,1},
    {0,1,0,0}
};

将二维矩阵 [3][1]位置，也就是 D -> B位置的数值修改为 0，表示无引用关系。

final double[][] matrix = new double[][] {
    {0,(double)1/3,(double)1/3,(double)1/3},
    {0.5,0,0,0.5},
    {0,0,0,1},
    {0,0,0,0}
};

为了验证上述观点： 如果一个网页没有出链，仅有入链。则会导致它一直吸收其他页面的分值不释放。最终将其他所有页面的分值吸收掉并彻底变为 0 ，这样的情况叫做等级泄露。

运行程序，查看运行结果。

程序运行一段时间后，经过图中打印数据可得：

页面 D会吸收其他所有页面分值，导致其他所有页面的分值归为 0。并且在其他页面分值归 0时，页面 D也会因为无法吸收分值而导致自己的分值归 0，可谓害人终害己。

出现这种问题的原因可以理解为 D页面对整个网络没有 PR值得贡献，因为它得出度为 0，相反它还会吸收其他网页对它的 PR贡献，导致整个页面的 PR越来越小。

2. 等级沉没

如果页面集合中，有其中某个页面的入度为 0，也就是没有入链，仅有出链。

则这样的情况会出现等级沉没问题，该页面会无私的稀释自己的分值给其他页面，于此同时，并不会进行分值吸收。

最终它的页面分值会归零。

我们对刚刚的页面稍做修改：

删除 A -> B的引用，将页面 A的入链删除。

同时在原来的基础上对二位矩阵进行修改：

final double[][] matrix = new double[][] {
    {0,(double)1/3,(double)1/3,(double)1/3},
    {0.5,0,0,0.5},
    {0,0,0,1},
    {0,1,0,0}
};

删除 A -> B的引用，也就是 [1][0]处数值归 0，表示无引用关系。

final double[][] matrix = new double[][] {
    {0,(double)1/3,(double)1/3,(double)1/3},
    {0,0,0,0.5},
    {0,0,0,1},
    {0,1,0,0}
};

运行结果：

由运行结果可见，在程序运行初期，页面 A的分值就已经被分散出去归为 0，并且后续一直保持分值为 0的状态。

四、算法优化 – 随机浏览模型

为了解决第六章所提到的等级泄露以及等级沉没的问题， 拉里·佩奇提出了一个重要的概念。

• 随机浏览模型

随机浏览模型是根据用户上网行为总结出来的一种模型，表示用户随机的打开了一个网页，那么在跳转网页时，要么是通过点击这个网页上的链接来打开其他网页浏览，或者随机的重新随机打卡一个网页并重新开启另一轮的浏览。

即用户并不完全依靠网页中的链接引用来访问响应网页，也有可能通过其他方式。例如直接输入网址。

因此， 拉里·佩奇提出了 阻尼因子的概念，这个因子 d的用途是直接反应用户按照跳转链接来上网的概率，而 1 - d则表示用户通过其他方式访问网页的概率。我们将其引入到原来的公式稍作修改得到一个新的公式：

其中 N为整个网页集合的数目， d为阻尼因子，通常阻尼因子的值可以取 0.85。

引入阻尼因子后，网页集合的直观有向图可以变为一个拥有双向链接的有向图。

引用网页即出链入链为实线，并且用户使用超链接跳转的概率为 0.85。

其他访问方式为虚线，用户使用的概率为 0.15。

这样的一个随机浏览模型就是一个完整的全连接关系，解决了等级泄露和等级沉没的问题。

Original: https://blog.csdn.net/Pratik_shiku/article/details/119928075
Author: 一个欧维
Title: 谷歌页面排名算法 – 未完