We need a way for a computer to rank thousands of web pages that match a search so the most important page appears at the top.
1
Turning Links into Votes
A link from one page to another acts as a vote of confidence, but simply counting incoming links creates ties and lets anyone cheat by making fake pages that point to their site. Instead, we weigh each vote by the importance of the page casting it, and split a page's vote equally among all of its outgoing links.
Ranking Web Pages with Links
Setting each page's score equal to the shares arriving from its incoming links gives four flow equations for our four-page web:
ABCD=C+D=21A=21A+21B=21B
Because A's score depends on C and C's score depends on A, we cannot find the scores one page at a time by direct arithmetic.
2
Random Surfers and the Link Matrix
To get around this loop, we track where random web surfers end up over time as they click outgoing links at random, turning the web into a Markov chain. We want to build the transition matrix for this chain and find where the surfer counts stop changing.
Random Surfers and the Link Matrix
3
Text solution:
Write the link matrix from the outgoing splits. Each column records where the surfers leaving one page go on the next click, so a page with k outgoing links puts k1 in each row it links to, and every column adds to 1:
L=To ATo BTo CTo DFromA021210FromB002121FromC1000FromD1000
Multiply by L to move surfers forward one click. Starting with 10 surfers on each page, multiplying L by the count vector x adds up everyone arriving at each page across the rows:
Set Lx=x for the long-run steady state. An eigenvector of L is a vector that only gets scaled when multiplied by L (Lx=λx), so the steady state where one more click leaves every page's total unchanged is the eigenvector for eigenvalue λ=1:
next clickLx=current counts1x
So our four flow equations are really the eigenvector equation Lx=x.
Whether the 40 surfers start spread out evenly or all 40 start on the lowest-ranked page D, the total stays at 40 on every click and Lkx always settles into the same 16,8,12,4 steady state where the surfers arriving at each page match the surfers leaving it.
No matter how the 40 surfers start across the four pages, splitting them equally down each link at every click keeps all 40 in the web and always settles into the same final balance.
4
Finding the PageRank Eigenvector
Now we want to solve Lx=x to find the steady-state PageRank probability vector x=ABCD whose entries add up to 1.
Finding the PageRank Eigenvector
5
Text solution:
Pick an easy value for one page and solve from the bottom up. Because any nonzero multiple of an eigenvector is still an eigenvector, we can set D=1 in the flow equations Lx=x and work upward:
Divide by the total to get a probability vector. Dividing the eigenvector 4231 by the sum of its entries, 4+2+3+1=10, scales the scores so they add up to 1:
So Page A ranks first with 40% of the steady-state traffic, breaking its incoming-link tie with C (30%) because C passes its entire score to A, while B (20%) beats D (10%) because B's single link comes from the top page A.
When a page adds another outgoing link, its column in L splits its existing score across more arrows rather than creating new importance, while an unshared incoming link from a top-ranked page gives a much larger boost than links from low-ranked pages.
Each page splits its traffic equally among its outgoing links, so a single link from a top-ranked page sends far more traffic than links from a low-ranked page.
6
Dead Ends, Spider Traps, and the Google Matrix
On the real web, pure link-following breaks down when surfers hit a dead end (a page with no outgoing links, where surfers vanish) or a spider trap (a closed loop of pages with no links pointing out, so surfers who enter it can never leave). We need to adjust our transition matrix so surfers can always escape both traps.
Dead Ends, Spider Traps, and the Google Matrix
7
Text solution:
Replace any dead-end zero column with N1 in every row. When a page in an N-page web has no outgoing links, we assume a surfer stuck there jumps at random to any of the N pages, bringing the column sum back to 1:
Add the 15% random teleportation step. With a damping factor of 0.85, a surfer follows the page's links 85% of the time and teleports to a random page 15% of the time (41 to each of the 4 pages):
Factor out x to form the single Google Matrix G. Because x is a probability vector with A+B+C+D=1, multiplying the all-41 matrix by x gives 41414141, letting us combine link-following and teleportation into a single matrix G where xnext=Gx:
Every column of G still adds to 1, and because every entry is positive (at least 0.15×41=0.0375), this Markov chain cannot get stuck in any trap and is guaranteed to have a single steady-state probability vector, the eigenvector for λ=1 whose entries add to 1.
8
Calculating the Damped PageRank
Now we want to solve Gx=x with A+B+C+D=1 to see how the 15% teleportation rule changes our four-page ranking.
Calculating the Damped PageRank
9
Text solution:
Write the damped flow equations. Instead of multiplying out the decimals of G, use the split form 0.85Lx+0.03750.03750.03750.0375=x:
So the 3.75% teleportation minimum slightly lowers the top pages (A drops from 40% to 38.7% and C from 30% to 28.8%) and boosts the lowest page (D rises from 10% to 12.3%), while keeping the ranking order A>C>B>D the same.
When page D's link is removed to create a dead end or pointed into a two-page loop with B to create a spider trap, pure link-following under L either drains the entire web to zero or traps 100% of the surfers in the loop, while the 15% random teleportation in G keeps letting surfers escape and holds every page at or above the 3.75% minimum.
A dead end or a spider trap breaks pure link-following, while random teleportation keeps traffic flowing and holds every page above a baseline floor.
10
Power Iteration for a Billion Pages
With 3 or 4 pages, substitution solves Gx=x in a few lines, but a search engine has to find the λ=1 eigenvector for N=109 pages. We need a way to compute x when the matrix is far too large to row-reduce or even store in memory as a full grid.
Power Iteration for a Billion Pages
Instead of solving (G−I)x=0 directly, a search engine starts with an even split x0=N1⋮N1 and steps the Markov chain forward by Power Iteration, multiplying only by the mostly zero link matrix L at each step:
xk+1=Gxk=0.85(Lxk)+N0.15⋮N0.15
Key concepts
PageRank turns web ranking into finding the steady-state eigenvector (λ=1) of a Markov transition matrix. You never need the characteristic polynomial det(L−λI)=0 because a Markov matrix whose columns add to 1 always has λ=1.
Building the link matrix L and fixing dead ends
Put each page's outgoing links down its column, splitting k1 to each of the k pages it links to (if A links to B and C, column A is 02121). If a page is a dead end with no outgoing links, its column of all zeros drains surfers to zero; replace that zero column with N1⋮N1 so every column adds to 1.
Undamped PageRank (Lx=x)
When the web has no spider traps and no damping is used, write the flow equations from the rows of Lx=x, set one variable to an easy number (like D=1) to solve for the relative shares 4231, and divide by the sum of the entries (10) at the end so the probabilities add to 1.
Damped PageRank and the Google Matrix (Gx=x)
When a spider trap locks surfers in a closed loop, or when a damping factor of 0.85 is used, surfers follow links 85% of the time and teleport equally across all N pages 15% of the time:
Every page gets at least the teleportation minimum N0.15 (which is 0.05 for 3 pages and 0.0375 for 4 pages). Because adding N0.15 already assumes the entries of x add to 1, do not set a variable to 1 and rescale at the end; instead, write the pages in terms of one variable (such as B=0.425A+0.05) and substitute directly into A+B+⋯=1.
Substitution vs. Power Iteration (xk+1=Gxk)
For 3 or 4 pages when you want the exact steady state, solve the flow equations by substitution. When stepping forward from a starting vector x0 or ranking a huge web of N=109 pages (where Gaussian elimination on (G−I)x=0 would take roughly N3=1027 operations on a dense 1018-entry matrix, because teleporting fills in every zero of L), skip building G and compute xk+1=0.85(Lxk)+N0.15⋮N0.15 directly from the mostly zero link matrix L.
11
Practice
1
In a three-page web, Page A links to B and C, Page B links only to A, and Page C links to A and B. Write the 3×3 link matrix L (with columns From A,B,C and rows To A,B,C), and find how many surfers are on each page after one click if you start with x0=202020.
Put each page's outgoing links down its column so every column adds to 1, then multiply Lx0 row by row.
Put the outgoing links from A,B, and C down the first, second, and third columns (be careful not to put outgoing links across the rows, which gives the transposed matrix 0121210212100 where the columns do not all add to 1 and one click mistakenly leaves the counts at 202020):
L=0212110021210
Multiply L by x0=202020 to find the surfer counts after one click:
In a three-page web, Page A links to B and C, Page B links only to C, and Page C links to A and B. Both B and C have 2 incoming links, while A has 1. Write the flow equations for Lx=x, find the steady-state PageRank probability vector x=ABC whose entries add to 1, and explain why the tie between B and C is broken.
Don't stop at 234, whose entries add to 9 instead of 1; divide by the total 2+3+4=9 to get the probability vector.
Write what each page receives from its incoming links, set A=2 to clear the fractions, and rescale at the end so A+B+C=1.
Because A and C each split their score across 2 outgoing links while B sends all of its score to C, the flow equations for Lx=x are:
ABC=21C=21A+21C=21A+B
Setting A=2 gives C=4 from the first equation and B=21(2)+21(4)=1+2=3 from the second equation (which also checks out in the third equation, C=1+3=4), giving the eigenvector 234. Page C beats Page B because B gives its entire score to C, whereas C splits its score between A and B.
Don't stop at 234, whose entries add to 9 instead of 1; divide by the total 2+3+4=9 to get the probability vector:
x=923194≈0.2220.3330.444
3
In a three-page web, Page A links only to B, Page B links only to C, and Page C is a dead end with no outgoing links. Write the initial link matrix L and state what happens to the surfer counts over time under L; then fix the dead end so every column adds to 1 and find the steady-state PageRank probability vector.
A dead-end page has a column of zeros; replace that column with equal probabilities to all three pages before solving for the steady state.
Because Page C has no outgoing links, Column C of the initial link matrix is all zeros:
L=010001000
Under L, surfers reaching C vanish on the next click, so all the surfer counts drain to 000.
To fix the dead end, replace the zero column with 313131 so a surfer on C jumps to any of the 3 pages with equal probability (be careful not to replace Column C with 21210 by leaving out C itself, which leads to the wrong vector 515252):
Setting A=1 gives C=3 and B=1+1=2, and dividing 123 by 1+2+3=6 gives the steady-state PageRank vector:
x=613121
4
In a three-page web, Page A links to B and C, Page B links only to C, and Page C links only to B. Find the undamped steady-state probability vector for Lx=x, then write the Google Matrix G using a 0.85 damping factor (where 0.15×31=0.05 teleports to each page) and find the damped steady-state probability vector for Gx=x.
Notice which pages link to A; in the damped web, how do surfers ever reach A?
Without damping, B and C form a spider trap that takes in all traffic from A and never lets surfers back out, so A=0 and the traffic splits equally between B and C:
xundamped=00.50.5
With damping factor 0.85, multiply every entry of L by 0.85 before adding the 0.05 teleportation share (don't add 0.05 to L before multiplying by 0.85, which produces 0.55 and 1.05 and makes the columns add to 1.15 instead of 1):
Because no page links to A, Page A receives only the 0.05 from teleporting (A=0.05), and the remaining 1−0.05=0.95 splits equally between B and C:
x=0.050.4750.475
5
In a three-page web, Page A links to B and C, while Pages B and C each link only to A. Find the undamped PageRank vector (Lx=x) and the damped PageRank vector (Gx=x) with damping factor 0.85 (where 0.15×31=0.05 teleports to each page), and explain how damping changes the scores.
Write B and C directly in terms of A using B=0.425A+0.05, then substitute both into A+B+C=1.
Undamped, A=B+C and B=C=21A; substituting into A+B+C=1 gives 2A=1, so:
xundamped=0.50.250.25
Damped, the equations for B and C are B=0.85(21A)+0.05=0.425A+0.05 and C=0.425A+0.05. Because adding 0.05 already assumes A+B+C=1, do not set A=1 to get B=C=0.475 and divide 10.4750.475 by 1.95 (which gives the wrong vector 0.5130.2440.244). Instead, substitute B and C directly into A+B+C=1:
The 5% teleportation share slightly lowers the top page A and boosts the smaller pages B and C while keeping the ranking order the same:
x=371874197419≈0.4860.2570.257
6
A four-page web has link matrix L=000100010001212100. Starting from the equal split x0=41414141 with damping factor 0.85, compute one step of Power Iteration x1=Gx0 without writing out the full matrix G, and give the two reasons why a search engine with 109 pages uses Power Iteration instead of Gaussian elimination on (G−I)x=0.
Be careful not to add the full 0.15 to every entry, which gives 0.256250.256250.150.7875 whose entries add to 1.45 instead of 1.
Multiply Lx0 first, multiply that vector by 0.85, and add the 0.15(41)=0.0375 teleportation boost to every entry.
For N=109 pages, Gaussian elimination takes roughly N3=1027 operations and requires storing the full 109×109=1018-entry matrix G−I, because teleporting fills in every zero of the mostly zero link matrix, whereas Power Iteration needs only 50 to 100 multiplications with the mostly zero matrix L and never builds the full matrix G in memory.
To compute x1=Gx0, first multiply by the link matrix L:
Next, multiply Lx0 by 0.85 and add each page's teleportation share 0.15×41=0.0375 to each entry (be careful not to add the full 0.15 to every entry, which gives 0.256250.256250.150.7875 whose entries add to 1.45 instead of 1):