petgraph/algo/
page_rank.rs

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

petgraph/algo/
page_rank.rs
