《我的第一本算法书》阅读笔记 7-3 网页排名(PageRank)

川长思鸟来 2022-11-16 13:38 131阅读 0赞

网页排名（PageRank，也叫作佩奇排名）是一种在搜索网页时对搜索结果进行排序的算法。 Google 因在搜索引擎中使用了这个算法而成为了世界知名的大企业是众所周知的事情。

--------------------

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70][]

网页排名就是利用网页之间的链接结构计算出网页价值的算法。我们来看看具体的计算流程吧。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 1][]

这里假设方块表示网页， 箭头表示网页间的链接 关系。在网页排名中，链 入页面越多的网页，它 的重要性也就越高。

![20210407112345218.png][]

从这张图中我们可以看出，上面网页的重要性最 高。实际上，各个网页的重要性会通过计算来数 值化。下面我们就来了解计算方法的基本思路。

![20210407112355932.png][]

假设没有链入页面的网页权重为1。

![20210407112408216.png][]

有链入页面的网页权重是其链入页面的权重 之和。

![2021040711250869.png][]

如果一个网页链向多个页面，那么其链向的所 有页面将平分它的权重。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 2][]

在网页排名中，链入的 页面越多，该网页所发 出的链接的价值就越高。

![20210407112549856.png][]

最顶端的网页被权重为3的页面链接，所以权重较高。以上就是网页排名的基本思路。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 3][]

但是，如果在链接结构为环状的情况下使用这 种方法，就会出现问题。

![20210407112608879.png][]

计算各个网页权重的操作会无限循环下去，从 而导致环内网页的权重不断增长。

![20210407112623475.png][]

此时可以使用“随机游走模型”（random walk model）来解决这个问题。要想了解这个模型， 先得思考一下人们是怎样浏览网页的。

![20210407112633254.png][]

假设有一天，某位互联网用户想浏览从杂志上 看到的一个有趣的网页。他从左下角的网页开 始浏览，然后通过链接到达其他网页。

![20210407112644652.png][]

浏览了一些网页后他不想再看了，于是结束 浏览。

![20210407112654503.png][]

过了几天，他又开始浏览朋友推荐的一个与之 前完全不同的网页。

![20210407112704757.png][]

这次也通过链接浏览了别的网页，并在一段时 间后结束了浏览。就像这样，他重复着从某个 网页开始，通过链接浏览了几个网页后结束的 流程。

![2021040711272734.png][]

如果我们站在互联网空间的视角来观察上述流 程，就会觉得浏览网页的人只是在不断重复着 “在有链接指向的页面之间移动几次之后，远 程跳转到了完全不相关的网页”这一过程。

![20210407112738723.png][]

那么，用户浏览网页的操作就可以这样来定 义 ：用户等概率跳转到当前网页所链向的一个 网页的概率为1- α ；等概率远程跳转到其他网 页中的一个网页的概率为α。

![20210407112750383.png][]

此处我们将远程跳转概率α设为15%，并根据 前面的定义来模拟一下网页间的跳转过程。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 4][]

网页上的数字代表用户访问该网页的次数。现 在模拟还未开始，所有的数字都是0。

![20210407112812238.png][]

开始根据定义模拟用户浏览网页的过程，各个 网页的访问次数也开始出现差距。

![20210407112830880.png][]

模拟中……

![20210407112841153.png][]

模拟该过程直到访问的总次数达到1000次为 止，最终结果如上图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 5][]

换算成百分比后，结果如上图所示。这些值代表的是“某一刻正在浏览这个网页的概率”，随机游走模 型会直接将其作为网页的权重来使用。

![20210407112916563.png][]

最后，我们来确认网页排名的值和最初介绍的用链接加权计算的结果是否一致。

![20210407112934132.png][]

由于各个值都是四舍五入后的结果，所以所有 值加起来并不等于1，但分值比例与之前的结 果是非常接近的。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 6][]

这是前面讲到的链接结构，试着计算它的权重。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 7][]

可以看出，此处的分值比例也和之前的很相近。

--------------------

以前的搜索引擎都是以关键词和网页内容的关联性来决定搜索结果的排列顺序，但 这种方法没有考虑网页内是否含有有效内容，因此搜索精度较低。

Google 公司提供了使用网页排名算法的搜索引擎，然后凭借其强大的性能成为了世界 知名企业。当然，如今决定 Google 搜索结果排序的已不仅仅是网页排名这一个算法了。

但不管是从利用网页链接结构计算出网页价值这种思路来看，还是从链接形成环状 时也能进行计算这点来看，网页排名都是一个划时代的算法。

--------------------

《我的第一本算法书》  \[日\]石田保辉 宫崎修一/著    张贝/译

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70]: /images/20221022/9d759e343c434193a69e04e53e15bc6c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 1]: /images/20221022/7070a3e513c3401bb5581ce7b46d3166.png
[20210407112345218.png]: /images/20221022/e635b207b5fc4e58a5e7925997254ae8.png
[20210407112355932.png]: /images/20221022/be4dffc6db8f4f0282fce854342172c9.png
[20210407112408216.png]: /images/20221022/33d3d66ef41b42a1b4c4dd73b6cd8e0f.png
[2021040711250869.png]: /images/20221022/cabebe872b464a6b9a6621b49cdfa772.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 2]: /images/20221022/b916ba3909c749798971a1cf6f8e55c5.png
[20210407112549856.png]: /images/20221022/657a46cd83bb40b4bd7d49c21debf4d4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 3]: /images/20221022/eb8e26ce660a4e3d8520483a31bbfe3b.png
[20210407112608879.png]: /images/20221022/f8dc48fadc764b7eb0a86779fb49513c.png
[20210407112623475.png]: /images/20221022/100ee45d264641b0853386ac3c95907b.png
[20210407112633254.png]: /images/20221022/db6d82f4ceb941feb462c1e940246f61.png
[20210407112644652.png]: /images/20221022/7b624a83c5e34255a36e69d78d4aa674.png
[20210407112654503.png]: /images/20221022/8330ed0fe627461280709f191207d39d.png
[20210407112704757.png]: /images/20221022/c40c9700585d4bd29fbc5c97cd7de766.png
[2021040711272734.png]: /images/20221022/065b3063e901438dbd4dadf553b65bf4.png
[20210407112738723.png]: /images/20221022/aea5462e7c39469c898d0a8d867b960a.png
[20210407112750383.png]: /images/20221022/cc52c723f2cb4de79d19c48961b978f1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 4]: /images/20221022/6acde048a78b4ef0a2a5abcd9a248cdd.png
[20210407112812238.png]: /images/20221022/b36f899448db49649e8a905ce0ee1dd8.png
[20210407112830880.png]: /images/20221022/d0992d3f441e4f9781aa70d35f948cca.png
[20210407112841153.png]: /images/20221022/1a0909368bdc486ab8afc3e4de24107a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 5]: /images/20221022/847f388bd2324208b838ae32236cec55.png
[20210407112916563.png]: /images/20221022/9d3fcdf6104e4ebc9ea854ed3b170c00.png
[20210407112934132.png]: /images/20221022/1ccced27e7d241a6aff05aba04a4dada.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 6]: /images/20221022/70b4e60f57b447f2b81b9a21872831bb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 7]: /images/20221022/58ea92c5355941589fd0c57f8c96d329.png