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
91
92
93
94

//! Closeness centrality algorithms.
//!
//! This module provides closeness centrality measures.
//!
//! Convention: returns `Result<_, crate::core::error::GraphinaError>` to propagate
//!

use crate::core::error::{GraphinaError, Result};
use crate::core::paths::dijkstra_path_f64;
use crate::core::types::{BaseGraph, GraphConstructor, GraphinaGraph, NodeMap};
use std::fmt::Debug;

/// Compute closeness centrality for all nodes.
pub fn closeness_centrality<A, Ty>(graph: &BaseGraph<A, f64, Ty>) -> Result<NodeMap<f64>>
where
    A: Debug,
    Ty: GraphConstructor<A, f64>,
    BaseGraph<A, f64, Ty>: GraphinaGraph<A, f64>,
{
    if graph.node_count() == 0 {
        return Err(GraphinaError::invalid_graph("Empty graph"));
    }

    let n = graph.node_count();
    let mut centralities = NodeMap::default();

    for (node, _) in graph.nodes() {
        let (dist_map, _) = dijkstra_path_f64(graph, node, None)?;
        // Sum of shortest path distances to reachable nodes, and how many are
        // reachable. Closeness is the reciprocal of the mean distance.
        let mut sum_dist = 0.0;
        let mut reachable = 0usize;
        // Iterate the distance map directly rather than doing one hash lookup per
        // other node. Summation is order-independent, so iteration order is fine.
        for (&other_node, dist_opt) in &dist_map {
            if node != other_node {
                if let Some(dist_f64) = dist_opt {
                    if *dist_f64 > 0.0 && dist_f64.is_finite() {
                        sum_dist += *dist_f64;
                        reachable += 1;
                    }
                }
            }
        }
        // Wasserman-Faust improved closeness: (reachable / sum_dist) scaled by
        // the fraction of the graph that is reachable, which is well defined on
        // disconnected graphs and reduces to (n - 1) / sum_dist when connected.
        let closeness = if sum_dist > 0.0 && n > 1 {
            (reachable as f64 / sum_dist) * (reachable as f64 / (n as f64 - 1.0))
        } else {
            0.0
        };
        centralities.insert(node, closeness);
    }

    Ok(centralities)
}

#[cfg(test)]
mod tests {
    // Regression: closeness centrality summed reciprocal distances (the harmonic
    // centrality formula) instead of computing closeness. On the unit-weight path
    // 0-1-2 the endpoint's closeness is (reachable / sum_dist) * (reachable / (n-1))
    // = (2/3) * (2/2) = 0.6667, not the harmonic value 1/1 + 1/2 = 1.5.
    #[test]
    fn test_closeness_centrality_is_not_harmonic() {
        use crate::centrality::closeness::closeness_centrality;
        use crate::core::types::Graph;

        let mut g = Graph::<i32, f64>::new();
        let n0 = g.add_node(0);
        let n1 = g.add_node(1);
        let n2 = g.add_node(2);
        g.add_edge(n0, n1, 1.0);
        g.add_edge(n1, n2, 1.0);

        let cc = closeness_centrality(&g).expect("closeness should succeed");
        assert!(
            (cc[&n0] - 2.0 / 3.0).abs() < 1e-9,
            "expected 0.6667, got {}",
            cc[&n0]
        );
        assert!(
            (cc[&n1] - 1.0).abs() < 1e-9,
            "expected 1.0, got {}",
            cc[&n1]
        );
        assert!(
            (cc[&n2] - 2.0 / 3.0).abs() < 1e-9,
            "expected 0.6667, got {}",
            cc[&n2]
        );
    }
}