Skip to content
Tutorials Center
My learning

Topics

Lesson 53 of 62 ยท Projects

Project: PageRank

Build PageRank from scratch: turn links into a stochastic matrix, run power iteration, add damping and dangling pages, and check the result against an eigenvector.

When a search engine has to order a million pages that all contain your keywords, it needs a score that does not depend on the words. PageRank's answer is beautifully linear-algebraic: a page is important if important pages link to it. That sentence sounds circular, and it is. Linear algebra turns the circle into an equation you can solve, and the solution is an eigenvector.

In this project you will describe a tiny website as a matrix, watch a random surfer's probabilities settle down, repair the two ways the idea breaks (pages nobody links to, pages that link nowhere), and confirm your answer with np.linalg.eig. You only need matrix-vector products and a first look at eigenvectors.

The random surfer

Click a link From a page, follow one of its links at random.
Repeat forever Keep surfing for a very long time.
Count visits Pages visited most often are the most important.

The long-run visit frequencies are the PageRank scores.

1 / 2

Step 1: a tiny web as a matrix

Our site has six pages. Each page lists the pages it links to.

Python From links to an adjacency matrix

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

We put the source in the column and the target in the row on purpose. Column j then describes everything page j does, and multiplying the matrix by a vector spreads the vector's mass along the links (the column-combination view). The row sums count incoming links: Home has four, About has none. Nobody links to About, which will matter later.

Step 2: make the columns probabilities

A surfer on a page with three links picks each with probability 1/3. So we divide every column by its sum. The result M is a column-stochastic matrix: all entries are at least 0 and every column adds up to 1.

If r is a vector of probabilities saying where the surfer might be right now, then M @ r says where she might be after one more click. Probabilities in, probabilities out: the entries of M @ r still add up to 1.

Python One click at a time

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

After five clicks, About has already dropped to exactly 0 and the other numbers are bouncing around Home's 0.33 and Docs' 0.32. The bouncing shrinks with every step. Let the loop run 100 times and the vector stops changing: that final r satisfies M @ r = r. Written as M r = 1 r, it is an eigenvector of M with eigenvalue 1.

Step 3: power iteration and the eigenvector check

Repeatedly multiplying by a matrix is called power iteration (it computes M^k r, a matrix power). It converges to the eigenvector of the largest eigenvalue, because that direction is stretched the most, and every other direction fades. For a stochastic matrix the largest eigenvalue is exactly 1.

We can verify this by asking NumPy for the eigenvectors directly. An eigenvector can be scaled arbitrarily (and even has an arbitrary sign), so we rescale it to add up to 1 before comparing.

Python Power iteration versus np.linalg.eig

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both methods agree: Home and Docs share the top spot at about 0.316, Help follows with 0.158, and Blog and Shop get 0.105. About scores 0. The power method is the practical choice, because for a web of billions of pages you cannot afford a full eigen-decomposition. Each iteration is one sparse matrix-vector product.

Power iteration needs a start vector that is not exactly perpendicular to the answer. A uniform start vector works for every graph in this lesson. The convergence speed depends on the gap between the largest and the second-largest eigenvalue size.

Step 4: two problems and one fix

The plain model has two flaws.

  • Dangling pages have no outgoing links. Their column sums to 0, so dividing by the link count produces nan, and probability leaks out of the system. The standard repair: a surfer who reaches a dead end jumps to a random page, so we fill that column with 1/n.
  • Unreachable pages and traps. About has no incoming links and gets score 0 forever, and groups of pages that only link to each other can swallow all the probability. Real graphs have both.

The fix for the second flaw is damping. With probability d (usually 0.85) the surfer follows a link; with probability 1 - d she gets bored and jumps to a uniformly random page. One step becomes:

TEXT
r_new = d * (M @ r) + (1 - d) / n

The second term adds the same small amount to every page. In matrix form this is a new stochastic matrix G = d * M + (1 - d) / n, sometimes called the Google matrix, which has every entry positive. That guarantees a single, unique steady state.

flowchart LR
    S["Surfer on a page"] -->|"probability d"| L["Follow a random<br/>outgoing link"]
    S -->|"probability 1 - d"| J["Jump to a random<br/>page"]
    L --> N["Next page"]
    J --> N

Damping gives every page a small guaranteed share of visits, so no page is stuck at zero.

Python PageRank with damping, as a function

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

About now has a score of 0.025 instead of 0, which is exactly the share the random jumps give it: (1 - 0.85) / 6. When Shop becomes a dead end, the other pages keep valid scores that still add up to 1, and Home loses ground because Shop no longer feeds it.

Step 5: explore the damping factor

Damping is a trade-off. A small d means the surfer jumps a lot, scores flatten toward equal and the iteration converges fast. A d close to 1 trusts the link structure more but needs many more steps. You can also confirm the result is a true eigenvector of the Google matrix, and watch a simulated surfer reproduce the numbers.

Python Damping, eigenvalues and a simulated surfer

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The three runs show the trade-off clearly: 24 steps at d = 0.5, 63 at 0.85 and 118 at 0.99, while About's score shrinks toward 0 as damping loosens its grip. The Google matrix has one eigenvalue of size 1, and the second one is about 0.72, which is below 0.85. That gap is why the iteration converges, and the size of that second eigenvalue sets how fast the error shrinks: roughly by a factor of 0.72 per step here (never worse than 0.85). The eigenvector and the simulated surfer both match the power iteration to about two decimals.

Ideas to extend it

  • Give a page a hundred times more links to it and see how the rank moves.
  • Store M with scipy.sparse (sparse matrices) so the same code scales to a graph with a million pages.
  • Personalize: replace the uniform jump 1/n with a vector that favours your favourite pages.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the link matrix used here, what does column j contain?

    Column j is the source page. Its entries say how likely the surfer is to land on each target after one click, which is why every column sums to 1.
  2. 2. The PageRank vector satisfies M r = r. What does that make r?

    An eigenvector keeps its direction under the matrix. Here the matrix leaves r completely unchanged, so the eigenvalue is 1.
  3. 3. Why do we add damping?

    Random jumps with probability 1 - d make every entry of the Google matrix positive, so no page is stuck at zero and the steady state is unique.
  4. 4. What happens to a dangling page's column when we divide by its out-degree of 0?

    0/0 gives nan with a warning. The usual repair is to let a surfer on a dead end jump to a random page, so the column becomes 1/n everywhere.

Summary

  • Put "page j links to page i" in entry [i, j], then divide each column by its sum to get a column-stochastic matrix M.
  • M @ r moves a probability vector one click; repeating it is power iteration and converges to the eigenvector for eigenvalue 1.
  • Dangling pages are fixed by letting the surfer jump anywhere; damping r = d * M @ r + (1 - d) / n guarantees a unique answer.
  • A larger damping factor trusts the links more but needs more iterations.
  • np.linalg.eig confirms the answer, after rescaling the eigenvector so its entries sum to 1.

Next project: A Matrix-Factorization Recommender.