Maths IA · Modelling · topic 91 of 97
How search engines rank pages: PageRank · IB Maths IA idea: guide, sample graph and step-by-step plan
links in, rank outA page is important if important pages link to it. That sounds circular, and it is, until you write it as one equation and let a matrix settle the argument. You're going to rank a small web, and test what the ranking depends on.
- ✓ you like matrices and want to see them do something big
- ✓ you want to rank something with a method you can explain from scratch
- ✓ you can build a small network of links, citations or match results
The big idea
PageRank imagines a surfer who clicks a random link with probability d and otherwise jumps to a random page. The long-run share of time spent on each page is its rank. Write the links as a transition matrix and the ranks are a steady state: the eigenvector for eigenvalue 1 of the damped matrix. You can find it by solving a linear system, or by multiplying repeatedly (the power method) and watching it converge. Matrices and eigenvectors are AI HL content; on AA you would be teaching yourself a whole topic. The set-up is routine. The marks come from asking what changes the ranking: the damping factor, an added link, a page with no links out, or how fast the iteration converges and why.
Make it yours: pick one twist
Copying a classic won't show your choices. Pick one of these (or invent your own) and your IA becomes yours.
Swipe for more twists →
Draw a web of 5 to 8 pages, write the transition matrix column by column, and check that every column adds to 1.
→ A matrix from a picture. Decide what to do with a page that has no outgoing links, because the rules need every column to sum to 1.Solve (I − dM)x = ((1 − d)/n)·1 directly, and also by repeated multiplication from an equal start.
→ Two routes to one answer. Compare them and explain why the answers agree.Rank the same web for d = 0.5, 0.85 and 0.95 and see whether the order of pages changes.
→ A sensitivity study. Find the value of d at which two pages swap places and explain what is happening to the surfer.Plot the error after each multiplication and compare the slope with the second-largest eigenvalue.
→ Links the algorithm to the spectrum of the matrix. Show the rate is at most d, and say why that matters for a huge web.Rank sports teams from head-to-head results, or papers from their citations, using the same method.
→ A new context where you choose what a link means, and compare the ranking with the official table.Add a link from a low-ranked page to a high-ranked page, or remove one, and recompute.
→ Shows how much one link is worth. Ask whether a page could raise its own rank by adding links to itself.Your Maths IA research question: run the check
what is a link here?Write your own question first. Then make sure it ticks every box:
- Names the web or network and says what a link means.
- Says how many pages there are and where the links come from (built by you, or real).
- Names the quantity found: the rank of each page, the order, or the number of iterations needed.
- Says how the damping factor is chosen and varied.
- Says what the answer is checked against: a direct solution, an existing table or a second method.
The model
Each page splits its rank equally among the pages it links to. Draw a small web of your own and write the share on every arrow.
How your Maths IA could be laid out
The usual order for a topic like this, what each part needs to show, and roughly how much of your 12 to 20 pages it takes. The words are all yours.
What is being ranked, why links might measure importance, and a prediction before any calculation.
The web drawn, the transition matrix built and every column checked, with the dangling-page rule.
The damped matrix and why it has a steady state, with the meaning of d.
The steady state by solving equations, and by repeated multiplication with a table of iterations.
Damping factor, an added link or a missing one: a table and a graph of the ranks.
The error after each step against the second eigenvalue, with a graph on a log scale.
Back to your aim: the ranking, how stable it is, and what drove it.
A tiny web against the real one, what 'a link' ignores, and how a rank can be manipulated. Say which matters most.
Where the web, the method and the formulas came from.
What your Maths IA graph could look like
straight line on a log scaleMade-up values to show the form of a strong graph: the error of the power method after each multiplication, on a log scale. Yours will look different. example only
- One point per iteration you computed, with iteration count on the horizontal axis.
- The decay is geometric. A log scale on the vertical axis would make it a straight line, so say so.
- Find the ratio from your own data and compare it with the second-largest eigenvalue.
- Mark the iteration where the error first drops below the precision you promised.
The maths in action
worked through, not sketched!The graph above was a sketch with made-up numbers. This figure works the idea through from the model itself, so you can see what a finished figure looks like. The source line under it says where every number comes from.
Your game plan
Tick steps off as you go. We'll remember on this device.
0 of 10 done
- Read and predictRead how PageRank works. Before any calculation, guess which page of a small web you built will rank first.
- Build the webDraw 5 to 8 pages and their links, or choose a real set of results or citations. Say what a link means.
- Write the matrixBuild the transition matrix column by column and check each column sums to 1. Decide what to do with a page with no links.
- Trial run (1 lesson)Do a three-page web by hand, solving the steady state with equations. Use it to check your matrix software.
- Add dampingBuild the damped matrix with d = 0.85 and explain in words what the random jump does.
- Find the ranksSolve for the steady state, then repeat by multiplying from an equal start. Show the iterations in a table.
- Go further, with a reasonVary d, add or remove a link, or study convergence. HL: this is where the rigour for criterion E comes from.
- Check against somethingCompare your ranks with a known table, such as league positions, or with a second method.
- Reflect as you goAfter every result write one line on what it means for a real search and what it assumes. These lines become your evaluation.
- Cut, check, then sendCheck every matrix is labelled, every symbol is defined once and the conclusion answers your aim. Then send your teacher one draft.
The maths you'll use
- Transition matrix – Build with if page links to page , and check every column sums to 1.
- Damped matrix – Form , where is the all-ones matrix, and show is also a transition matrix.
- Steady state – Solve with , as a linear system and as an eigenvector for eigenvalue 1.
- Iteration – Compute and track the error to show geometric decay at a rate set by the second eigenvalue.
- Sensitivity – Study as a function of and find the value at which two pages swap order.
Key equations
Syllabus links
- No codes for this course.
- 1.14Matrices, determinants and inversesHL
- 1.15Eigenvalues, eigenvectors and matrix powersHL
- 3.14Graph theory: vocabulary and types of graphHL
- 3.15Adjacency matrices, walks and transition matricesHL
- 4.19Markov chains and steady statesHL
- 1.8Solving systems and polynomial equations with technology
Read up first
Data and sources to start from
Build a small web yourself, or use match results or citations as links. Real web crawls are too large to check by hand.
References to cite
- Brin, S., & Page, L. (1998). The anatomy of a large-scale hypertextual web search engine. Computer Networks and ISDN Systems, 30(1-7), 107-117.
- Langville, A. N., & Meyer, C. D. (2006). Google's PageRank and beyond: The science of search engine rankings. Princeton University Press.
Cite what you actually use, in your own format, and say where each number came from.
Traps to avoid in this Maths IA
which sums to 1: rows or columns?- Writing rows instead of columns, or the reverse, and then not checking which of them sum to 1.
- Ignoring pages with no outgoing links. They break the matrix, and the fix is part of your model.
- Using d = 0.85 without saying why, or without testing other values.
- Treating the order of pages as exact when two pages have almost equal rank.
- Claiming the power method converges in 'a few steps' without measuring the error.
- Using a real web of thousands of pages and then being unable to check anything by hand.
More Maths IA ideas like this
Markov chains: what is the long-run weather?●●●
Rating players: how does the Elo system work?●●○
Walk every bridge once: from Königsberg to your city●●○
This guide shows how a topic like this is usually approached. It is not an IA. Your question, choices, data, analysis and words must be your own: change something, tell your teacher where the idea came from, and follow your school's rules on outside help.