Linear AlgebraApplications2 of 6
Applications · 2

PageRank: Ranking the Web with an Eigenvector

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.

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
AA
BB
CC
DD
12\dfrac{1}{2}
12\dfrac{1}{2}
12\dfrac{1}{2}
12\dfrac{1}{2}
11
11
10\htmlClass{lc-blue}{10}
10\htmlClass{lc-blue}{10}
10\htmlClass{lc-blue}{10}
10\htmlClass{lc-blue}{10}
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 kk outgoing links puts 1k\tfrac{1}{k} in each row it links to, and every column adds to 11:

L=FromAFromBFromCFromDTo ATo BTo CTo D[01212000121210001000]\displaystyle \begin{aligned} & \links{L} = \\ & \begin{array}{rcccc} & \begin{gathered}\scriptstyle\text{From} \\[-3pt] \scriptstyle A\end{gathered} & \begin{gathered}\scriptstyle\text{From} \\[-3pt] \scriptstyle B\end{gathered} & \begin{gathered}\scriptstyle\text{From} \\[-3pt] \scriptstyle C\end{gathered} & \begin{gathered}\scriptstyle\text{From} \\[-3pt] \scriptstyle D\end{gathered} \\[4pt] \begin{array}{r} \text{To } A \\[2pt] \text{To } B \\[2pt] \text{To } C \\[2pt] \text{To } D \end{array} & \left[\begin{array}{c} 0 \\[2pt] \tfrac{1}{2} \\[2pt] \tfrac{1}{2} \\[2pt] 0 \end{array}\right. & \begin{array}{c} 0 \\[2pt] 0 \\[2pt] \tfrac{1}{2} \\[2pt] \tfrac{1}{2} \end{array} & \begin{array}{c} 1 \\[2pt] 0 \\[2pt] 0 \\[2pt] 0 \end{array} & \left.\begin{array}{c} 1 \\[2pt] 0 \\[2pt] 0 \\[2pt] 0 \end{array}\right] \end{array} \end{aligned}

Multiply by L\links{L} to move surfers forward one click. Starting with 10\score{10} surfers on each page, multiplying L\links{L} by the count vector x\score{x} adds up everyone arriving at each page across the rows:

Lx=[00111200012120001200][10101010]=[10+1055+55]=[205105]\displaystyle \begin{aligned} \links{L}\score{x} &= \begin{bmatrix} 0 & 0 & 1 & 1 \\ \tfrac{1}{2} & 0 & 0 & 0 \\ \tfrac{1}{2} & \tfrac{1}{2} & 0 & 0 \\ 0 & \tfrac{1}{2} & 0 & 0 \end{bmatrix} \score{\begin{bmatrix} 10 \\ 10 \\ 10 \\ 10 \end{bmatrix}} \\ &= \begin{bmatrix} 10 + 10 \\ 5 \\ 5 + 5 \\ 5 \end{bmatrix} \\ &= \score{\begin{bmatrix} 20 \\ 5 \\ 10 \\ 5 \end{bmatrix}} \end{aligned}

Set Lx=x\links{L}\score{x} = \score{x} for the long-run steady state. An eigenvector of L\links{L} is a vector that only gets scaled when multiplied by L\links{L} (Lx=λx\links{L}\score{x} = \lambda \score{x}), so the steady state where one more click leaves every page's total unchanged is the eigenvector for eigenvalue λ=1\lambda = 1:

Lx⏟next click\displaystyle \underbrace{\links{L}\score{x}}_{\text{next click}} =1x⏟current counts\displaystyle = \underbrace{1\score{x}}_{\text{current counts}}

So our four flow equations are really the eigenvector equation Lx=x\links{L}\score{x} = \score{x}.

Whether the 40\score{40} surfers start spread out evenly or all 40\score{40} start on the lowest-ranked page DD, the total stays at 40\score{40} on every click and Lkx\links{L^k} \score{x} always settles into the same 16,8,12,4\score{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\links{L}\score{x} = \score{x} to find the steady-state PageRank probability vector x=[ABCD]\score{x} = \score{\begin{bmatrix} A \\ B \\ C \\ D \end{bmatrix}} whose entries add up to 11.

Finding the PageRank Eigenvector
AA
BB
CC
DD
?\htmlClass{lc-blue}{?}
?\htmlClass{lc-blue}{?}
?\htmlClass{lc-blue}{?}
?\htmlClass{lc-blue}{?}
A=C+DB=12AC=12A+12BD=12B\begin{aligned} A &= C + D \\ B &= \tfrac{1}{2}A \\ C &= \tfrac{1}{2}A + \tfrac{1}{2}B \\ D &= \tfrac{1}{2}B \end{aligned}
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=1D = \score{1} in the flow equations Lx=x\links{L}\score{x} = \score{x} and work upward:

D=1D=12B  ⟹  B=2(1)=2B=12A  ⟹  A=2(2)=4C=12A+12B  ⟹  C=12(4)+12(2)=2+1=3\displaystyle \begin{aligned} & D = \score{1} \\ & D = \tfrac{1}{2}B \implies B = 2(\score{1}) = \score{2} \\ & B = \tfrac{1}{2}A \implies A = 2(\score{2}) = \score{4} \\ & C = \tfrac{1}{2}A + \tfrac{1}{2}B \implies C = \tfrac{1}{2}(\score{4}) \\ &\quad + \tfrac{1}{2}(\score{2}) = 2 + 1= \score{3} \end{aligned}

Divide by the total to get a probability vector. Dividing the eigenvector [4231]\score{\begin{bmatrix} 4 \\ 2 \\ 3 \\ 1 \end{bmatrix}} by the sum of its entries, 4+2+3+1=104 + 2 + 3 + 1 = 10, scales the scores so they add up to 11:

x=110[4231]=[0.40.20.30.1]←1st: A (40%)←3rd: B (20%)←2nd: C (30%)←4th: D (10%)\displaystyle \score{x} = \frac{1}{10}\score{\begin{bmatrix} 4 \\ 2 \\ 3 \\ 1 \end{bmatrix}} = \score{\begin{bmatrix} 0.4 \\ 0.2 \\ 0.3 \\ 0.1 \end{bmatrix}} \begin{array}{l} \leftarrow \text{1st: } A \ (\score{40\%}) \\ \leftarrow \text{3rd: } B \ (\score{20\%}) \\ \leftarrow \text{2nd: } C \ (\score{30\%}) \\ \leftarrow \text{4th: } D \ (\score{10\%}) \end{array}

So Page AA ranks first with 40%\score{40\%} of the steady-state traffic, breaking its incoming-link tie with CC (30%\score{30\%}) because CC passes its entire score to AA, while BB (20%\score{20\%}) beats DD (10%\score{10\%}) because BB's single link comes from the top page AA.

When a page adds another outgoing link, its column in L\links{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 end\text{Dead end}
BB
DD
Spider trap\text{Spider trap}
DD
EE
FF
Dead Ends, Spider Traps, and the Google Matrix
AA
BB
CC
DD
L=\htmlClass{lc-violet}{L} =
FromABCD\hspace{2.8099em}\mathllap{\htmlClass{lc-mute}{\text{From}}\hspace{0.3em}}\hspace{1.2397em}\mathclap{A}\hspace{1.5702em}\mathclap{B}\hspace{1.5702em}\mathclap{C}\hspace{1.5702em}\mathclap{D}
12ToA\vphantom{\tfrac{1}{2}}\htmlClass{lc-mute}{\text{To}}\hspace{0.3em}A
120011\vphantom{\tfrac{1}{2}}\hspace{0.7025em}\mathclap{0}\hspace{1.5702em}\mathclap{0}\hspace{1.5702em}\mathclap{1}\hspace{1.5702em}\mathclap{1}
12B\vphantom{\tfrac{1}{2}}B
1212000\vphantom{\tfrac{1}{2}}\hspace{0.7025em}\mathclap{\tfrac{1}{2}}\hspace{1.5702em}\mathclap{0}\hspace{1.5702em}\mathclap{0}\hspace{1.5702em}\mathclap{0}
12C\vphantom{\tfrac{1}{2}}C
12121200\vphantom{\tfrac{1}{2}}\hspace{0.7025em}\mathclap{\tfrac{1}{2}}\hspace{1.5702em}\mathclap{\tfrac{1}{2}}\hspace{1.5702em}\mathclap{0}\hspace{1.5702em}\mathclap{0}
12D\vphantom{\tfrac{1}{2}}D
1201200\vphantom{\tfrac{1}{2}}\hspace{0.7025em}\mathclap{0}\hspace{1.5702em}\mathclap{\tfrac{1}{2}}\hspace{1.5702em}\mathclap{0}\hspace{1.5702em}\mathclap{0}
7

Text solution:

Replace any dead-end zero column with 1N\teleport{\tfrac{1}{N}} in every row. When a page in an NN-page web has no outgoing links, we assume a surfer stuck there jumps at random to any of the NN pages, bringing the column sum back to 11:

[00101200012120001200]⟶[001141200141212014012014]\displaystyle \begin{bmatrix} 0 & 0 & 1 & \deadend{0} \\ \tfrac{1}{2} & 0 & 0 & \deadend{0} \\ \tfrac{1}{2} & \tfrac{1}{2} & 0 & \deadend{0} \\ 0 & \tfrac{1}{2} & 0 & \deadend{0} \end{bmatrix} \longrightarrow \begin{bmatrix} 0 & 0 & 1 & \teleport{\tfrac{1}{4}} \\ \tfrac{1}{2} & 0 & 0 & \teleport{\tfrac{1}{4}} \\ \tfrac{1}{2} & \tfrac{1}{2} & 0 & \teleport{\tfrac{1}{4}} \\ 0 & \tfrac{1}{2} & 0 & \teleport{\tfrac{1}{4}} \end{bmatrix}

Add the 15%\teleport{15\%} random teleportation step. With a damping factor of 0.85\links{0.85}, a surfer follows the page's links 85%\links{85\%} of the time and teleports to a random page 15%\teleport{15\%} of the time (14\teleport{\tfrac{1}{4}} to each of the 44 pages):

xnext=0.85Lx⏟follow links+0.15[14141414]⏟random teleport\displaystyle \score{x_{\text{next}}} = \underbrace{\links{0.85L}\score{x}}_{\text{follow links}} + \underbrace{\teleport{0.15\begin{bmatrix} \tfrac{1}{4} \\ \tfrac{1}{4} \\ \tfrac{1}{4} \\ \tfrac{1}{4} \end{bmatrix}}}_{\text{random teleport}}

Factor out x\score{x} to form the single Google Matrix G\links{G}. Because x\score{x} is a probability vector with A+B+C+D=1A + B + C + D = 1, multiplying the all-14\teleport{\tfrac{1}{4}} matrix by x\score{x} gives [14141414]\teleport{\begin{bmatrix} \tfrac{1}{4} \\ \tfrac{1}{4} \\ \tfrac{1}{4} \\ \tfrac{1}{4} \end{bmatrix}}, letting us combine link-following and teleportation into a single matrix G\links{G} where xnext=Gx\score{x_{\text{next}}} = \links{G}\score{x}:

G=0.85[00111200012120001200]+0.15[14141414141414141414141414141414]=[0.03750.03750.88750.88750.46250.03750.03750.03750.46250.46250.03750.03750.03750.46250.03750.0375]\displaystyle \begin{aligned} & \links{G} = \links{0.85}\begin{bmatrix} 0 & 0 & 1 & 1 \\ \tfrac{1}{2} & 0 & 0 & 0 \\ \tfrac{1}{2} & \tfrac{1}{2} & 0 & 0 \\ 0 & \tfrac{1}{2} & 0 & 0 \end{bmatrix} \\ &\quad + \teleport{0.15\begin{bmatrix} \tfrac{1}{4} & \tfrac{1}{4} & \tfrac{1}{4} & \tfrac{1}{4} \\ \tfrac{1}{4} & \tfrac{1}{4} & \tfrac{1}{4} & \tfrac{1}{4} \\ \tfrac{1}{4} & \tfrac{1}{4} & \tfrac{1}{4} & \tfrac{1}{4} \\ \tfrac{1}{4} & \tfrac{1}{4} & \tfrac{1}{4} & \tfrac{1}{4} \end{bmatrix}} \\[6pt] & = \begin{bmatrix} 0.0375 & 0.0375 & 0.8875 & 0.8875 \\ 0.4625 & 0.0375 & 0.0375 & 0.0375 \\ 0.4625 & 0.4625 & 0.0375 & 0.0375 \\ 0.0375 & 0.4625 & 0.0375 & 0.0375 \end{bmatrix} \end{aligned}

Every column of G\links{G} still adds to 11, and because every entry is positive (at least 0.15×14=0.0375\teleport{0.15} \times \teleport{\tfrac{1}{4}} = \teleport{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\lambda = 1 whose entries add to 11.

8

Calculating the Damped PageRank

Now we want to solve Gx=x\links{G}\score{x} = \score{x} with A+B+C+D=1A + B + C + D = 1 to see how the 15%\teleport{15\%} teleportation rule changes our four-page ranking.

Calculating the Damped PageRank
AA
BB
CC
DD
12\dfrac{1}{2}
12\dfrac{1}{2}
12\dfrac{1}{2}
12\dfrac{1}{2}
11
11
?\htmlClass{lc-blue}{?}
?\htmlClass{lc-blue}{?}
?\htmlClass{lc-blue}{?}
?\htmlClass{lc-blue}{?}
9

Text solution:

Write the damped flow equations. Instead of multiplying out the decimals of G\links{G}, use the split form 0.85Lx+[0.03750.03750.03750.0375]=x\links{0.85L}\score{x} + \teleport{\begin{bmatrix} 0.0375 \\ 0.0375 \\ 0.0375 \\ 0.0375 \end{bmatrix}} = \score{x}:

A=0.85(C+D)+0.0375B=0.425A+0.0375C=0.425A+0.425B+0.0375D=0.425B+0.0375\displaystyle \begin{aligned} A &= \links{0.85}(C + D) + \teleport{0.0375} \\ B &= 0.425A + \teleport{0.0375} \\ C &= 0.425A + 0.425B + \teleport{0.0375} \\ D &= 0.425B + \teleport{0.0375} \end{aligned}

Write BB, CC, and DD in terms of AA. Substitute B=0.425A+0.0375B = 0.425A + \teleport{0.0375} into the equations for CC and DD:

B=0.425A+0.0375C=0.425A+0.425(0.425A+0.0375)+0.0375≈0.606A+0.053D=0.425(0.425A+0.0375)+0.0375≈0.181A+0.053\displaystyle \begin{aligned} B &= 0.425A + \teleport{0.0375} \\ C &= 0.425A \\ &\quad + 0.425(0.425A + \teleport{0.0375}) \\ &\quad + \teleport{0.0375} \\ &\approx 0.606A + 0.053 \\ D &= 0.425(0.425A + \teleport{0.0375}) \\ &\quad + \teleport{0.0375} \\ &\approx 0.181A + 0.053 \end{aligned}

Substitute into A+B+C+D=1A + B + C + D = 1. Adding the four expressions and setting the total probability equal to 11 gives AA, which then gives BB, CC, and DD:

A+(0.425A+0.0375)+(0.606A+0.053)+(0.181A+0.053)=12.211A+0.144=1  ⟹  A≈0.387x=[0.3870.2020.2880.123]\displaystyle \begin{aligned} & A + (0.425A + \teleport{0.0375}) \\ &\quad + (0.606A + 0.053) \\ &\quad + (0.181A + 0.053) = 1 \\ & 2.211A + 0.144 = 1 \\ &\quad \implies A \approx \score{0.387} \\[4pt] & \score{x} = \score{\begin{bmatrix} 0.387 \\ 0.202 \\ 0.288 \\ 0.123 \end{bmatrix}} \end{aligned}

So the 3.75%\teleport{3.75\%} teleportation minimum slightly lowers the top pages (AA drops from 40%\score{40\%} to 38.7%\score{38.7\%} and CC from 30%\score{30\%} to 28.8%\score{28.8\%}) and boosts the lowest page (DD rises from 10%\score{10\%} to 12.3%\score{12.3\%}), while keeping the ranking order A>C>B>DA > C > B > D the same.

When page DD's link is removed to create a dead end or pointed into a two-page loop with BB to create a spider trap, pure link-following under L\links{L} either drains the entire web to zero or traps 100%\score{100\%} of the surfers in the loop, while the 15%\teleport{15\%} random teleportation in G\links{G} keeps letting surfers escape and holds every page at or above the 3.75%\teleport{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 33 or 44 pages, substitution solves Gx=x\links{G}\score{x} = \score{x} in a few lines, but a search engine has to find the λ=1\lambda = 1 eigenvector for N=109N = 10^9 pages. We need a way to compute x\score{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
AA
BB
CC
DD
Gx=x,N=109\htmlClass{lc-violet}{G}\htmlClass{lc-blue}{x} = \htmlClass{lc-blue}{x}, \qquad N = 10^{9}

Instead of solving (G−I)x=0(\links{G} - I)\score{x} = 0 directly, a search engine starts with an even split x0=[1N⋮1N]\score{x_0} = \score{\begin{bmatrix} \tfrac{1}{N} \\ \vdots \\ \tfrac{1}{N} \end{bmatrix}} and steps the Markov chain forward by Power Iteration, multiplying only by the mostly zero link matrix L\links{L} at each step:

xk+1=Gxk=0.85(Lxk)+[0.15N⋮0.15N]\displaystyle \score{x_{k+1}} = \links{G}\score{x_k} = \links{0.85}(\links{L}\score{x_k}) + \teleport{\begin{bmatrix} \tfrac{0.15}{N} \\ \vdots \\ \tfrac{0.15}{N} \end{bmatrix}}

Key concepts

PageRank turns web ranking into finding the steady-state eigenvector (λ=1\lambda = 1) of a Markov transition matrix. You never need the characteristic polynomial det⁡(L−λI)=0\det(\links{L} - \lambda I) = 0 because a Markov matrix whose columns add to 11 always has λ=1\lambda = 1.

Building the link matrix L\links{L} and fixing dead ends

Put each page's outgoing links down its column, splitting 1k\tfrac{1}{k} to each of the kk pages it links to (if AA links to BB and CC, column AA is [01212]\begin{bmatrix} 0 \\ \tfrac{1}{2} \\ \tfrac{1}{2} \end{bmatrix}). 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 [1N⋮1N]\teleport{\begin{bmatrix} \tfrac{1}{N} \\ \vdots \\ \tfrac{1}{N} \end{bmatrix}} so every column adds to 11.

Undamped PageRank (Lx=x\links{L}\score{x} = \score{x})

When the web has no spider traps and no damping is used, write the flow equations from the rows of Lx=x\links{L}\score{x} = \score{x}, set one variable to an easy number (like D=1D = \score{1}) to solve for the relative shares [4231]\score{\begin{bmatrix} 4 \\ 2 \\ 3 \\ 1 \end{bmatrix}}, and divide by the sum of the entries (1010) at the end so the probabilities add to 11.

Damped PageRank and the Google Matrix (Gx=x\links{G}\score{x} = \score{x})

When a spider trap locks surfers in a closed loop, or when a damping factor of 0.85\links{0.85} is used, surfers follow links 85%\links{85\%} of the time and teleport equally across all NN pages 15%\teleport{15\%} of the time:

G=0.85L+0.15[1N⋯1N⋮⋱⋮1N⋯1N],0.85Lx+[0.15N⋮0.15N]=x\displaystyle \begin{aligned} & \links{G} = \links{0.85L} \\ &\quad + \teleport{0.15\begin{bmatrix} \tfrac{1}{N} & \cdots & \tfrac{1}{N} \\ \vdots & \ddots & \vdots \\ \tfrac{1}{N} & \cdots & \tfrac{1}{N} \end{bmatrix}}, \\ & \links{0.85L}\score{x} + \teleport{\begin{bmatrix} \tfrac{0.15}{N} \\ \vdots \\ \tfrac{0.15}{N} \end{bmatrix}} = \score{x} \end{aligned}
Every page gets at least the teleportation minimum 0.15N\teleport{\tfrac{0.15}{N}} (which is 0.05\teleport{0.05} for 33 pages and 0.0375\teleport{0.0375} for 44 pages). Because adding 0.15N\teleport{\tfrac{0.15}{N}} already assumes the entries of x\score{x} add to 11, do not set a variable to 11 and rescale at the end; instead, write the pages in terms of one variable (such as B=0.425A+0.05B = 0.425A + \teleport{0.05}) and substitute directly into A+B+⋯=1A + B + \dots = 1.

Substitution vs. Power Iteration (xk+1=Gxk\score{x_{k+1}} = \links{G}\score{x_k})

For 33 or 44 pages when you want the exact steady state, solve the flow equations by substitution. When stepping forward from a starting vector x0\score{x_0} or ranking a huge web of N=109N = 10^9 pages (where Gaussian elimination on (G−I)x=0(\links{G} - I)\score{x} = 0 would take roughly N3=1027N^3 = 10^{27} operations on a dense 101810^{18}-entry matrix, because teleporting fills in every zero of L\links{L}), skip building G\links{G} and compute xk+1=0.85(Lxk)+[0.15N⋮0.15N]\score{x_{k+1}} = \links{0.85}(\links{L}\score{x_k}) + \teleport{\begin{bmatrix} \tfrac{0.15}{N} \\ \vdots \\ \tfrac{0.15}{N} \end{bmatrix}} directly from the mostly zero link matrix L\links{L}.

11

Practice

1

In a three-page web, Page AA links to BB and CC, Page BB links only to AA, and Page CC links to AA and BB. Write the 3×33 \times 3 link matrix L\links{L} (with columns From A,B,CA, B, C and rows To A,B,CA, B, C), and find how many surfers are on each page after one click if you start with x0=[202020]\score{x_0} = \score{\begin{bmatrix} 20 \\ 20 \\ 20 \end{bmatrix}}.

Put each page's outgoing links down its column so every column adds to 11, then multiply Lx0\links{L}\score{x_0} row by row.

Put the outgoing links from AA, BB, and CC down the first, second, and third columns (be careful not to put outgoing links across the rows, which gives the transposed matrix [0121210012120]\begin{bmatrix} 0 & \tfrac{1}{2} & \tfrac{1}{2} \\ 1 & 0 & 0 \\ \tfrac{1}{2} & \tfrac{1}{2} & 0 \end{bmatrix} where the columns do not all add to 11 and one click mistakenly leaves the counts at [202020]\begin{bmatrix} 20 \\ 20 \\ 20 \end{bmatrix}):
L=[0112120121200]\displaystyle \links{L} = \begin{bmatrix} 0 & 1 & \tfrac{1}{2} \\ \tfrac{1}{2} & 0 & \tfrac{1}{2} \\ \tfrac{1}{2} & 0 & 0 \end{bmatrix}
Multiply L\links{L} by x0=[202020]\score{x_0} = \score{\begin{bmatrix} 20 \\ 20 \\ 20 \end{bmatrix}} to find the surfer counts after one click:
x1=Lx0=[0(20)+1(20)+12(20)12(20)+0(20)+12(20)12(20)+0(20)+0(20)]=[302010]\displaystyle \begin{aligned} \score{x_1} = \links{L}\score{x_0} &= \begin{bmatrix} 0(\score{20}) + 1(\score{20}) + \tfrac{1}{2}(\score{20}) \\ \tfrac{1}{2}(\score{20}) + 0(\score{20}) + \tfrac{1}{2}(\score{20}) \\ \tfrac{1}{2}(\score{20}) + 0(\score{20}) + 0(\score{20}) \end{bmatrix} \\ &= \score{\begin{bmatrix} 30 \\ 20 \\ 10 \end{bmatrix}} \end{aligned}
AA has 30\score{30} surfers, BB has 20\score{20}, and CC has 10\score{10}.
2

In a three-page web, Page AA links to BB and CC, Page BB links only to CC, and Page CC links to AA and BB. Both BB and CC have 22 incoming links, while AA has 11. Write the flow equations for Lx=x\links{L}\score{x} = \score{x}, find the steady-state PageRank probability vector x=[ABC]\score{x} = \score{\begin{bmatrix} A \\ B \\ C \end{bmatrix}} whose entries add to 11, and explain why the tie between BB and CC is broken.

Write what each page receives from its incoming links, set A=2A = \score{2} to clear the fractions, and rescale at the end so A+B+C=1A + B + C = 1.

Because AA and CC each split their score across 22 outgoing links while BB sends all of its score to CC, the flow equations for Lx=x\links{L}\score{x} = \score{x} are:
A=12CB=12A+12CC=12A+B\displaystyle \begin{aligned} A &= \tfrac{1}{2}C \\ B &= \tfrac{1}{2}A + \tfrac{1}{2}C \\ C &= \tfrac{1}{2}A + B \end{aligned}
Setting A=2A = \score{2} gives C=4C = \score{4} from the first equation and B=12(2)+12(4)=1+2=3B = \tfrac{1}{2}(\score{2}) + \tfrac{1}{2}(\score{4}) = 1 + 2 = \score{3} from the second equation (which also checks out in the third equation, C=1+3=4C = 1 + 3 = 4), giving the eigenvector [234]\score{\begin{bmatrix} 2 \\ 3 \\ 4 \end{bmatrix}}. Page CC beats Page BB because BB gives its entire score to CC, whereas CC splits its score between AA and BB.
Don't stop at [234]\score{\begin{bmatrix} 2 \\ 3 \\ 4 \end{bmatrix}}, whose entries add to 99 instead of 11; divide by the total 2+3+4=92 + 3 + 4 = 9 to get the probability vector:
x=[291349]≈[0.2220.3330.444]\displaystyle \score{x} = \score{\begin{bmatrix} \tfrac{2}{9} \\ \tfrac{1}{3} \\ \tfrac{4}{9} \end{bmatrix}} \approx \score{\begin{bmatrix} 0.222 \\ 0.333 \\ 0.444 \end{bmatrix}}
3

In a three-page web, Page AA links only to BB, Page BB links only to CC, and Page CC is a dead end with no outgoing links. Write the initial link matrix L\links{L} and state what happens to the surfer counts over time under L\links{L}; then fix the dead end so every column adds to 11 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 CC has no outgoing links, Column CC of the initial link matrix is all zeros:
L=[000100010]\displaystyle \links{L} = \begin{bmatrix} 0 & 0 & \deadend{0} \\ 1 & 0 & \deadend{0} \\ 0 & 1 & \deadend{0} \end{bmatrix}
Under L\links{L}, surfers reaching CC vanish on the next click, so all the surfer counts drain to [000]\score{\begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix}}.
To fix the dead end, replace the zero column with [131313]\teleport{\begin{bmatrix} \tfrac{1}{3} \\ \tfrac{1}{3} \\ \tfrac{1}{3} \end{bmatrix}} so a surfer on CC jumps to any of the 33 pages with equal probability (be careful not to replace Column CC with [12120]\begin{bmatrix} \tfrac{1}{2} \\ \tfrac{1}{2} \\ 0 \end{bmatrix} by leaving out CC itself, which leads to the wrong vector [152525]\begin{bmatrix} \tfrac{1}{5} \\ \tfrac{2}{5} \\ \tfrac{2}{5} \end{bmatrix}):
[001310130113][ABC]=[ABC]  ⟹  A=13CB=A+13CC=B+13C\displaystyle \begin{bmatrix} 0 & 0 & \teleport{\tfrac{1}{3}} \\ 1 & 0 & \teleport{\tfrac{1}{3}} \\ 0 & 1 & \teleport{\tfrac{1}{3}} \end{bmatrix} \score{\begin{bmatrix} A \\ B \\ C \end{bmatrix}} = \score{\begin{bmatrix} A \\ B \\ C \end{bmatrix}} \implies \begin{aligned} A &= \teleport{\tfrac{1}{3}}C \\ B &= A + \teleport{\tfrac{1}{3}}C \\ C &= B + \teleport{\tfrac{1}{3}}C \end{aligned}
Setting A=1A = \score{1} gives C=3C = \score{3} and B=1+1=2B = 1 + 1 = \score{2}, and dividing [123]\score{\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}} by 1+2+3=61 + 2 + 3 = 6 gives the steady-state PageRank vector:
x=[161312]\displaystyle \score{x} = \score{\begin{bmatrix} \tfrac{1}{6} \\ \tfrac{1}{3} \\ \tfrac{1}{2} \end{bmatrix}}
4

In a three-page web, Page AA links to BB and CC, Page BB links only to CC, and Page CC links only to BB. Find the undamped steady-state probability vector for Lx=x\links{L}\score{x} = \score{x}, then write the Google Matrix G\links{G} using a 0.85\links{0.85} damping factor (where 0.15×13=0.05\teleport{0.15} \times \teleport{\tfrac{1}{3}} = \teleport{0.05} teleports to each page) and find the damped steady-state probability vector for Gx=x\links{G}\score{x} = \score{x}.

Notice which pages link to AA; in the damped web, how do surfers ever reach AA?

Without damping, BB and CC form a spider trap that takes in all traffic from AA and never lets surfers back out, so A=0A = 0 and the traffic splits equally between BB and CC:
xundamped=[00.50.5]\displaystyle \score{x_{\text{undamped}}} = \score{\begin{bmatrix} 0 \\ 0.5 \\ 0.5 \end{bmatrix}}
With damping factor 0.85\links{0.85}, multiply every entry of L\links{L} by 0.85\links{0.85} before adding the 0.05\teleport{0.05} teleportation share (don't add 0.050.05 to L\links{L} before multiplying by 0.850.85, which produces 0.550.55 and 1.051.05 and makes the columns add to 1.151.15 instead of 11):
G=0.85[00012011210]+[0.050.050.050.050.050.050.050.050.05]=[0.050.050.050.4750.050.900.4750.900.05]\displaystyle \begin{aligned} \links{G} &= \links{0.85}\begin{bmatrix} 0 & 0 & 0 \\ \tfrac{1}{2} & 0 & 1 \\ \tfrac{1}{2} & 1 & 0 \end{bmatrix} \\ &\quad + \teleport{\begin{bmatrix} 0.05 & 0.05 & 0.05 \\ 0.05 & 0.05 & 0.05 \\ 0.05 & 0.05 & 0.05 \end{bmatrix}} \\ &= \begin{bmatrix} 0.05 & 0.05 & 0.05 \\ 0.475 & 0.05 & 0.90 \\ 0.475 & 0.90 & 0.05 \end{bmatrix} \end{aligned}
Because no page links to AA, Page AA receives only the 0.05\teleport{0.05} from teleporting (A=0.05A = \teleport{0.05}), and the remaining 1−0.05=0.951 - 0.05 = 0.95 splits equally between BB and CC:
x=[0.050.4750.475]\displaystyle \score{x} = \score{\begin{bmatrix} 0.05 \\ 0.475 \\ 0.475 \end{bmatrix}}
5

In a three-page web, Page AA links to BB and CC, while Pages BB and CC each link only to AA. Find the undamped PageRank vector (Lx=x\links{L}\score{x} = \score{x}) and the damped PageRank vector (Gx=x\links{G}\score{x} = \score{x}) with damping factor 0.85\links{0.85} (where 0.15×13=0.05\teleport{0.15} \times \teleport{\tfrac{1}{3}} = \teleport{0.05} teleports to each page), and explain how damping changes the scores.

Write BB and CC directly in terms of AA using B=0.425A+0.05B = 0.425A + \teleport{0.05}, then substitute both into A+B+C=1A + B + C = 1.

Undamped, A=B+CA = B + C and B=C=12AB = C = \tfrac{1}{2}A; substituting into A+B+C=1A + B + C = 1 gives 2A=12A = 1, so:
xundamped=[0.50.250.25]\displaystyle \score{x_{\text{undamped}}} = \score{\begin{bmatrix} 0.5 \\ 0.25 \\ 0.25 \end{bmatrix}}
Damped, the equations for BB and CC are B=0.85(12A)+0.05=0.425A+0.05B = \links{0.85}(\tfrac{1}{2}A) + \teleport{0.05} = 0.425A + \teleport{0.05} and C=0.425A+0.05C = 0.425A + \teleport{0.05}. Because adding 0.05\teleport{0.05} already assumes A+B+C=1A + B + C = 1, do not set A=1A = 1 to get B=C=0.475B = C = 0.475 and divide [10.4750.475]\begin{bmatrix} 1 \\ 0.475 \\ 0.475 \end{bmatrix} by 1.951.95 (which gives the wrong vector [0.5130.2440.244]\begin{bmatrix} 0.513 \\ 0.244 \\ 0.244 \end{bmatrix}). Instead, substitute BB and CC directly into A+B+C=1A + B + C = 1:
A+(0.425A+0.05)+(0.425A+0.05)=11.85A+0.10=1  ⟹  A=0.901.85=1837≈0.486B=C=0.425(1837)+0.05=1974≈0.257\displaystyle \begin{aligned} & A + (0.425A + \teleport{0.05}) \\ &\quad + (0.425A + \teleport{0.05}) = 1 \\ & 1.85A + 0.10 = 1 \\ &\quad \implies A = \frac{0.90}{1.85} = \frac{18}{37} \\ &\quad \approx \score{0.486} \\ & B = C = 0.425\left(\frac{18}{37}\right) + \teleport{0.05} \\ &\quad = \frac{19}{74}\approx \score{0.257} \end{aligned}
The 5%\teleport{5\%} teleportation share slightly lowers the top page AA and boosts the smaller pages BB and CC while keeping the ranking order the same:
x=[183719741974]≈[0.4860.2570.257]\displaystyle \score{x} = \score{\begin{bmatrix} \tfrac{18}{37} \\ \tfrac{19}{74} \\ \tfrac{19}{74} \end{bmatrix}} \approx \score{\begin{bmatrix} 0.486 \\ 0.257 \\ 0.257 \end{bmatrix}}
6

A four-page web has link matrix L=[000120001200001110]\links{L} = \begin{bmatrix} 0 & 0 & 0 & \tfrac{1}{2} \\ 0 & 0 & 0 & \tfrac{1}{2} \\ 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 \end{bmatrix}. Starting from the equal split x0=[14141414]\score{x_0} = \score{\begin{bmatrix} \tfrac{1}{4} \\ \tfrac{1}{4} \\ \tfrac{1}{4} \\ \tfrac{1}{4} \end{bmatrix}} with damping factor 0.85\links{0.85}, compute one step of Power Iteration x1=Gx0\score{x_1} = \links{G}\score{x_0} without writing out the full matrix G\links{G}, and give the two reasons why a search engine with 10910^9 pages uses Power Iteration instead of Gaussian elimination on (G−I)x=0(\links{G} - I)\score{x} = 0.

Multiply Lx0\links{L}\score{x_0} first, multiply that vector by 0.85\links{0.85}, and add the 0.15(14)=0.0375\teleport{0.15}(\teleport{\tfrac{1}{4}}) = \teleport{0.0375} teleportation boost to every entry.

For N=109N = 10^9 pages, Gaussian elimination takes roughly N3=1027N^3 = 10^{27} operations and requires storing the full 109×109=101810^9 \times 10^9 = 10^{18}-entry matrix G−I\links{G} - I, because teleporting fills in every zero of the mostly zero link matrix, whereas Power Iteration needs only 5050 to 100100 multiplications with the mostly zero matrix L\links{L} and never builds the full matrix G\links{G} in memory.
To compute x1=Gx0\score{x_1} = \links{G}\score{x_0}, first multiply by the link matrix L\links{L}:
Lx0=[000120001200001110][14141414]=[1818034]=[0.1250.12500.75]\displaystyle \begin{aligned} \links{L}\score{x_0} &= \begin{bmatrix} 0 & 0 & 0 & \tfrac{1}{2} \\ 0 & 0 & 0 & \tfrac{1}{2} \\ 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 \end{bmatrix} \score{\begin{bmatrix} \tfrac{1}{4} \\ \tfrac{1}{4} \\ \tfrac{1}{4} \\ \tfrac{1}{4} \end{bmatrix}} \\ &= \score{\begin{bmatrix} \tfrac{1}{8} \\ \tfrac{1}{8} \\ 0 \\ \tfrac{3}{4} \end{bmatrix}} = \score{\begin{bmatrix} 0.125 \\ 0.125 \\ 0 \\ 0.75 \end{bmatrix}} \end{aligned}
Next, multiply Lx0\links{L}\score{x_0} by 0.85\links{0.85} and add each page's teleportation share 0.15×14=0.0375\teleport{0.15} \times \teleport{\tfrac{1}{4}} = \teleport{0.0375} to each entry (be careful not to add the full 0.150.15 to every entry, which gives [0.256250.256250.150.7875]\begin{bmatrix} 0.25625 \\ 0.25625 \\ 0.15 \\ 0.7875 \end{bmatrix} whose entries add to 1.451.45 instead of 11):
x1=0.85[0.1250.12500.75]+[0.03750.03750.03750.0375]=[0.143750.143750.03750.675]\displaystyle \begin{aligned} \score{x_1} &= \links{0.85}\score{\begin{bmatrix} 0.125 \\ 0.125 \\ 0 \\ 0.75 \end{bmatrix}} + \teleport{\begin{bmatrix} 0.0375 \\ 0.0375 \\ 0.0375 \\ 0.0375 \end{bmatrix}} \\ &= \score{\begin{bmatrix} 0.14375 \\ 0.14375 \\ 0.0375 \\ 0.675 \end{bmatrix}} \end{aligned}