Computer Science 1998

The Anatomy of a Large-Scale Hypertextual Web Search Engine

Sergey Brin & Lawrence Page

Rank a web page by who links to it — and the search engine that became Google is born.

Choose your version

In depth · the introduction

Before Google, most search engines mostly counted the words on a page. PageRank asked a smarter question: who points to this page?

The idea, unpacked

A link from one page to another is a little like a recommendation. PageRank's insight is that not all recommendations are equal: a link from a page that is itself important should count for more, and a page that links to everything spreads its recommendation thin. So a page is important if important pages link to it.

That sounds circular — and it is — but it can be solved. Picture a 'random surfer' clicking links forever, now and then jumping to a random page out of boredom. The pages this surfer ends up on most often are the important ones. PageRank is just the math that works out, for the whole web at once, where the surfer spends its time.

Where it came from

In the mid-1990s, two Stanford PhD students, Sergey Brin and Lawrence Page, started a project they called BackRub — because it studied the web's back-links. Out of it grew a search engine they renamed Google, after 'googol', the number 1 followed by a hundred zeros, a nod to the scale of the web. In 1998 they laid out the whole design in an eight-page paper at the WWW7 conference, and founded the company the same year.

Why it mattered

The web in 1998 was drowning in pages, and keyword search was easy to fool — stuff a page with popular words and it would rank. PageRank turned the web's own link structure into a quality signal that was far harder to fake, because you cannot easily force thousands of other people to link to you. The results were so much better that within a few years Google's approach had reshaped the entire industry, and search became most people's gateway to the internet.

A way to picture it

Think of academic papers. A paper cited by many well-cited papers is probably important — more so than one cited by a few obscure ones. PageRank does the same for web pages, with links standing in for citations. The cleverness is that the importance 'flows': a page passes a share of its own standing to the pages it links to, around and around, until the whole web settles into a stable ranking. Try that flow yourself below.

Where it sits

PageRank rests on Tim Berners-Lee's web (berners-lee-1989), which strung documents together with links, running over the internet built by Cerf and Kahn (cerf-kahn-1974). Its link-counting math echoes a much older idea from how scholars rank journals by citation. And the search box it created is now growing a new layer on top: the answer engines and chatbots built on the 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