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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
//! Harmonic centrality (ALGO-PR-009).
//!
//! Counterpart of `igraph_harmonic_centrality()` from
//! `references/igraph/src/centrality/closeness.c:800-805` (and the
//! underlying `igraph_harmonic_centrality_cutoff`). Defined as the mean
//! inverse distance to all other vertices, with `1/inf == 0` for
//! unreachable pairs.
//!
//! Phase-1 minimal slice: undirected / `IGRAPH_OUT`, unweighted, normalized.
//! Returns `f64` per vertex (no `Option`); a vertex with no reachable
//! neighbours simply gets 0.0 (matching python-igraph's behaviour).
use crate::algorithms::paths::distances::distances;
use crate::core::{Graph, IgraphResult};
/// Per-vertex harmonic centrality.
///
/// `result[v] = (1/(n-1)) * sum_{u != v, reachable} 1/d(v, u)`. The
/// inverse distance to unreachable vertices is taken as 0, so harmonic
/// centrality is well-defined on disconnected graphs (unlike closeness).
///
/// For graphs with `vcount < 2` returns an empty / single-zero vector
/// (the normalization factor `n - 1` is 0 in that case; we report 0
/// rather than NaN to match python-igraph 0.11.x).
///
/// Counterpart of
/// `igraph_harmonic_centrality(_, _, vss_all(), IGRAPH_OUT, NULL, /*normalized=*/true)`.
///
/// # Examples
///
/// ```
/// use rust_igraph::{Graph, harmonic_centrality};
///
/// // Path 0-1-2: vertex 1 (centre) has harmonic 1.0; ends 0.75.
/// let mut g = Graph::with_vertices(3);
/// g.add_edge(0, 1).unwrap();
/// g.add_edge(1, 2).unwrap();
/// let h = harmonic_centrality(&g).unwrap();
/// assert_eq!(h, vec![0.75, 1.0, 0.75]);
/// ```
pub fn harmonic_centrality(graph: &Graph) -> IgraphResult<Vec<f64>> {
let n = graph.vcount();
let n_us = n as usize;
if n < 2 {
return Ok(vec![0.0; n_us]);
}
let mut out = Vec::with_capacity(n_us);
let denom = f64::from(n - 1);
for v in 0..n {
let d = distances(graph, v)?;
let mut sum_inv: f64 = 0.0;
let v_us = v as usize;
for (target, &val) in d.iter().enumerate() {
if target == v_us {
continue;
}
if let Some(dist) = val {
if dist > 0 {
sum_inv += 1.0 / f64::from(dist);
}
}
}
out.push(sum_inv / denom);
}
Ok(out)
}
#[cfg(test)]
mod tests {
use super::*;
fn close(a: f64, b: f64, tol: f64) {
assert!((a - b).abs() < tol, "{a} vs {b}");
}
#[test]
fn empty_graph_yields_empty() {
let g = Graph::with_vertices(0);
assert!(harmonic_centrality(&g).unwrap().is_empty());
}
#[test]
fn singleton_yields_zero() {
let g = Graph::with_vertices(1);
assert_eq!(harmonic_centrality(&g).unwrap(), vec![0.0]);
}
#[test]
fn isolated_vertices_all_zero() {
let g = Graph::with_vertices(3);
assert_eq!(harmonic_centrality(&g).unwrap(), vec![0.0, 0.0, 0.0]);
}
#[test]
fn path_3_centre_one_ends_three_quarters() {
// 0-1-2: centre has 1/1 + 1/1 = 2; / (3-1) = 1.0.
// End: 1/1 + 1/2 = 1.5; / 2 = 0.75.
let mut g = Graph::with_vertices(3);
g.add_edge(0, 1).unwrap();
g.add_edge(1, 2).unwrap();
let h = harmonic_centrality(&g).unwrap();
assert_eq!(h, vec![0.75, 1.0, 0.75]);
}
#[test]
fn k3_uniform_one() {
let mut g = Graph::with_vertices(3);
g.add_edge(0, 1).unwrap();
g.add_edge(1, 2).unwrap();
g.add_edge(2, 0).unwrap();
let h = harmonic_centrality(&g).unwrap();
for &x in &h {
close(x, 1.0, 1e-12);
}
}
#[test]
fn star_centre_one_leaves_two_thirds() {
// Centre: 3 leaves at distance 1 → sum = 3, /3 = 1.0.
// Leaf: centre at 1 + 2 leaves at 2 → 1 + 0.5 + 0.5 = 2; /3 = 2/3.
let mut g = Graph::with_vertices(4);
for v in 1..4 {
g.add_edge(0, v).unwrap();
}
let h = harmonic_centrality(&g).unwrap();
close(h[0], 1.0, 1e-12);
for &leaf in &h[1..4] {
close(leaf, 2.0 / 3.0, 1e-12);
}
}
#[test]
fn disconnected_components_well_defined() {
// {0-1-2} and {3} (isolated). Vertex 0: reach {1,2} sum=1+0.5 = 1.5; /3 = 0.5.
// Vertex 3: no reach → 0/3 = 0.
// Unlike closeness, harmonic is defined here.
let mut g = Graph::with_vertices(4);
g.add_edge(0, 1).unwrap();
g.add_edge(1, 2).unwrap();
let h = harmonic_centrality(&g).unwrap();
close(h[0], 0.5, 1e-12);
close(h[1], 2.0 / 3.0, 1e-12); // 1/1 + 1/1 = 2; /3.
close(h[2], 0.5, 1e-12);
close(h[3], 0.0, 1e-12);
}
#[test]
fn directed_path_uses_out_edges() {
// 0->1->2: from 0 reach {1, 2}, from 1 reach {2}, from 2 reach {} (= 0).
let mut g = Graph::new(3, true).unwrap();
g.add_edge(0, 1).unwrap();
g.add_edge(1, 2).unwrap();
let h = harmonic_centrality(&g).unwrap();
// 0: 1/1 + 1/2 = 1.5; / 2 = 0.75.
close(h[0], 0.75, 1e-12);
// 1: 1/1 = 1; / 2 = 0.5.
close(h[1], 0.5, 1e-12);
// 2: 0; / 2 = 0.
close(h[2], 0.0, 1e-12);
}
}