petgraph/algo/
page_rank.rs

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

petgraph/algo/
page_rank.rs
