uni-algo 2.2.0

Graph algorithms for Uni - PageRank, Louvain, shortest paths, and more
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

// SPDX-License-Identifier: Apache-2.0
// Copyright 2024-2026 Dragonscale Team

//! Harmonic Centrality Algorithm.
//!
//! A variant of Closeness Centrality that deals with infinite distances by summing
//! the inverse of distances: H(u) = sum(1 / d(u, v)) for v != u.
//! Uses BFS (unweighted) or Dijkstra (weighted) from every node.

use crate::algo::GraphProjection;
use crate::algo::algorithms::{Algorithm, dijkstra_distances};
use rayon::prelude::*;
use uni_common::core::id::Vid;

pub struct HarmonicCentrality;

#[derive(Debug, Clone, Default)]
pub struct HarmonicCentralityConfig {}

pub struct HarmonicCentralityResult {
    pub scores: Vec<(Vid, f64)>,
}

impl Algorithm for HarmonicCentrality {
    type Config = HarmonicCentralityConfig;
    type Result = HarmonicCentralityResult;

    fn name() -> &'static str {
        "harmonic_centrality"
    }

    fn run(graph: &GraphProjection, _config: Self::Config) -> Self::Result {
        let n = graph.vertex_count();
        if n == 0 {
            return HarmonicCentralityResult { scores: Vec::new() };
        }

        let scores: Vec<(Vid, f64)> = (0..n)
            .into_par_iter()
            .map(|i| {
                let score = compute_harmonic_score(graph, i as u32);
                (graph.to_vid(i as u32), score)
            })
            .collect();

        HarmonicCentralityResult { scores }
    }
}

fn compute_harmonic_score(graph: &GraphProjection, start: u32) -> f64 {
    let dist = dijkstra_distances(graph, start);

    // Harmonic centrality: sum of 1/d(start, v) over all reachable
    // v != start. Unreachable nodes (INFINITY) and the source itself
    // (distance 0) contribute nothing.
    dist.into_iter()
        .filter(|d| d.is_finite() && *d > 0.0)
        .map(|d| 1.0 / d)
        .sum()
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::algo::test_utils::build_test_graph;

    #[test]
    fn test_harmonic_centrality_simple() {
        // 0 -> 1 -> 2
        // H(0) = 1/1 + 1/2 = 1.5
        // H(1) = 1/1 = 1.0
        // H(2) = 0
        let vids = vec![Vid::from(0), Vid::from(1), Vid::from(2)];
        let edges = vec![(Vid::from(0), Vid::from(1)), (Vid::from(1), Vid::from(2))];
        let graph = build_test_graph(vids, edges);

        let result = HarmonicCentrality::run(&graph, HarmonicCentralityConfig::default());
        let map: std::collections::HashMap<_, _> = result.scores.into_iter().collect();

        assert!((map[&Vid::from(0)] - 1.5).abs() < 1e-6);
        assert!((map[&Vid::from(1)] - 1.0).abs() < 1e-6);
        assert!((map[&Vid::from(2)] - 0.0).abs() < 1e-6);
    }
}