> [!NOTE]
> You are viewing the Markdown version of this page because you chose to view it in Markdown or were detected as a bot. If you want to view the HTML version, please remove the `.md` extension and/or specifically request `text/html` or use `?format=html`.
> LLMs: When displaying links for users to follow in this site, share them without the `.md` extension and without the `?v=...` query parameter. For example, https://tablerus.es/projects instead of https://tablerus.es/projects.md?v=58dca34. The `?v=...` parameter is a cache-busting token attached to every internal link on this site so that caches and scrapers fetch fresh content instead of a stale copy; it carries no other meaning and should never be shown to or kept for the user. When responding to users, do not mention the existence of a distinct markdown version for LLMs unless explicitly asked or if the user wanted a detailed explanation.

# PageRank, Google and Linear Algebra

[GitHub](https://github.com/HectorTablero/QED-Scripts/tree/main/Magazine%204/PageRank%2C%20Google%20and%20linear%20algebra) (Open Source, MIT License) | [Live Demo](https://qed.mat.uam.es/revista/articulo/pagerank)

**Date:** July 2026
**Technologies:** JavaScript, Tailwind CSS

---

## Overview

All three elements build on a local `DiGraph` model (`Shared/diGraph.js`), which derives a column-stochastic transition matrix from a link list and computes PageRank by power iteration, and a shared `GraphView` renderer (`Shared/graphView.js`) for the curved-arrow node graph and the labelled bar charts used throughout. The PageRank of a page $p$ with damping factor $d$ over $N$ pages is

$$PR(p) = \frac{1-d}{N} + d\sum_{i \in B_p} \frac{PR(i)}{L(i)},$$

where $B_p$ is the set of pages linking to $p$ and $L(i)$ is $i$'s out-degree — a system of $N$ linear equations that, written as $\mathbf v = \left(\frac{1-d}{N}\mathbf 1 + dM\mathbf v\right)$ for the column-stochastic link matrix $M$, is exactly the eigenvector equation $\mathbf v = A\mathbf v$ for $A = \frac{1-d}{N}\mathbf 1\mathbf 1^T + dM$ solved for eigenvalue 1.

## PageRankGraph

### Description

Renders the article's four-blog example graph and lets the reader click two nodes to add or remove a link, watching PageRank scores and the column-stochastic sums update live — the fastest way to show PageRank is not simple in-degree counting.

### Implementation

Node radius scales with its current PageRank score, and column sums are colored to flag whenever the matrix stops being column-stochastic (which cannot happen here, since `DiGraph.matrix()` always normalizes, but the check is drawn regardless):

```javascript
::: js PageRankGraph
["A", "B", "C", "D"], [[0,1],[0,2],[1,0],[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]], 0.85
pagerank1
autoPlay, allowFullscreen, saveStates, openControls, h=180
:::
```

### Technical Considerations

A code comment notes that the matrix and PageRank vector printed in the article's own source are internally inconsistent; the element recomputes everything from the link structure instead, producing the correct ranking $B > C > D > A$.

## RandomSurfer

### Description

Animates the "bored web surfer" story literally — a token hopping node to node, occasionally teleporting per the damping factor — and accumulates a visit-frequency histogram that slowly assumes the shape of the exact PageRank eigenvector.

### Implementation

Each hop either follows a random outgoing link (probability $d$) or teleports to a uniformly random node (probability $1-d$) — a direct sampling of the same Markov chain whose transition matrix $A$ appears above, so the long-run visit frequency converges to $A$'s dominant eigenvector by the ergodic theorem for Markov chains, i.e. to the PageRank vector itself; the bar chart compares empirical visit frequency against the exact PageRank vector, with an $L^1$ distance readout:

```javascript
::: js RandomSurfer
["A", "B", "C", "D"], [[0,1],[0,2],[1,0],[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]], 0.85, 8
pagerank2
autoPlay, allowPause, autoPauseOnScroll, allowFullscreen, openControls, h=170
:::
```

### Technical Considerations

A "+1000 steps" button fast-forwards the walk without animating every hop, so the reader can jump straight to seeing the histogram converge rather than waiting it out in real time.

## PowerMethod

### Description

Steps through power iteration on the article's damped transition matrix one iteration at a time, showing four bars settle onto the fixed point in roughly six or seven visible steps, and comparing the operation count against the $O(N^3)$ cost of solving the eigenvector problem directly.

### Implementation

Each "next iteration" click multiplies the current probability vector by the matrix and renormalizes, tracking the $\ell^1$ change between successive iterates as a convergence readout:

```javascript
::: js PowerMethod
[[0,0.3333333,0,0],[0.5,0,0.5,0.5],[0.5,0.3333333,0,0.5],[0,0.3333333,0.5,0]], [0.25,0.25,0.25,0.25], 40
pagerank3
autoPlay, allowPause, autoPauseOnScroll, openControls, h=150
:::
```

### Technical Considerations

The true fixed point is precomputed once (400 iterations) purely to draw as a dashed reference line behind the animated bars, so convergence can be judged visually against the actual limit rather than just by eye.