graphina 0.4.0-alpha.2

A graph data science library for Rust
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

//! Personalized PageRank centrality facade.
//!
//! Provides a NodeMap-based personalized PageRank interface consistent with other centrality
//! routines, wrapping the raw vector implementation. Use `personalized_pagerank_vec` if you need
//! the raw contiguous vector aligned to internal node ordering.

use super::personalized_pagerank::personalized_page_rank;
use crate::core::error::Result;
use crate::core::types::{BaseGraph, GraphConstructor, NodeId, NodeMap};
use petgraph::EdgeType;

/// Compute personalized PageRank returning a NodeMap<NodeId, f64> for consistency.
///
/// Errors on invalid parameters or empty graph.
pub fn personalized_pagerank<A, W, Ty>(
    graph: &BaseGraph<A, W, Ty>,
    personalization: Option<Vec<f64>>,
    damping: f64,
    tol: f64,
    max_iter: usize,
) -> Result<NodeMap<f64>>
where
    W: Copy + PartialOrd + Into<f64> + From<u8>,
    Ty: GraphConstructor<A, W> + EdgeType,
{
    // Build stable node list to map ranks
    let node_list: Vec<NodeId> = graph.nodes().map(|(nid, _)| nid).collect();
    let ranks_vec = personalized_page_rank(graph, personalization, damping, tol, max_iter)?;
    // Safety: personalized_page_rank returns rank vector sized to node_list.len()
    let mut map = NodeMap::default();
    for (i, nid) in node_list.iter().enumerate() {
        if let Some(val) = ranks_vec.get(i) {
            map.insert(*nid, *val);
        }
    }
    Ok(map)
}

#[cfg(test)]
mod tests {

    // Regression: personalized PageRank redistributed the rank mass of dangling
    // nodes uniformly instead of by the personalization vector. With no edges every
    // node is dangling, so all mass teleports by personalization and the result must
    // equal the (normalized) personalization vector exactly.
    #[test]
    fn test_personalized_pagerank_dangling_uses_personalization() {
        use crate::centrality::personalized::personalized_pagerank;
        use crate::core::types::Graph;

        let mut g = Graph::<i32, f64>::new();
        let nodes: Vec<_> = (0..3).map(|i| g.add_node(i)).collect();

        let p = vec![0.5, 0.3, 0.2];
        let pr = personalized_pagerank(&g, Some(p.clone()), 0.85, 1e-12, 2000)
            .expect("personalized pagerank should succeed");
        for (i, &want) in p.iter().enumerate() {
            assert!(
                (pr[&nodes[i]] - want).abs() < 1e-9,
                "node {i}: expected {want}, got {}",
                pr[&nodes[i]]
            );
        }
    }
    use super::*;
    use crate::core::types::Graph;

    #[test]
    fn test_personalized_pagerank_map_basic() {
        let mut g = Graph::<i32, f64>::new();
        let n1 = g.add_node(1);
        let n2 = g.add_node(2);
        g.add_edge(n1, n2, 1.0);
        let pr = personalized_pagerank(&g, None, 0.85, 1e-6, 50).unwrap();
        assert_eq!(pr.len(), 2);
        assert!(pr[&n1] > 0.0);
        assert!(pr[&n2] > 0.0);
    }

    #[test]
    fn test_personalized_pagerank_map_with_personalization() {
        let mut g = Graph::<i32, f64>::new();
        let n1 = g.add_node(1);
        let n2 = g.add_node(2);
        g.add_edge(n1, n2, 1.0);
        let pr = personalized_pagerank(&g, Some(vec![2.0, 1.0]), 0.85, 1e-6, 50).unwrap();
        // Node with higher personalization weight should have higher rank.
        assert!(pr[&n1] > pr[&n2]);
    }
}