uni_algo/algo/algorithms/
eigenvector_centrality.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2024-2026 Dragonscale Team
3
4//! Eigenvector Centrality Algorithm.
5//!
6//! Measures the influence of a node in a network.
7//! Uses power iteration method.
8
9use crate::algo::GraphProjection;
10use crate::algo::algorithms::Algorithm;
11use uni_common::core::id::Vid;
12
13pub struct EigenvectorCentrality;
14
15#[derive(Debug, Clone)]
16pub struct EigenvectorCentralityConfig {
17    pub max_iterations: usize,
18    pub tolerance: f64,
19}
20
21impl Default for EigenvectorCentralityConfig {
22    fn default() -> Self {
23        Self {
24            max_iterations: 100,
25            tolerance: 1e-6,
26        }
27    }
28}
29
30pub struct EigenvectorCentralityResult {
31    pub scores: Vec<(Vid, f64)>,
32    pub iterations: usize,
33}
34
35impl Algorithm for EigenvectorCentrality {
36    type Config = EigenvectorCentralityConfig;
37    type Result = EigenvectorCentralityResult;
38
39    fn name() -> &'static str {
40        "eigenvector_centrality"
41    }
42
43    fn run(graph: &GraphProjection, config: Self::Config) -> Self::Result {
44        let n = graph.vertex_count();
45        if n == 0 {
46            return EigenvectorCentralityResult {
47                scores: Vec::new(),
48                iterations: 0,
49            };
50        }
51
52        let mut x = vec![1.0 / (n as f64).sqrt(); n]; // Initial vector (normalized)
53        let mut next_x = vec![0.0; n];
54        let mut iterations = 0;
55
56        for iter in 0..config.max_iterations {
57            iterations = iter + 1;
58            next_x.fill(0.0);
59
60            // Matrix multiplication: next_x = A^T * x (using incoming edges)
61            // Or A * x if directed means "influence flows from u to v"?
62            // Eigenvector usually defined on adjacency A. x_v = 1/lambda * sum(A_uv * x_u)
63            // If u -> v (u influences v), then v's score depends on u's score.
64            // So we iterate incoming edges of v.
65            // Or iterate outgoing edges of u and add to v.
66
67            // Using push method (outgoing edges) is cache friendly for CSR.
68            for (u, &x_u) in x.iter().enumerate().take(n) {
69                if x_u == 0.0 {
70                    continue;
71                }
72                for (i, &v_u32) in graph.out_neighbors(u as u32).iter().enumerate() {
73                    let weight = if graph.has_weights() {
74                        graph.out_weight(u as u32, i)
75                    } else {
76                        1.0
77                    };
78                    next_x[v_u32 as usize] += x_u * weight;
79                }
80            }
81
82            // Normalize (L2 norm)
83            let mut norm_sq = 0.0;
84            for val in &next_x {
85                norm_sq += val * val;
86            }
87            let norm = norm_sq.sqrt();
88
89            if norm == 0.0 {
90                // Graph likely has no edges or sink trap
91                break;
92            }
93
94            for val in &mut next_x {
95                *val /= norm;
96            }
97
98            // Check convergence
99            let mut diff = 0.0;
100            for i in 0..n {
101                diff += (next_x[i] - x[i]).abs();
102            }
103
104            x.copy_from_slice(&next_x);
105
106            if diff < config.tolerance {
107                break;
108            }
109        }
110
111        let scores = x
112            .into_iter()
113            .enumerate()
114            .map(|(i, s)| (graph.to_vid(i as u32), s))
115            .collect();
116
117        EigenvectorCentralityResult { scores, iterations }
118    }
119}
120
121#[cfg(test)]
122mod tests {
123    use super::*;
124    use crate::algo::test_utils::build_test_graph;
125
126    #[test]
127    fn test_eigenvector_centrality_star() {
128        // Use a non-bipartite graph to avoid power iteration oscillation.
129        // Triangle 0-1-2 plus node 3 connected to 0.
130        // 0-1, 1-2, 2-0, 0-3
131        // 0 has degree 3 (neighbors 1,2,3). 1,2 degree 2. 3 degree 1.
132        let vids2 = vec![Vid::from(0), Vid::from(1), Vid::from(2), Vid::from(3)];
133        let edges2 = vec![
134            (Vid::from(0), Vid::from(1)),
135            (Vid::from(1), Vid::from(0)),
136            (Vid::from(1), Vid::from(2)),
137            (Vid::from(2), Vid::from(1)),
138            (Vid::from(2), Vid::from(0)),
139            (Vid::from(0), Vid::from(2)),
140            (Vid::from(0), Vid::from(3)),
141            (Vid::from(3), Vid::from(0)),
142        ];
143        let graph2 = build_test_graph(vids2, edges2);
144        let result2 = EigenvectorCentrality::run(&graph2, EigenvectorCentralityConfig::default());
145        let map2: std::collections::HashMap<_, _> = result2.scores.into_iter().collect();
146
147        // 0 should be highest
148        assert!(map2[&Vid::from(0)] > map2[&Vid::from(3)]);
149        assert!(map2[&Vid::from(0)] > map2[&Vid::from(1)]);
150    }
151}
uni_algo/algo/algorithms/eigenvector_centrality.rs

uni_algo/algo/algorithms/
eigenvector_centrality.rs
