34_tiny_pagerank/
34_tiny_pagerank.rs

1//! # Example: Tiny PageRank
2//!
3//! Run: cargo run --example 34_tiny_pagerank
4//!
5//! ## Problem
6//! Rank the nodes of a tiny directed graph by importance, where a node is
7//! important if important nodes link to it — the core idea behind PageRank.
8//!
9//! ## Math idea
10//! Build a column-stochastic link matrix `M` (`M[i, j] = 1/outdeg(j)` when `j -> i`).
11//! With damping `d` and `N` nodes, power-iterate
12//! ```text
13//! r_next[i] = (1 - d)/N + d * (M · r)[i]
14//! ```
15//! until `r` settles. The `(1 - d)/N` term is the uniform "teleport" that keeps the
16//! walk from getting stuck.
17//!
18//! ## Tensor representation
19//! `M` is an N×N `Tensor`; the rank vector `r` is a length-N `Tensor`. The matrix
20//! product `M · r` is one `Tensor::matmul` (`[m, n] × [n] -> [m]`); the damping and
21//! teleport are ordinary Rust over `as_slice`.
22//!
23//! ## What this demonstrates
24//! - matrix × vector multiplication via `Tensor::matmul`;
25//! - power iteration (repeated multiply-and-renormalize);
26//! - composing `Tensor` math with plain Rust arithmetic.
27//!
28//! ## Expected output
29//! ```text
30//! PageRank after 50 iterations (d = 0.85):
31//!   node 0: 0.3725
32//!   node 1: 0.1958
33//!   node 2: 0.3941
34//!   node 3: 0.0375
35//! highest-ranked node: 2
36//! Tiny PageRank: OK
37//! ```
38
39use matten::Tensor;
40
41/// One PageRank power-iteration step.
42fn pagerank_step(m: &Tensor, r: &Tensor, damping: f64, n: usize) -> Tensor {
43    let mr = m.matmul(r); // [n, n] × [n] -> [n]
44    let base = (1.0 - damping) / n as f64;
45    let next: Vec<f64> = mr.as_slice().iter().map(|&x| base + damping * x).collect();
46    Tensor::from_vec(next)
47}
48
49fn main() {
50    // Directed graph on 4 nodes:
51    //   0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 3 -> 2
52    // Column-stochastic link matrix M (M[i, j] = share of j's rank flowing to i):
53    //          from: 0    1   2   3
54    //   to 0 [ 0     0    1   0  ]
55    //   to 1 [ 0.5   0    0   0  ]
56    //   to 2 [ 0.5   1    0   1  ]
57    //   to 3 [ 0     0    0   0  ]
58    let m = Tensor::new(
59        vec![
60            0.0, 0.0, 1.0, 0.0, //
61            0.5, 0.0, 0.0, 0.0, //
62            0.5, 1.0, 0.0, 1.0, //
63            0.0, 0.0, 0.0, 0.0, //
64        ],
65        &[4, 4],
66    );
67
68    let n = 4;
69    let damping = 0.85;
70    let mut r = Tensor::from_vec(vec![0.25, 0.25, 0.25, 0.25]);
71    for _ in 0..50 {
72        r = pagerank_step(&m, &r, damping, n);
73    }
74
75    let ranks = r.as_slice();
76    println!("PageRank after 50 iterations (d = {damping}):");
77    for (i, &rank) in ranks.iter().enumerate() {
78        println!("  node {i}: {rank:.4}");
79    }
80
81    // The best-connected node should win; the link-less node 3 only gets teleport.
82    let top = ranks
83        .iter()
84        .enumerate()
85        .max_by(|a, b| a.1.partial_cmp(b.1).unwrap())
86        .map(|(i, _)| i)
87        .unwrap();
88    println!("highest-ranked node: {top}");
89
90    let total: f64 = ranks.iter().sum();
91    assert!((total - 1.0).abs() < 1e-9, "ranks must sum to 1");
92    assert_eq!(top, 2, "node 2 receives the most links");
93    println!("Tiny PageRank: OK");
94}
34_tiny_pagerank/34_tiny_pagerank.rs

34_tiny_pagerank/
34_tiny_pagerank.rs
