pub fn page_rank<G, D>(graph: G, damping_factor: D, nb_iter: usize) -> Vec<D>
Expand description
[Generic] Page Rank algorithm.
Computes the ranks of every node in a graph using the Page Rank algorithm.
Returns a Vec
container mapping each node index to its rank.
§Panics
The damping factor should be a number of type f32
or f64
between 0 and 1 (0 and 1 included). Otherwise, it panics.
§Complexity
Time complexity is O(N|V|²|E|). Space complexity is O(|V| + |E|) where N is the number of iterations, |V| the number of vertices (i.e nodes) and |E| the number of edges.
§Example
use petgraph::Graph;
use petgraph::algo::page_rank;
let mut g: Graph<(), usize> = Graph::new();
assert_eq!(page_rank(&g, 0.5_f64, 1), vec![]); // empty graphs have no node ranks.
let a = g.add_node(());
let b = g.add_node(());
let c = g.add_node(());
let d = g.add_node(());
let e = g.add_node(());
g.extend_with_edges(&[(0, 1), (0, 3), (1, 2), (1, 3)]);
// With the following dot representation.
//digraph {
// 0 [ label = "()" ]
// 1 [ label = "()" ]
// 2 [ label = "()" ]
// 3 [ label = "()" ]
// 4 [ label = "()" ]
// 0 -> 1 [ label = "0.0" ]
// 0 -> 3 [ label = "0.0" ]
// 1 -> 2 [ label = "0.0" ]
// 1 -> 3 [ label = "0.0" ]
//}
let damping_factor = 0.7_f32;
let number_iterations = 10;
let output_ranks = page_rank(&g, damping_factor, number_iterations);
let expected_ranks = vec![0.14685437, 0.20267677, 0.22389607, 0.27971846, 0.14685437];
assert_eq!(expected_ranks, output_ranks);