Skip to main content

publet_algorithms/
propagate.rs

1//! Personalized `PageRank` over a weighted, labelled graph.
2//!
3//! The iteration is:
4//!
5//! ```text
6//!   W_0     = R
7//!   W_{n+1} = ((10^6 - a) * R  +  a * (W_n . T)) / 10^6
8//!   W       = W_K              where K = params.iterations
9//! ```
10//!
11//! Two properties are load-bearing and both are enforced by construction
12//! rather than by care:
13//!
14//! * **Exactly `K` iterations.** There is no tolerance parameter, so a
15//!   convergence criterion cannot be introduced by accident. Two
16//!   implementations that stop at different points produce different
17//!   numbers, and reproducibility depends on them producing the same ones.
18//! * **Ordered traversal.** Every map here is a [`BTreeMap`]. A `HashMap`
19//!   would make the accumulation order depend on a hash seed, and floating
20//!   point would make that visible; integers hide it, which is worse,
21//!   because the divergence would surface only on a value near a threshold.
22//!
23//! Nodes are plain `String` labels. A caller whose graph is keyed by
24//! something richer -- a content identifier, a database row, a URL --
25//! converts to and from `String` at its own boundary; nothing here needs to
26//! know what the label means, only that two equal labels are the same node.
27
28use std::collections::{BTreeMap, BTreeSet};
29
30use crate::Fixed6;
31
32/// One declared, weighted, directed edge.
33#[derive(Debug, Clone, PartialEq, Eq)]
34pub struct TrustEdge {
35    /// The node conferring weight.
36    pub from: String,
37    /// The node receiving it.
38    pub to: String,
39    /// Declared weight, before normalization.
40    pub weight: Fixed6,
41    /// Age in days, for decay. Zero when the caller applies no half-life.
42    pub age_days: u64,
43    /// Labels this edge is confined to.
44    ///
45    /// Empty means unconfined: the edge applies regardless of context. A
46    /// non-empty list restricts the edge to a query run with a matching
47    /// label in `subjects`, which is what makes a per-context seed weight
48    /// meaningful rather than one more undifferentiated scalar.
49    pub subjects: Vec<String>,
50}
51
52/// One seed weight: a node the walk restarts to, and how much.
53#[derive(Debug, Clone, PartialEq, Eq)]
54pub struct Seed {
55    /// The seeded node.
56    pub key: String,
57    /// Relative seed weight, before normalization.
58    pub weight: Fixed6,
59}
60
61/// The parameters a propagation run needs, independent of any particular
62/// caller's seed-selection policy.
63#[derive(Debug, Clone, Copy, PartialEq, Eq)]
64pub struct Params {
65    /// Damping factor, scaled by 10^6 (see [`crate::SCALE`]).
66    pub damping: Fixed6,
67    /// Exactly how many iterations to run. Never a convergence criterion.
68    pub iterations: u32,
69    /// Half-life for edge decay, in days. `None` disables decay.
70    pub decay_half_life_days: Option<u64>,
71}
72
73/// Weight per node.
74pub type Weights = BTreeMap<String, Fixed6>;
75
76/// Run the propagation to a fixed iteration count.
77///
78/// `edges` need not be sorted; they are grouped deterministically here.
79///
80/// # Example
81///
82/// ```
83/// use publet_algorithms::Fixed6;
84/// use publet_algorithms::propagate::{Params, Seed, TrustEdge, propagate};
85///
86/// let edge = |from: &str, to: &str| TrustEdge {
87///     from: from.into(), to: to.into(), weight: Fixed6::ONE, age_days: 0, subjects: vec![],
88/// };
89/// let params = Params { damping: Fixed6::from_scaled(850_000), iterations: 20, decay_half_life_days: None };
90/// let seeds = [Seed { key: "alice".into(), weight: Fixed6::ONE }];
91/// let edges = [edge("alice", "bob"), edge("bob", "carol"), edge("dave", "erin")];
92///
93/// let weights = propagate(&params, &seeds, &edges);
94/// // Weight flows from the seed along edges, less at each step...
95/// assert!(weights["alice"] > weights["bob"] && weights["bob"] > weights["carol"]);
96/// // ...and never to nodes the seed cannot reach.
97/// assert!(!weights.contains_key("dave") && !weights.contains_key("erin"));
98/// // The same input gives the same output, to the last digit.
99/// assert_eq!(propagate(&params, &seeds, &edges), weights);
100/// ```
101#[must_use]
102pub fn propagate(params: &Params, roots: &[Seed], edges: &[TrustEdge]) -> Weights {
103    propagate_within(params, roots, edges, &[])
104}
105
106/// Propagate for a query confined to the given subjects.
107///
108/// An edge confined to subjects applies only when the query names one of
109/// them. Propagating with no subject context therefore uses the unconfined
110/// edges alone: an edge declared "on Rust terminology" has not said
111/// anything about a query that is not one.
112///
113/// # Example
114///
115/// ```
116/// use publet_algorithms::Fixed6;
117/// use publet_algorithms::propagate::{Params, Seed, TrustEdge, propagate, propagate_within};
118///
119/// let edge = |from: &str, to: &str| TrustEdge {
120///     from: from.into(), to: to.into(), weight: Fixed6::ONE, age_days: 0, subjects: vec![],
121/// };
122/// let params = Params { damping: Fixed6::from_scaled(850_000), iterations: 20, decay_half_life_days: None };
123/// let seeds = [Seed { key: "alice".into(), weight: Fixed6::ONE }];
124/// // alice vouches for bob only on Rust terminology.
125/// let edges = [TrustEdge { subjects: vec!["rust".into()], ..edge("alice", "bob") }];
126///
127/// assert!(!propagate(&params, &seeds, &edges).contains_key("bob"));
128/// assert!(propagate_within(&params, &seeds, &edges, &["rust".into()]).contains_key("bob"));
129/// ```
130#[must_use]
131pub fn propagate_within(
132    params: &Params,
133    roots: &[Seed],
134    edges: &[TrustEdge],
135    subjects: &[String],
136) -> Weights {
137    let edges: Vec<TrustEdge> = edges
138        .iter()
139        .filter(|e| e.subjects.is_empty() || e.subjects.iter().any(|s| subjects.contains(s)))
140        .cloned()
141        .collect();
142    propagate_all(params, roots, &edges)
143}
144
145fn propagate_all(params: &Params, roots: &[Seed], edges: &[TrustEdge]) -> Weights {
146    // Seed vector, normalized to Fixed6::ONE in total.
147    let seed_total: Fixed6 = roots.iter().map(|r| r.weight).sum();
148    let mut seed: Weights = BTreeMap::new();
149    for root in roots {
150        let share = root.weight.mul_div(Fixed6::ONE, seed_total);
151        let entry = seed.entry(root.key.clone()).or_insert(Fixed6::ZERO);
152        *entry = *entry + share;
153    }
154
155    // Outbound edges per node, with decay applied before normalization so
156    // that an old edge confers less rather than merely ranking lower.
157    let mut outbound: BTreeMap<String, BTreeMap<String, Fixed6>> = BTreeMap::new();
158    for edge in edges {
159        let weight = match params.decay_half_life_days {
160            Some(half_life) => edge.weight.halve_fractional(edge.age_days, half_life),
161            None => edge.weight,
162        };
163        let slot = outbound
164            .entry(edge.from.clone())
165            .or_default()
166            .entry(edge.to.clone())
167            .or_insert(Fixed6::ZERO);
168        *slot = *slot + weight;
169    }
170
171    // Per-node normalization: a node's total conferred weight is fixed
172    // regardless of how many nodes it points to, which is what makes a
173    // disconnected subgraph worth zero at every size.
174    let normalized: BTreeMap<String, BTreeMap<String, Fixed6>> = outbound
175        .into_iter()
176        .map(|(from, targets)| {
177            let total: Fixed6 = targets.values().copied().sum();
178            let shares = targets
179                .into_iter()
180                .map(|(to, w)| (to, w.mul_div(Fixed6::ONE, total)))
181                .collect();
182            (from, shares)
183        })
184        .collect();
185
186    let damping = params.damping;
187    let complement = Fixed6::from_scaled(crate::SCALE) - damping;
188    let mut weights = seed.clone();
189
190    for _ in 0..params.iterations {
191        let mut next: Weights = BTreeMap::new();
192        // Seed contribution: (10^6 - a) * R / 10^6.
193        for (key, value) in &seed {
194            let share = value.times(complement);
195            let entry = next.entry(key.clone()).or_insert(Fixed6::ZERO);
196            *entry = *entry + share;
197        }
198        // Propagated contribution: a * (W . T) / 10^6.
199        for (from, share) in &weights {
200            let Some(targets) = normalized.get(from) else {
201                continue;
202            };
203            for (to, fraction) in targets {
204                let contribution = share.times(*fraction).times(damping);
205                let entry = next.entry(to.clone()).or_insert(Fixed6::ZERO);
206                *entry = *entry + contribution;
207            }
208        }
209        weights = next;
210    }
211
212    // Nodes that never received weight are absent rather than zero, so
213    // that callers cannot mistake "not reached" for "reached with
214    // nothing".
215    weights.retain(|_, v| !v.is_zero());
216    weights
217}
218
219/// Nodes reachable from `start` within `distance` hops, over `edges`
220/// treated as undirected.
221///
222/// # Example
223///
224/// ```
225/// use std::collections::BTreeSet;
226/// use publet_algorithms::Fixed6;
227/// use publet_algorithms::propagate::{TrustEdge, reachable_within};
228///
229/// let edge = |from: &str, to: &str| TrustEdge {
230///     from: from.into(), to: to.into(), weight: Fixed6::ONE, age_days: 0, subjects: vec![],
231/// };
232/// let edges = [edge("a", "b"), edge("b", "c"), edge("c", "d")];
233/// // One hop from b, in either direction.
234/// assert_eq!(
235///     reachable_within(&edges, "b", 1),
236///     BTreeSet::from(["a".to_string(), "b".to_string(), "c".to_string()]),
237/// );
238/// ```
239#[must_use]
240pub fn reachable_within(edges: &[TrustEdge], start: &str, distance: u32) -> BTreeSet<String> {
241    let mut adjacency: BTreeMap<&str, BTreeSet<&str>> = BTreeMap::new();
242    for edge in edges {
243        adjacency
244            .entry(edge.from.as_str())
245            .or_default()
246            .insert(edge.to.as_str());
247        adjacency
248            .entry(edge.to.as_str())
249            .or_default()
250            .insert(edge.from.as_str());
251    }
252    let mut seen: BTreeSet<String> = BTreeSet::new();
253    let mut frontier: BTreeSet<&str> = BTreeSet::from([start]);
254    seen.insert(start.to_owned());
255    for _ in 0..distance {
256        let mut next: BTreeSet<&str> = BTreeSet::new();
257        for node in &frontier {
258            if let Some(neighbours) = adjacency.get(node) {
259                for n in neighbours {
260                    if seen.insert((*n).to_owned()) {
261                        next.insert(n);
262                    }
263                }
264            }
265        }
266        frontier = next;
267    }
268    seen
269}