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(¶ms, &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(¶ms, &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(¶ms, &seeds, &edges).contains_key("bob"));
128/// assert!(propagate_within(¶ms, &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}