uni_algo/algo/algorithms/
pagerank.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2024-2026 Dragonscale Team
3
4//! PageRank Centrality Algorithm.
5
6use crate::algo::GraphProjection;
7use crate::algo::algorithms::Algorithm;
8use rayon::prelude::*;
9use uni_common::core::id::Vid;
10
11pub struct PageRank;
12
13#[derive(Debug, Clone)]
14pub struct PageRankConfig {
15    pub damping_factor: f64,
16    pub max_iterations: usize,
17    pub tolerance: f64,
18}
19
20impl Default for PageRankConfig {
21    fn default() -> Self {
22        Self {
23            damping_factor: 0.85,
24            max_iterations: 20,
25            tolerance: 1e-6,
26        }
27    }
28}
29
30pub struct PageRankResult {
31    pub scores: Vec<(Vid, f64)>,
32    pub iterations: usize,
33    pub converged: bool,
34}
35
36impl Algorithm for PageRank {
37    type Config = PageRankConfig;
38    type Result = PageRankResult;
39
40    fn name() -> &'static str {
41        "pageRank"
42    }
43
44    fn needs_reverse() -> bool {
45        true
46    }
47
48    fn run(graph: &GraphProjection, config: Self::Config) -> Self::Result {
49        let n = graph.vertex_count();
50        if n == 0 {
51            return PageRankResult {
52                scores: Vec::new(),
53                iterations: 0,
54                converged: true,
55            };
56        }
57
58        let d = config.damping_factor;
59        let base = (1.0 - d) / n as f64;
60
61        let mut scores = vec![1.0 / n as f64; n];
62        let mut next = vec![0.0; n];
63
64        let mut iterations = 0;
65        let mut converged = false;
66
67        for iter in 0..config.max_iterations {
68            iterations = iter + 1;
69
70            // Parallel iteration over vertices
71            next.par_iter_mut().enumerate().for_each(|(v, score)| {
72                let sum: f64 = graph
73                    .in_neighbors(v as u32)
74                    .iter()
75                    .map(|&u| {
76                        let out_deg = graph.out_degree(u);
77                        if out_deg > 0 {
78                            scores[u as usize] / out_deg as f64
79                        } else {
80                            // Dangling node logic - standard PageRank distributes their score evenly
81                            // but simpler impl often just ignores or handles via sink correction.
82                            // For MVP, we ignore them in the sum (effectively base distributes them).
83                            0.0
84                        }
85                    })
86                    .sum();
87                *score = base + d * sum;
88            });
89
90            // Convergence check
91            let diff: f64 = scores
92                .par_iter()
93                .zip(next.par_iter())
94                .map(|(a, b)| (a - b).abs())
95                .sum();
96
97            std::mem::swap(&mut scores, &mut next);
98
99            if diff < config.tolerance {
100                converged = true;
101                break;
102            }
103        }
104
105        // Map results back to VIDs
106        let results = scores
107            .into_iter()
108            .enumerate()
109            .map(|(slot, score)| (graph.to_vid(slot as u32), score))
110            .collect();
111
112        PageRankResult {
113            scores: results,
114            iterations,
115            converged,
116        }
117    }
118}
uni_algo/algo/algorithms/pagerank.rs

uni_algo/algo/algorithms/
pagerank.rs
