計算機科學 1998

大規模超文本網路搜尋引擎剖析

謝爾蓋·布林與賴利·佩吉

用「誰連結了它」來為網頁排名——後來成為 Google 的搜尋引擎，就此誕生。

Choose your version

In depth · the introduction

在 Google 之前，多數搜尋引擎主要是在數一個網頁上的詞。PageRank 問了一個更聰明的問題：是誰，指向了這個網頁？

把這個想法拆開看

從一個網頁指向另一個網頁的連結，有點像一句推薦。PageRank 的洞見在於：並非所有推薦都等值——來自一個本身就重要的網頁的連結，理應分量更重；而一個什麼都連結的網頁，它的推薦就被攤得很薄。於是，一個網頁之所以重要，是因為有重要的網頁指向它。

這聽上去是循環的——確實如此——但它解得開。想像一位「隨機衝浪者」，永遠在點擊連結，時不時又因無聊而跳到一個隨機網頁。這位衝浪者最常落腳的那些網頁，就是重要的網頁。PageRank 不過是那套數學：它一口氣替整個網路算出，衝浪者把時間花在了哪裡。

它從哪裡來

1990 年代中期，兩位史丹佛的博士生，謝爾蓋·布林與賴利·佩吉，啟動了一個他們稱為 BackRub 的專案——因為它研究的是網路的「反向連結」。從中長出了一個搜尋引擎，他們把它改名為 Google，取自 googol（1 後面跟一百個零），以致意網路之浩大。1998 年，他們在 WWW7 大會上，用一篇八頁的論文鋪陳了整套設計，並在同年創立了公司。

它為何重要

1998 年的網路，正被海量網頁淹沒，而關鍵詞搜尋很容易被騙——往一個網頁裡塞滿熱門詞，它就能排到前面。PageRank 把網路自身的連結結構，變成了一個遠更難偽造的品質訊號，因為你沒法輕易逼著成千上萬的人來連結你。它的結果好得太多，以至於短短數年間，Google 的這套方法便重塑了整個產業，而搜尋，也成了大多數人通往網際網路的入口。

一種想像它的方式

想想學術論文。一篇被許多高被引論文引用的文章，多半是重要的——比一篇只被幾篇無名之作引用的更重要。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