rust_igraph/algorithms/properties/
harmonic.rs

1//! Harmonic centrality (ALGO-PR-009).
2//!
3//! Counterpart of `igraph_harmonic_centrality()` from
4//! `references/igraph/src/centrality/closeness.c:800-805` (and the
5//! underlying `igraph_harmonic_centrality_cutoff`). Defined as the mean
6//! inverse distance to all other vertices, with `1/inf == 0` for
7//! unreachable pairs.
8//!
9//! Phase-1 minimal slice: undirected / `IGRAPH_OUT`, unweighted, normalized.
10//! Returns `f64` per vertex (no `Option`); a vertex with no reachable
11//! neighbours simply gets 0.0 (matching python-igraph's behaviour).
12
13use crate::algorithms::paths::distances::distances;
14use crate::core::{Graph, IgraphResult};
15
16/// Per-vertex harmonic centrality.
17///
18/// `result[v] = (1/(n-1)) * sum_{u != v, reachable} 1/d(v, u)`. The
19/// inverse distance to unreachable vertices is taken as 0, so harmonic
20/// centrality is well-defined on disconnected graphs (unlike closeness).
21///
22/// For graphs with `vcount < 2` returns an empty / single-zero vector
23/// (the normalization factor `n - 1` is 0 in that case; we report 0
24/// rather than NaN to match python-igraph 0.11.x).
25///
26/// Counterpart of
27/// `igraph_harmonic_centrality(_, _, vss_all(), IGRAPH_OUT, NULL, /*normalized=*/true)`.
28///
29/// # Examples
30///
31/// ```
32/// use rust_igraph::{Graph, harmonic_centrality};
33///
34/// // Path 0-1-2: vertex 1 (centre) has harmonic 1.0; ends 0.75.
35/// let mut g = Graph::with_vertices(3);
36/// g.add_edge(0, 1).unwrap();
37/// g.add_edge(1, 2).unwrap();
38/// let h = harmonic_centrality(&g).unwrap();
39/// assert_eq!(h, vec![0.75, 1.0, 0.75]);
40/// ```
41pub fn harmonic_centrality(graph: &Graph) -> IgraphResult<Vec<f64>> {
42    let n = graph.vcount();
43    let n_us = n as usize;
44    if n < 2 {
45        return Ok(vec![0.0; n_us]);
46    }
47    let mut out = Vec::with_capacity(n_us);
48    let denom = f64::from(n - 1);
49    for v in 0..n {
50        let d = distances(graph, v)?;
51        let mut sum_inv: f64 = 0.0;
52        let v_us = v as usize;
53        for (target, &val) in d.iter().enumerate() {
54            if target == v_us {
55                continue;
56            }
57            if let Some(dist) = val {
58                if dist > 0 {
59                    sum_inv += 1.0 / f64::from(dist);
60                }
61            }
62        }
63        out.push(sum_inv / denom);
64    }
65    Ok(out)
66}
67
68#[cfg(test)]
69mod tests {
70    use super::*;
71
72    fn close(a: f64, b: f64, tol: f64) {
73        assert!((a - b).abs() < tol, "{a} vs {b}");
74    }
75
76    #[test]
77    fn empty_graph_yields_empty() {
78        let g = Graph::with_vertices(0);
79        assert!(harmonic_centrality(&g).unwrap().is_empty());
80    }
81
82    #[test]
83    fn singleton_yields_zero() {
84        let g = Graph::with_vertices(1);
85        assert_eq!(harmonic_centrality(&g).unwrap(), vec![0.0]);
86    }
87
88    #[test]
89    fn isolated_vertices_all_zero() {
90        let g = Graph::with_vertices(3);
91        assert_eq!(harmonic_centrality(&g).unwrap(), vec![0.0, 0.0, 0.0]);
92    }
93
94    #[test]
95    fn path_3_centre_one_ends_three_quarters() {
96        // 0-1-2: centre has 1/1 + 1/1 = 2; / (3-1) = 1.0.
97        // End: 1/1 + 1/2 = 1.5; / 2 = 0.75.
98        let mut g = Graph::with_vertices(3);
99        g.add_edge(0, 1).unwrap();
100        g.add_edge(1, 2).unwrap();
101        let h = harmonic_centrality(&g).unwrap();
102        assert_eq!(h, vec![0.75, 1.0, 0.75]);
103    }
104
105    #[test]
106    fn k3_uniform_one() {
107        let mut g = Graph::with_vertices(3);
108        g.add_edge(0, 1).unwrap();
109        g.add_edge(1, 2).unwrap();
110        g.add_edge(2, 0).unwrap();
111        let h = harmonic_centrality(&g).unwrap();
112        for &x in &h {
113            close(x, 1.0, 1e-12);
114        }
115    }
116
117    #[test]
118    fn star_centre_one_leaves_two_thirds() {
119        // Centre: 3 leaves at distance 1 → sum = 3, /3 = 1.0.
120        // Leaf: centre at 1 + 2 leaves at 2 → 1 + 0.5 + 0.5 = 2; /3 = 2/3.
121        let mut g = Graph::with_vertices(4);
122        for v in 1..4 {
123            g.add_edge(0, v).unwrap();
124        }
125        let h = harmonic_centrality(&g).unwrap();
126        close(h[0], 1.0, 1e-12);
127        for &leaf in &h[1..4] {
128            close(leaf, 2.0 / 3.0, 1e-12);
129        }
130    }
131
132    #[test]
133    fn disconnected_components_well_defined() {
134        // {0-1-2} and {3} (isolated). Vertex 0: reach {1,2} sum=1+0.5 = 1.5; /3 = 0.5.
135        // Vertex 3: no reach → 0/3 = 0.
136        // Unlike closeness, harmonic is defined here.
137        let mut g = Graph::with_vertices(4);
138        g.add_edge(0, 1).unwrap();
139        g.add_edge(1, 2).unwrap();
140        let h = harmonic_centrality(&g).unwrap();
141        close(h[0], 0.5, 1e-12);
142        close(h[1], 2.0 / 3.0, 1e-12); // 1/1 + 1/1 = 2; /3.
143        close(h[2], 0.5, 1e-12);
144        close(h[3], 0.0, 1e-12);
145    }
146
147    #[test]
148    fn directed_path_uses_out_edges() {
149        // 0->1->2: from 0 reach {1, 2}, from 1 reach {2}, from 2 reach {} (= 0).
150        let mut g = Graph::new(3, true).unwrap();
151        g.add_edge(0, 1).unwrap();
152        g.add_edge(1, 2).unwrap();
153        let h = harmonic_centrality(&g).unwrap();
154        // 0: 1/1 + 1/2 = 1.5; / 2 = 0.75.
155        close(h[0], 0.75, 1e-12);
156        // 1: 1/1 = 1; / 2 = 0.5.
157        close(h[1], 0.5, 1e-12);
158        // 2: 0; / 2 = 0.
159        close(h[2], 0.0, 1e-12);
160    }
161}
rust_igraph/algorithms/properties/harmonic.rs

rust_igraph/algorithms/properties/
harmonic.rs
