计算机科学 1998

大规模超文本网络搜索引擎剖析

谢尔盖·布林与拉里·佩奇

用「谁链接了它」来给网页排名——后来成为谷歌的搜索引擎，就此诞生。

Choose your version

In depth · the introduction

在谷歌之前，多数搜索引擎主要是在数一个网页上的词。PageRank 问了一个更聪明的问题：是谁，指向了这个网页？

把这个想法拆开看

从一个网页指向另一个网页的链接，有点像一句推荐。PageRank 的洞见在于：并非所有推荐都等值——来自一个本身就重要的网页的链接，理应分量更重；而一个什么都链接的网页，它的推荐就被摊得很薄。于是，一个网页之所以重要，是因为有重要的网页指向它。

这听上去是循环的——确实如此——但它解得开。想象一位「随机冲浪者」，永远在点击链接，时不时又因无聊而跳到一个随机网页。这位冲浪者最常落脚的那些网页，就是重要的网页。PageRank 不过是那套数学：它一口气替整个网络算出，冲浪者把时间花在了哪里。

它从哪里来

1990 年代中期，两位斯坦福的博士生，谢尔盖·布林与拉里·佩奇，启动了一个他们称为 BackRub 的项目——因为它研究的是网络的「反向链接」。从中长出了一个搜索引擎，他们把它改名为 Google，取自 googol（1 后面跟一百个零），以致意网络之浩大。1998 年，他们在 WWW7 大会上，用一篇八页的论文铺陈了整套设计，并在同年创立了公司。

它为何重要

1998 年的网络，正被海量网页淹没，而关键词搜索很容易被骗——往一个网页里塞满热门词，它就能排到前面。PageRank 把网络自身的链接结构，变成了一个远更难伪造的质量信号，因为你没法轻易逼着成千上万的人来链接你。它的结果好得太多，以至于短短数年间，谷歌的这套方法便重塑了整个行业，而搜索，也成了大多数人通往互联网的入口。

一种想象它的方式

想想学术论文。一篇被许多高被引论文引用的文章，多半是重要的——比一篇只被几篇无名之作引用的更重要。PageRank 对网页做的，正是同样的事，只是用链接顶替了引用。其精妙之处在于：重要性会「流动」——一个网页把自身地位的一份，传给它所链接的网页，如此一圈圈传下去，直到整个网络沉淀出一个稳定的排名。在下方，亲手让它流动起来。

它身处何处

PageRank 立在蒂姆·伯纳斯-李的万维网之上（berners-lee-1989）——是万维网，用链接把文档串到了一起；而它又跑在瑟夫与卡恩所造的互联网之上（cerf-kahn-1974）。它数链接的数学，呼应着一个古老得多的想法——学者们如何按引用给期刊排名。而它所造就的那个搜索框，如今正在其上生长出新的一层：建在 Transformer 之上的问答引擎与聊天机器人（transformer-2017）。

The original document

Original source text

Sergey Brin & Lawrence Page · Computer Networks and ISDN Systems 30 (1998): 107–117 · 7th International World Wide Web Conference, Brisbane, April 1998

Abstract

The paper presents Google, a prototype search engine that makes heavy use of the structure present in hypertext. Its central claim is that the web's link graph — who links to whom — carries enough information to rank pages by importance, and that combining this with the text of the links themselves yields far more relevant results than keyword matching alone.

PageRank: bringing order to the web

A link from page i to page A is treated as a vote, but a weighted one: a vote from a page that is itself important counts for more, and a page that links to many places splits its vote among them. This makes the definition circular — a page is important if important pages point to it — which the paper resolves with the recurrence below and a damping factor d (about 0.85).

The authors give the rank an intuitive reading: the 'random surfer'. Imagine someone who clicks links at random and, every so often (with probability 1−d), gets bored and jumps to a random page. PageRank is the long-run fraction of time this surfer spends on each page — equivalently, the principal eigenvector of the web's link matrix, computed by iterating the formula to convergence.

Anchor text and the rest of the system

Google also indexes the anchor text — the clickable words of a link — and associates it with the page the link points to, since those words often describe the target more accurately than the target describes itself (and let the engine index pages it has never crawled). Around these two ideas the paper builds a full system: a crawler, a parser, an inverted index, and a ranking that blends PageRank with text-match scores, font and position cues, and proximity.

The name is a play on 'googol' (10^100), hinting at the scale intended. The described prototype already indexed about 24 million pages on commodity hardware, and ran publicly at google.stanford.edu.

[ … ]

Results and conclusion

The paper reports that link-based ranking returns markedly more relevant pages than the keyword engines of the day, precisely because link structure is hard to manipulate with words alone. It closes by arguing that a search engine is too important to be shaped by advertising incentives — and that scalable, high-quality search is an open research problem the academic community should pursue.

Stanford, California · 1998