第24章 线性代数与强大的谷歌搜索引擎(2)

谷歌的创始人拉里·佩奇和谢尔盖·布林当时还是研究生院的两个学生,他们发明了一种新的网络搜索算法:让网页自己给自己投票,不是举手投票,而是用 实际行动(链接)投票。在上面的例子中,页面X和页面Y都链向页面Z,页面Z是这个迷你网络中唯一有两个外链接指向它的页面。所以,页面Z是这个迷你网络 中最“流行”的网页。“流行度”是有信息含量的 。但是,如果一个可疑网页链向另一个网页,那么另一个网页也应该被扣分,就像一个不可靠的人推荐的人不值得别人信任一样。“流行度”本身不说明问题,只有 被好的网页“推荐”(好的网页里含有你的链接),才能获得加分。

于是,我们又回到了那句禅语:最佳网页是那些链接其他最佳网页的网页。但是,一开始,谁来决定哪些网页是最佳网页呢?

我 们让网络自己来决定,具体方式如下:谷歌的搜索算法给每个网页打一个分数,这个分数叫作“网页排序号”,是一个介于0和1之间的数字。“网页排序号”考虑 一个假想的上网者,他会在这个网页上花掉的时间占总上网时间的多大比例?通过回答这个问题,我们可以度量一个网页相对于其他网页的重要程度。这个假想的上 网者是这样上网的:如果一个网页上有另外几个网站的链接,他就会从这些链接中随机选择一个点击,点击每个链接的概率相等。在这个假设条件下,一个网页的访 问量越大(我们假想的上网者的访问量,不是实际互联网用户的访问量),这个网站就越重要。

因为“网页排序号”的定义是(假想上网者)访问这 个网站的时间占总上网时间的比例,所以网络上所有网页的“网页排序号”的总和必然为1。根据守恒定律,我们还可以把“网页排序号”想象成一股水流,这股水 流在网页间流动,从体验不佳的网页不断地向体验良好的网页汇聚。谷歌的算法考察的就是,从长期来看,这股水流如何分配到网络中的各个网页中。

为 了算出水流的分配,我们需要一个巧妙的迭代算法。首先,我们对每个网页的“网页排序号”进行一个粗略的估计,用这个猜测值作为迭代的初始值。然后,我们考 虑水流如何不断地分流到新的网页中,规则是:如果一个网页上有另外几个网站的链接,假设上网者就从这些链接中随机选择一个点击,点击每个链接的概率相等。 这个过程不断地进行下去,直到水停止流动,每个网页的访问量稳定下来。

一开始,谷歌的算法比较宽泛:每个网页的初始值都一样。比如,我们的迷你网络共有3个网页,那么每个网页的“网页排序号”的初始值都是1/3。 



读书导航