uni_algo/algo/algorithms/
harmonic_centrality.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2024-2026 Dragonscale Team
3
4//! Harmonic Centrality Algorithm.
5//!
6//! A variant of Closeness Centrality that deals with infinite distances by summing
7//! the inverse of distances: H(u) = sum(1 / d(u, v)) for v != u.
8//! Uses BFS (unweighted) or Dijkstra (weighted) from every node.
9
10use crate::algo::GraphProjection;
11use crate::algo::algorithms::Algorithm;
12use rayon::prelude::*;
13use std::cmp::Reverse;
14use std::collections::BinaryHeap;
15use uni_common::core::id::Vid;
16
17pub struct HarmonicCentrality;
18
19#[derive(Debug, Clone, Default)]
20pub struct HarmonicCentralityConfig {}
21
22pub struct HarmonicCentralityResult {
23    pub scores: Vec<(Vid, f64)>,
24}
25
26impl Algorithm for HarmonicCentrality {
27    type Config = HarmonicCentralityConfig;
28    type Result = HarmonicCentralityResult;
29
30    fn name() -> &'static str {
31        "harmonic_centrality"
32    }
33
34    fn run(graph: &GraphProjection, _config: Self::Config) -> Self::Result {
35        let n = graph.vertex_count();
36        if n == 0 {
37            return HarmonicCentralityResult { scores: Vec::new() };
38        }
39
40        let scores: Vec<(Vid, f64)> = (0..n)
41            .into_par_iter()
42            .map(|i| {
43                let score = compute_harmonic_score(graph, i as u32);
44                (graph.to_vid(i as u32), score)
45            })
46            .collect();
47
48        HarmonicCentralityResult { scores }
49    }
50}
51
52fn compute_harmonic_score(graph: &GraphProjection, start: u32) -> f64 {
53    let n = graph.vertex_count();
54    let mut dist = vec![f64::INFINITY; n];
55    let mut heap = BinaryHeap::new();
56
57    dist[start as usize] = 0.0;
58    heap.push(Reverse((0.0f64.to_bits(), start)));
59
60    let mut sum_inv_dist = 0.0;
61
62    while let Some(Reverse((d_bits, u))) = heap.pop() {
63        let d = f64::from_bits(d_bits);
64        if d > dist[u as usize] {
65            continue;
66        }
67
68        if u != start && d > 0.0 {
69            sum_inv_dist += 1.0 / d;
70        }
71
72        for (i, &v) in graph.out_neighbors(u).iter().enumerate() {
73            let weight = if graph.has_weights() {
74                graph.out_weight(u, i)
75            } else {
76                1.0
77            };
78            let new_dist = d + weight;
79            if new_dist < dist[v as usize] {
80                dist[v as usize] = new_dist;
81                heap.push(Reverse((new_dist.to_bits(), v)));
82            }
83        }
84    }
85
86    sum_inv_dist
87}
88
89#[cfg(test)]
90mod tests {
91    use super::*;
92    use crate::algo::test_utils::build_test_graph;
93
94    #[test]
95    fn test_harmonic_centrality_simple() {
96        // 0 -> 1 -> 2
97        // H(0) = 1/1 + 1/2 = 1.5
98        // H(1) = 1/1 = 1.0
99        // H(2) = 0
100        let vids = vec![Vid::from(0), Vid::from(1), Vid::from(2)];
101        let edges = vec![(Vid::from(0), Vid::from(1)), (Vid::from(1), Vid::from(2))];
102        let graph = build_test_graph(vids, edges);
103
104        let result = HarmonicCentrality::run(&graph, HarmonicCentralityConfig::default());
105        let map: std::collections::HashMap<_, _> = result.scores.into_iter().collect();
106
107        assert!((map[&Vid::from(0)] - 1.5).abs() < 1e-6);
108        assert!((map[&Vid::from(1)] - 1.0).abs() < 1e-6);
109        assert!((map[&Vid::from(2)] - 0.0).abs() < 1e-6);
110    }
111}
uni_algo/algo/algorithms/harmonic_centrality.rs

uni_algo/algo/algorithms/
harmonic_centrality.rs
