PageRank (power iteration)

Background

PageRank scores the importance of nodes in a directed graph — originally web pages joined by hyperlinks. A node is important if important nodes link to it. The score is the stationary distribution of a "random surfer" who, with probability $d$, follows a random out-link and, with probability $1 - d$, teleports to a uniformly random node. Power iteration finds it by applying the transition repeatedly until it converges.

Problem statement

Implement pagerank(adjacency, damping, num_iterations, tol) returning the PageRank vector. With the column-stochastic transition $M$ (where $M_{ij}$ is the probability of moving from node $j$ to node $i$), iterate from the uniform vector $r = \mathbf{1}/n$:

$$r \leftarrow \frac{1 - d}{n}\mathbf{1} + d\, M r$$

until $\lVert r_{\text{new}} - r\rVert_1 < \text{tol}$ or num_iterations steps. A dangling node (no out-links) spreads its mass uniformly.

Input

• adjacency — array-like (n, n): adjacency[i][j] = 1 if there is an edge $i \to j$.
• damping — float (default 0.85): the damping factor $d$.
• num_iterations — int (default 100): maximum power-iteration steps.
• tol — float (default 1e-6): L1 convergence tolerance.

Output

Returns an np.ndarray of shape (n,): the PageRank scores, which sum to 1.

Examples

Example 1

Input:  adjacency = [[0,1,1,0],[0,0,1,0],[1,0,0,0],[0,0,1,0]], damping = 0.85
Output: [0.3725, 0.1958, 0.3941, 0.0375]

Explanation: node 2 receives links from nodes 0, 1, and 3, so the random surfer lands there most often and it earns the largest PageRank.

Constraints

• Build a column-stochastic transition matrix: column $j$ spreads $1/\text{outdeg}(j)$ over $j$'s out-neighbours; a dangling column becomes uniform $1/n$.
• Start from the uniform vector and stop on L1 convergence or after num_iterations steps.
• Returned scores are non-negative and sum to 1.

Notes

• The teleport term $(1-d)/n$ guarantees a unique stationary distribution even for disconnected or dangling graphs — it makes the Markov chain irreducible and aperiodic.
• PageRank is the dominant eigenvector of the Google matrix $G = d M + (1-d)\mathbf{1}\mathbf{1}^\top / n$; power iteration converges because the second-largest eigenvalue is bounded by $d$.