How Did Google Find the Best Page on the Web?: Computing Further 9–12

Type “Nyatapola” into a search engine, and in less than a second it has found thousands of pages with that word on them: a temple guide, a hotel, a school project, a blog post from a tourist, a shop selling postcards. All of them contain the word. Which one should come first?

In 1997 this was a real problem. Search engines matched the words on pages, and anyone could fill a page with a word. In November 1997, only one of the four biggest search engines found its own home page among the top ten results when you typed its own name. Two students at Stanford University in California, Larry Page and Sergey Brin, tried a different idea: let the links between pages decide. Their search engine became Google.

Below is a small web of ten pages about Bhaktapur. It is made up: the pages and their links are invented for this topic, but they behave like real ones. Each arrow is a link from one page to another. A thousand “surfers” start on pages picked at random and keep clicking links at random. Press Play.

The number in each circle is the share of all the surfers’ visits so far that went to that page, in percent; a bigger circle, a bigger share. Press 100 clicks to jump ahead.

Surfers:

Jump:

Clicks: 0
Visits counted: 0
Most visited: –

1,000 surfers start on pages picked at random. Press Play, and watch where they spend their time.

Before the numbers settle, guess: which page will the surfers visit more?

Pick an answer to see why.

Nyatapola ends up with about 16% of all visits, the Curd shop with about 6.5%, even though three pages link to the Curd shop and only one to Nyatapola. The Curd shop’s links come from three small blogs that hardly anyone visits. Nyatapola’s one link comes from the City guide, the page the surfers visit most. A page matters if pages that matter link to it. In this topic your own program will find these numbers, two different ways, and show that they agree.

You need lists and dictionaries in Python (Grade 9) and graphs (Grade 10). Random choices are explained here.

Try it

Let the thousand surfers run for a few hundred clicks, then look at the numbers.

The City guide gets the most visits, about 31%. Five pages link to it.
Nyatapola and Bus times get about 16% each. Only the City guide links to them, and it has just those two links, so each gets half of the City guide’s surfers.
The three blogs get about 3% each. No page links to them at all: surfers arrive only by jumping (below).

One surfer at a time

Now press 1 beside Surfers: and follow a single surfer with One click. Most clicks follow a link on the page it is on (the red arrow). But now and then the surfer jumps: it gets bored and goes to a page picked at random, as if it had typed a new address. On Bus times it always jumps, because Bus times has no links at all.

Why should a surfer ever jump? Set Jump: to Never, set Surfers: back to 1,000, and press 100 clicks.

Pick an answer to see why.

A trap

Dead ends aren’t the only problem. Here is the same web with one change: More photos no longer links to the City guide. Photos and More photos now link only to each other.

It starts with Jump: Never. Press 100 clicks, then switch to Sometimes and press 100 clicks again.

Surfers:

Jump:

Clicks: 0
Visits counted: 0
Most visited: –

1,000 surfers start on pages picked at random. Press Play, and watch where they spend their time.

What you should see

Two or more pages that link only among themselves catch the surfers who wander in. Page and Brin called this a rank sink. The random jump limits the damage: a trapped surfer jumps out after about seven clicks, on average (it jumps 15 times in 100).

Watching surfers is slow, and the numbers wobble because the surfers are random. There is another way to get the same numbers, without any surfers, and it is exact.

Give every page an equal share to start: with ten pages, 0.1 each (10%). Then, in each round, every page hands its share on: it splits it equally among the pages it links to. A page with two links gives half its share to each. Repeat. After a few dozen rounds the shares stop changing, and they are the same numbers the surfers found.

Why the same? Think of the share as the fraction of all the surfers who are on that page. On each click, the surfers on a page spread out equally over its links. Handing the share on equally along the links is exactly that, with a whole crowd of surfers instead of a thousand.

Here is the example Page, Brin and two of their teachers used in their 1998 report: three pages, A links to B and C, B links to C, and C links back to A. This web has no dead ends and no traps, so it can be shared without jumps.

Press Next round a few times. Each arrow thickens with the share that flowed along it in the last round.

Jump:

Rounds: 0
Biggest change: –
Biggest share: –

Every page starts with an equal share, 33.3% each. Press Next round: each page hands its share on along its links.

After many rounds the shares settle at A 40%, B 20%, C 40%. Why does B end with half as much as A?

Pick an answer to see why.

The jump is easy to add to sharing. In each round, each page hands 85% of its share along its links, and spreads the other 15% equally over every page in the web (those are the surfers who got bored and jumped). A dead end spreads all of its share over every page. The 85% is called the damping factor; Page and Brin’s paper says, “We usually set d to 0.85.”

Their paper calls a page’s final share its PageRank (after Larry Page, and after pages), and describes it with the surfer you have been watching: a random surfer who keeps clicking links and “eventually gets bored and starts on another random page”. The probability that this surfer is on a page is the page’s PageRank.

Program it

You will build both methods, the surfers and the sharing, in four steps, each one running here on the page.

Step 1: the web as a dictionary

A web is a graph with arrows, and Grade 10 stored a graph as a dictionary: each page is a key, and its value is the list of pages it links to. This is the web you played with. First, the simplest ranking anyone would think of: count the links pointing to each page.

web = {    'City guide': ['Nyatapola', 'Bus times'],    'Nyatapola': ['City guide'],    'Curd shop': ['City guide'],    'Bus times': [],    'School': ['City guide'],    'Photos': ['More photos'],    'More photos': ['Photos', 'City guide'],    'Asha’s blog': ['Curd shop', 'School'],    'Bimal’s blog': ['Curd shop', 'City guide'],    'Dawa’s blog': ['Curd shop', 'Photos'],} links_in = {page: 0 for page in web}for page in web:    for target in web[page]:        links_in[target] += 1 for page in web:    print(f'{page:13} {links_in[page]} links in')

Output

City guide    5 links inNyatapola     1 links inCurd shop     3 links inBus times     1 links inSchool        1 links inPhotos        2 links inMore photos   1 links inAsha’s blog   0 links inBimal’s blog  0 links inDawa’s blog   0 links in

By this count the Curd shop is the second most important page, three times as important as Nyatapola. The surfers disagreed. Let’s program them.

Step 2: one random surfer

Python’s random module makes random choices: random.choice(a_list) picks one item, each equally likely, and random.random() gives a number from 0 up to (but not including) 1, so random.random() < 0.15 is true about 15 times in 100. random.seed(33) makes the program pick the same “random” choices every time it runs, so your run matches the output below; take it out for different walks.

click(page) is one click: on a dead end, or 15 times in 100, it jumps to any page; otherwise it follows one of the page’s links.

import random web = {    'City guide': ['Nyatapola', 'Bus times'],    'Nyatapola': ['City guide'],    'Curd shop': ['City guide'],    'Bus times': [],    'School': ['City guide'],    'Photos': ['More photos'],    'More photos': ['Photos', 'City guide'],    'Asha’s blog': ['Curd shop', 'School'],    'Bimal’s blog': ['Curd shop', 'City guide'],    'Dawa’s blog': ['Curd shop', 'Photos'],}pages = list(web) def click(page):    links = web[page]    if links == [] or random.random() < 0.15:        return random.choice(pages)    return random.choice(links) random.seed(33)page = random.choice(pages)walk = [page]for i in range(12):    page = click(page)    walk.append(page)print(' → '.join(walk))

Output

Dawa’s blog → Curd shop → City guide → Nyatapola → City guide → Bus times → Asha’s blog → Curd shop → City guide → Nyatapola → City guide → Bus times → Photos

The walk keeps coming back to the City guide. Twice it reached Bus times, a dead end, and jumped: once to Asha’s blog, once to Photos.

Step 3: a thousand surfers

Now let 1,000 surfers each make 100 clicks, and count every page each one lands on: 100,000 visits in all.

import random web = {    'City guide': ['Nyatapola', 'Bus times'],    'Nyatapola': ['City guide'],    'Curd shop': ['City guide'],    'Bus times': [],    'School': ['City guide'],    'Photos': ['More photos'],    'More photos': ['Photos', 'City guide'],    'Asha’s blog': ['Curd shop', 'School'],    'Bimal’s blog': ['Curd shop', 'City guide'],    'Dawa’s blog': ['Curd shop', 'Photos'],}pages = list(web) def click(page):    links = web[page]    if links == [] or random.random() < 0.15:        return random.choice(pages)    return random.choice(links) random.seed(2083)visits = {page: 0 for page in web}for surfer in range(1000):    page = random.choice(pages)    for _ in range(100):        page = click(page)        visits[page] += 1 total = sum(visits.values())for page in web:    print(f'{page:13} {100 * visits[page] / total:5.1f}%')

Output

City guide     31.0%Nyatapola      16.0%Curd shop       6.6%Bus times      15.9%School          4.1%Photos          8.1%More photos     9.8%Asha’s blog     2.8%Bimal’s blog    2.8%Dawa’s blog     2.8%

Your program, not a person, has ranked the pages: Nyatapola gets more than twice the visits of the Curd shop. Run it without random.seed(2083) a few times: the numbers change a little each time, in the first decimal place, because the surfers are random.

Now the exact method. pagerank(web) gives each page a share of 1 ÷ (number of pages), then does 50 rounds of sharing. In each round a new dictionary, new, starts with every page’s part of the jumps, 0.15 ÷ n, and each page adds 85% of its share to the pages it links to (or, for a dead end, spreads it over every page).

web = {    'City guide': ['Nyatapola', 'Bus times'],    'Nyatapola': ['City guide'],    'Curd shop': ['City guide'],    'Bus times': [],    'School': ['City guide'],    'Photos': ['More photos'],    'More photos': ['Photos', 'City guide'],    'Asha’s blog': ['Curd shop', 'School'],    'Bimal’s blog': ['Curd shop', 'City guide'],    'Dawa’s blog': ['Curd shop', 'Photos'],} def pagerank(web, rounds=50):    pages = list(web)    n = len(pages)    rank = {page: 1 / n for page in pages}    for _ in range(rounds):        new = {page: 0.15 / n for page in pages}        for page in pages:            links = web[page]            if links:                for target in links:                    new[target] += 0.85 * rank[page] / len(links)            else:                for target in pages:                    new[target] += 0.85 * rank[page] / n        rank = new    return rank rank = pagerank(web)for page in sorted(rank, key=rank.get, reverse=True):    print(f'{page:13} {100 * rank[page]:5.1f}%')print('All together:', round(sum(rank.values()), 6))

Output

City guide     30.8%Nyatapola      15.9%Bus times      15.9%More photos     9.9%Photos          8.3%Curd shop       6.5%School          4.1%Asha’s blog     2.9%Bimal’s blog    2.9%Dawa’s blog     2.9%All together: 1.0

(sorted(rank, key=rank.get, reverse=True) lists the pages from the biggest share to the smallest: key=rank.get tells sorted to compare pages by their value in rank.)

The same order as the surfers, and the same numbers to within a few tenths of a percent, with no randomness at all. The shares still add up to exactly 1: sharing moves them around, but never makes or loses any. Plug your pagerank into the web: the widget below gives your function its own dictionary of links.

Press 100 clicks a few times, then Compare. Change pagerank above (Edit), for example the 0.15 and 0.85 to 0.5 and 0.5, and Compare again: the surfers still jump 15 times in 100, so the two columns no longer agree.

Clicks: 0
Visits counted: 0
Most visited: –

1,000 surfers start on pages picked at random. Press Play, and watch where they spend their time.

Page	Surfers’ visits	Your pagerank
City guide	–	–
Nyatapola	–	–
Curd shop	–	–
Bus times	–	–
School	–	–
Photos	–	–
More photos	–	–
Asha’s blog	–	–
Bimal’s blog	–	–
Dawa’s blog	–	–

Press Compare: the page gives this web’s dictionary to your pagerank and shows what it gives back beside the surfers’ visits.

What your pagerank prints, and any error, appears here.

What your program shows

Your programs found three things.

a.Counting links gets it wrong. By links in, the Curd shop (3) beats Nyatapola (1). By the surfers and by sharing, Nyatapola gets 15.9% and the Curd shop 6.5%. A link is a vote, but a vote from an important page counts for more.
b.The surfers and the sharing agree. One method is random and needs 100,000 clicks; the other has no randomness and needs 50 rounds of adding. They give the same ranking, because the share is the surfers’ crowd, seen all at once.
c.The jump makes it work. Without it, dead ends and traps swallow the surfers; with it, every page keeps a little share and the crowd never gets stuck.

Does sharing still work for a web with thousands of pages? The program below makes made-up webs of 100, 1,000 and 10,000 pages, each page linking to up to eight pages picked at random (some linking to none), and counts the rounds until the shares have settled: until all the pages’ changes in a round, added up, come to less than a millionth. (With thousands of pages, handing each dead end’s share to every page one by one would take millions of additions a round, so this program adds up what the dead ends give first, from_dead_ends, and then hands every page that one amount.)

import random def rounds_needed(web):    pages = list(web)    n = len(pages)    rank = {page: 1 / n for page in pages}    rounds = 0    while True:        new = {page: 0.15 / n for page in pages}        from_dead_ends = 0        for page in pages:            links = web[page]            if links:                for target in links:                    new[target] += 0.85 * rank[page] / len(links)            else:                from_dead_ends += 0.85 * rank[page] / n        for page in pages:            new[page] += from_dead_ends        rounds += 1        change = sum(abs(new[page] - rank[page]) for page in pages)        rank = new        if change < 0.000001:            return rounds random.seed(1)for size in [100, 1000, 10000]:    web = {}    for page in range(size):        web[page] = random.sample(range(size), random.randint(0, 8))    print(f'{size:6} pages: {rounds_needed(web)} rounds')

Output

   100 pages: 17 rounds  1000 pages: 17 rounds 10000 pages: 18 rounds

A web a hundred times bigger needs just one more round. Each round takes longer (there are more links to follow), but the number of rounds hardly grows. (Adding up the changes matters: with ten thousand pages each share is tiny, so “no single share changed by a millionth” would come true too soon, and the bigger web would seem to need fewer rounds.) Page and Brin measured it the same way on the real web, by the total change from one round to the next: their 1998 report says PageRank on 322 million links settled “in roughly 52 iterations”, and on half of those links in roughly 45. That is why one computer could rank the whole web they had collected: their paper says the PageRank of 26 million pages “can be computed in a few hours on a medium size workstation.”

Ranking by links was the idea that made Google’s results better than its rivals’. It also showed something about the web itself: its millions of authors, each choosing what to link to, had between them already decided which pages were worth reading. PageRank just added up their votes.

A story from science

From BackRub to Google

Larry Page and Sergey Brin met in 1995, when Page was thinking of coming to Stanford for his doctorate and Brin, already a student there, was given the job of showing him around. Google’s own history says that, by some accounts, they disagreed about nearly everything that day. The next year they were working together, from their rooms at the university, on a search engine that used links to judge how important each page was. They called it BackRub. It was renamed Google, a play on googol, the number 1 followed by 100 zeros. In April 1998 they presented “The Anatomy of a Large-Scale Hypertextual Web Search Engine” at a conference in Brisbane, Australia; its prototype held at least 24 million pages. In August 1998 an investor, Andy Bechtolsheim, wrote them a cheque for $100,000, Google Inc. was born, and it moved into its first office: a garage in Menlo Park, California. The method itself was patented as “Method for node ranking in a linked database” (filed in January 1998, granted in 2001), with Page as the inventor and Stanford University as the owner. Stanford licensed it to Google for shares in the company; when it sold them, Stanford’s Office of Technology Licensing reported $336 million in its 2005 annual report, “by far the most lucrative invention we have ever licensed.”

A story from science

The engineer who ranked by links first

Page and Brin weren’t alone. In 1996 Robin Li (Li Yanhong), a young engineer from China working at IDD Information Services, a company in New Jersey, USA, built a search engine called RankDex that used the links pointing to a page, and the words in those links, to decide which pages to show. His patent for it, “Hypertext document retrieval system and method”, was filed in February 1997 and granted in 1999, and Page’s PageRank patent describes Li’s search engine (its address was rankdex.gari.com) among the work that came before it. In 2000 Li went back to China and founded Baidu with Eric Xu. Baidu grew into one of China’s main search engines. Two engineers on opposite sides of the world had seen, at almost the same time, that links say what a page is worth.

Today · checked October 2026

What Google uses today

Google says it still uses PageRank: its guide to its ranking systems (updated December 2025) calls PageRank “one of our core ranking systems used when Google first launched”, says that how it works “has evolved a lot since then”, and that “it continues to be part of our core ranking systems.” It is now one of many systems. Google’s How Search Works pages say its ranking looks at “many factors and signals, including the words of your query, relevance and usability of pages, expertise of sources, and your location and settings”, and that one sign of quality is whether “other prominent websites link or refer to the content.” Since October 2019 a language model, BERT, helps Google understand what a search means (at first for one in ten searches in English in the U.S., Google said then). Google no longer shows anyone a page’s PageRank: its browser toolbar showed a score out of 10 for years, until Google confirmed in March 2016 that it would remove it, and the scores went dark on April 15, 2016. Google’s spam policies call links made mainly to push a page up the rankings link spam: buying or selling links, for example, or swapping links in large numbers (“Link to me and I’ll link to you”).

Going further still

Make a page look important

What if the Curd shop’s owner makes ten new pages, “Fake 1” to “Fake 10”, each linking only to the Curd shop?

Jump home

The jump doesn’t have to go to any page. Page, Brin and their teachers tried a surfer who always jumps to one page: the home page of the Netscape browser, or the home page of the computer scientist John McCarthy. The ranking then shows the web as seen from that page, and they called it personalized PageRank. Change pagerank so that the 15% goes only to the School (and a dead end’s share too). Which pages rise, and which drop to nothing? (The School and the City guide rise most, Nyatapola and Bus times a little; every page you can’t reach from the School by following links drops to 0.)

A question to think about: PageRank measures how much attention the web’s authors give a page. Is the most linked-to page the best answer to your question? When might it not be?

Challenges

Three challenges, each checked on the page: write your function in the program above the checker (press Edit), then press Check my program. The examples show what your function should give; there are more tests you can’t see.

★ Links in

Write links_in(web, page): how many links in web point to page. A page no one links to has 0. (A page linking to itself counts too.)

def links_in(web, page):    # Give back the number of links pointing to page.    return 0 print(links_in({'A': ['B', 'C'], 'B': ['C'], 'C': ['A']}, 'C'))

Page C of the three pages links_in({'A': ['B', 'C'], 'B': ['C'], 'C': ['A']}, 'C') Should give 2 Yours —
The City guide links_in({'City guide': ['Nyatapola', 'Bus times'], 'Nyatapola': ['City guide'], 'Curd shop': ['City guide'], 'Bus times': [], 'School': ['City guide'], 'Photos': ['More photos'], 'More photos': ['Photos', 'City guide'], 'Asha’s blog': ['Curd shop', 'School'], 'Bimal’s blog': ['Curd shop', 'City guide'], 'Dawa’s blog': ['Curd shop', 'Photos']}, 'City guide') Should give 5 Yours —

Tests passed: — / 7
Challenge: ★ solved

Write your links_in in the program above (Edit), then check it.

A test your function gets wrong, anything it prints, and any error appear here.

Hint

Answer

★★ Until it settles

Write rounds_needed(web): how many rounds of sharing (with the jump, as Step 4) it takes until the shares settle: until the changes of all the pages in one round, added up, come to less than 0.000001. Count the round in which that happens.

def rounds_needed(web):    # Give back the number of rounds until the shares settle.    return 0 print(rounds_needed({'A': ['B', 'C'], 'B': ['C'], 'C': ['A']}))

The three pages of the 1998 report rounds_needed({'A': ['B', 'C'], 'B': ['C'], 'C': ['A']}) Should give 28 Yours —
The made-up Bhaktapur web rounds_needed({'City guide': ['Nyatapola', 'Bus times'], 'Nyatapola': ['City guide'], 'Curd shop': ['City guide'], 'Bus times': [], 'School': ['City guide'], 'Photos': ['More photos'], 'More photos': ['Photos', 'City guide'], 'Asha’s blog': ['Curd shop', 'School'], 'Bimal’s blog': ['Curd shop', 'City guide'], 'Dawa’s blog': ['Curd shop', 'Photos']}) Should give 26 Yours —

Tests passed: — / 7
Challenge: ★★ solved

Write your rounds_needed in the program above (Edit), then check it.

A test your function gets wrong, anything it prints, and any error appear here.

Hint

Another hint

Answer

★★★ Which link to ask for?

The owner of page target can ask one other page to add a link to it. Write best_link(web, target): the page whose new link would raise target’s PageRank the most. Leave out target itself and pages that already link to it. Use 50 rounds of sharing, as pagerank in Step 4 does (copy it into your program). Every test has one best page.

def best_link(web, target):    # Give back the page whose new link to target helps target most.    return '' web = {    'City guide': ['Nyatapola', 'Bus times'],    'Nyatapola': ['City guide'],    'Curd shop': ['City guide'],    'Bus times': [],    'School': ['City guide'],    'Photos': ['More photos'],    'More photos': ['Photos', 'City guide'],    'Asha’s blog': ['Curd shop', 'School'],    'Bimal’s blog': ['Curd shop', 'City guide'],    'Dawa’s blog': ['Curd shop', 'Photos'],}print(best_link(web, 'Curd shop'))

The Curd shop best_link({'City guide': ['Nyatapola', 'Bus times'], 'Nyatapola': ['City guide'], 'Curd shop': ['City guide'], 'Bus times': [], 'School': ['City guide'], 'Photos': ['More photos'], 'More photos': ['Photos', 'City guide'], 'Asha’s blog': ['Curd shop', 'School'], 'Bimal’s blog': ['Curd shop', 'City guide'], 'Dawa’s blog': ['Curd shop', 'Photos']}, 'Curd shop') Should give 'Bus times' Yours —
Bus times best_link({'City guide': ['Nyatapola', 'Bus times'], 'Nyatapola': ['City guide'], 'Curd shop': ['City guide'], 'Bus times': [], 'School': ['City guide'], 'Photos': ['More photos'], 'More photos': ['Photos', 'City guide'], 'Asha’s blog': ['Curd shop', 'School'], 'Bimal’s blog': ['Curd shop', 'City guide'], 'Dawa’s blog': ['Curd shop', 'Photos']}, 'Bus times') Should give 'Nyatapola' Yours —

Tests passed: — / 7
Challenge: ★★★ solved

Write your best_link in the program above (Edit), then check it.

A test your function gets wrong, anything it prints, and any error appear here.

Hint

Answer

Questions

In the made-up web, why does Nyatapola rank above the Curd shop?

Pick an answer to see why.

What is the damping factor of 0.85 in PageRank?

Pick an answer to see why.

Explain why, without jumps, almost every surfer ends up on Bus times. What does that do to the ranking?

Answer

Your Step 3 program and your Step 4 program gave nearly the same numbers. One is random and one is not. Why do they agree, and why aren’t they exactly equal?

Answer

A friend’s pagerank gives shares that add up to less than 1, and get smaller every round. What might they have forgotten?

Answer

Google’s spam policies forbid link spam: buying links, or making pages only to link to your own. Using what your programs showed, explain why someone would try them, and why a farm of pages nobody else links to still helps a little.

Answer

Page and Brin’s 1998 report says PageRank settled in roughly 52 rounds on 322 million links and in about 45 on half as many. What does that tell you about using it for the whole web?

Answer

Quiz yourself on this unit →

Where to go next

Grade 10, Graphs, Maps, Routes and Networks: one-way links, and how a crawler finds pages by breadth-first search before anything can rank them.
Grade 9, How the Internet Works: what happens when you open one of the pages a search engine sends you to.
Grade 11, Modeling and Simulation: random simulations (Monte Carlo), like your thousand surfers.
How Can a Computer Never Lose at Tic-Tac-Toe?: another algorithm that looks at a whole graph, the tree of every game.

How Did Google Find the Best Page on the Web?

Try it

One surfer at a time

A trap

How it works: share it out

The jump, in sharing

Program it

Step 1: the web as a dictionary

Step 2: one random surfer

Step 3: a thousand surfers

Step 4: share it out

What your program shows

Going further still

Make a page look important

Jump home

Challenges

★ Links in

★★ Until it settles

★★★ Which link to ask for?

Questions

Where to go next