petgraph/algo/
page_rank.rs

Help
1use alloc::{vec, vec::Vec};
2
3use super::UnitMeasure;
4use crate::visit::{EdgeRef, IntoEdges, NodeCount, NodeIndexable};
5
6#[cfg(feature = "rayon")]
7use rayon::prelude::*;
8
9/// \[Generic\] Page Rank algorithm.
10///
11/// Computes the ranks of every node in a graph using the [Page Rank algorithm][pr].
12///
13/// Returns a `Vec` container mapping each node index to its rank.
14///
15/// # Panics
16/// The damping factor should be a number of type `f32` or `f64` between 0 and 1 (0 and 1 included). Otherwise, it panics.
17///
18/// # Complexity
19/// Time complexity is **O(N|V|²|E|)**.
20/// Space complexity is **O(|V| + |E|)**
21/// where **N** is the number of iterations, **|V|** the number of vertices (i.e nodes) and **|E|** the number of edges.
22///
23/// [pr]: https://en.wikipedia.org/wiki/PageRank
24///
25/// # Example
26/// ```rust
27/// use petgraph::Graph;
28/// use petgraph::algo::page_rank;
29/// let mut g: Graph<(), usize> = Graph::new();
30/// assert_eq!(page_rank(&g, 0.5_f64, 1), vec![]); // empty graphs have no node ranks.
31/// let a = g.add_node(());
32/// let b = g.add_node(());
33/// let c = g.add_node(());
34/// let d = g.add_node(());
35/// let e = g.add_node(());
36/// g.extend_with_edges(&[(0, 1), (0, 3), (1, 2), (1, 3)]);
37/// // With the following dot representation.
38/// //digraph {
39/// //    0 [ label = "()" ]
40/// //    1 [ label = "()" ]
41/// //    2 [ label = "()" ]
42/// //    3 [ label = "()" ]
43/// //    4 [ label = "()" ]
44/// //    0 -> 1 [ label = "0.0" ]
45/// //    0 -> 3 [ label = "0.0" ]
46/// //    1 -> 2 [ label = "0.0" ]
47/// //    1 -> 3 [ label = "0.0" ]
48/// //}
49/// let damping_factor = 0.7_f32;
50/// let number_iterations = 10;
51/// let output_ranks = page_rank(&g, damping_factor, number_iterations);
52/// let expected_ranks = vec![0.14685437, 0.20267677, 0.22389607, 0.27971846, 0.14685437];
53/// assert_eq!(expected_ranks, output_ranks);
54/// ```
55#[track_caller]
56pub fn page_rank<G, D>(graph: G, damping_factor: D, nb_iter: usize) -> Vec<D>
57where
58    G: NodeCount + IntoEdges + NodeIndexable,
59    D: UnitMeasure + Copy,
60{
61    let node_count = graph.node_count();
62    if node_count == 0 {
63        return vec![];
64    }
65    assert!(
66        D::zero() <= damping_factor && damping_factor <= D::one(),
67        "Damping factor should be between 0 et 1."
68    );
69    let nb = D::from_usize(node_count);
70    let mut ranks = vec![D::one() / nb; node_count];
71    let nodeix = |i| graph.from_index(i);
72    let out_degrees: Vec<D> = (0..node_count)
73        .map(|i| graph.edges(nodeix(i)).map(|_| D::one()).sum::<D>())
74        .collect();
75
76    for _ in 0..nb_iter {
77        let pi = (0..node_count)
78            .enumerate()
79            .map(|(v, _)| {
80                ranks
81                    .iter()
82                    .enumerate()
83                    .map(|(w, r)| {
84                        let mut w_out_edges = graph.edges(nodeix(w));
85                        if w_out_edges.any(|e| e.target() == nodeix(v)) {
86                            damping_factor * *r / out_degrees[w]
87                        } else if out_degrees[w] == D::zero() {
88                            damping_factor * *r / nb // stochastic matrix condition
89                        } else {
90                            (D::one() - damping_factor) * *r / nb // random jumps
91                        }
92                    })
93                    .sum::<D>()
94            })
95            .collect::<Vec<D>>();
96        let sum = pi.iter().copied().sum::<D>();
97        ranks = pi.iter().map(|r| *r / sum).collect::<Vec<D>>();
98    }
99    ranks
100}
101
102#[allow(dead_code)]
103fn out_edges_info<G, D>(graph: G, index_w: usize, index_v: usize) -> (D, bool)
104where
105    G: NodeCount + IntoEdges + NodeIndexable + core::marker::Sync,
106    D: UnitMeasure + Copy + core::marker::Send + core::marker::Sync,
107{
108    let node_w = graph.from_index(index_w);
109    let node_v = graph.from_index(index_v);
110    let mut out_edges = graph.edges(node_w);
111    let mut out_edge = out_edges.next();
112    let mut out_degree = D::zero();
113    let mut flag_points_to = false;
114    while let Some(edge) = out_edge {
115        out_degree = out_degree + D::one();
116        if edge.target() == node_v {
117            flag_points_to = true;
118        }
119        out_edge = out_edges.next();
120    }
121    (out_degree, flag_points_to)
122}
123/// \[Generic\] Parallel Page Rank algorithm.
124///
125/// See [`page_rank`].
126#[cfg(feature = "rayon")]
127pub fn parallel_page_rank<G, D>(
128    graph: G,
129    damping_factor: D,
130    nb_iter: usize,
131    tol: Option<D>,
132) -> Vec<D>
133where
134    G: NodeCount + IntoEdges + NodeIndexable + core::marker::Sync,
135    D: UnitMeasure + Copy + core::marker::Send + core::marker::Sync,
136{
137    let node_count = graph.node_count();
138    if node_count == 0 {
139        return vec![];
140    }
141    assert!(
142        D::zero() <= damping_factor && damping_factor <= D::one(),
143        "Damping factor should be between 0 et 1."
144    );
145    let mut tolerance = D::default_tol();
146    if let Some(_tol) = tol {
147        tolerance = _tol;
148    }
149    let nb = D::from_usize(node_count);
150    let mut ranks: Vec<D> = (0..node_count)
151        .into_par_iter()
152        .map(|_| D::one() / nb)
153        .collect();
154    for _ in 0..nb_iter {
155        let pi = (0..node_count)
156            .into_par_iter()
157            .map(|v| {
158                ranks
159                    .iter()
160                    .enumerate()
161                    .map(|(w, r)| {
162                        let (out_deg, w_points_to_v) = out_edges_info(graph, w, v);
163                        if w_points_to_v {
164                            damping_factor * *r / out_deg
165                        } else if out_deg == D::zero() {
166                            damping_factor * *r / nb // stochastic matrix condition
167                        } else {
168                            (D::one() - damping_factor) * *r / nb // random jumps
169                        }
170                    })
171                    .sum::<D>()
172            })
173            .collect::<Vec<D>>();
174        let sum = pi.par_iter().map(|score| *score).sum::<D>();
175        let new_ranks = pi.par_iter().map(|r| *r / sum).collect::<Vec<D>>();
176        let squared_norm_2 = new_ranks
177            .par_iter()
178            .zip(&ranks)
179            .map(|(new, old)| (*new - *old) * (*new - *old))
180            .sum::<D>();
181        if squared_norm_2 <= tolerance {
182            return ranks;
183        } else {
184            ranks = new_ranks;
185        }
186    }
187    ranks
188}
petgraph/algo/page_rank.rs

petgraph/algo/
page_rank.rs
