oxicuda_graphalg/centrality/
eigenvector.rs

1//! Eigenvector centrality via power iteration on the adjacency matrix.
2
3use crate::error::{GraphalgError, GraphalgResult};
4use crate::repr::adjacency_list::AdjacencyList;
5
6pub fn eigenvector_centrality(
7    g: &AdjacencyList,
8    max_iter: usize,
9    tol: f64,
10) -> GraphalgResult<Vec<f64>> {
11    let n = g.n;
12    if n == 0 {
13        return Ok(Vec::new());
14    }
15    let mut x = vec![1.0f64 / (n as f64).sqrt(); n];
16    let mut y = vec![0.0f64; n];
17    for _ in 0..max_iter {
18        for v in y.iter_mut() {
19            *v = 0.0;
20        }
21        for u in 0..n {
22            let xu = x[u];
23            for &v in g.neighbors(u)? {
24                y[v] += xu;
25            }
26        }
27        let norm = y.iter().map(|v| v * v).sum::<f64>().sqrt();
28        if norm < 1e-300 {
29            return Err(GraphalgError::NumericalInstability(
30                "zero eigenvector during power iteration".to_string(),
31            ));
32        }
33        let mut diff = 0.0f64;
34        for i in 0..n {
35            let nv = y[i] / norm;
36            diff += (nv - x[i]).abs();
37            x[i] = nv;
38        }
39        if diff < tol {
40            return Ok(x);
41        }
42    }
43    Ok(x)
44}
45
46#[cfg(test)]
47mod tests {
48    use super::*;
49
50    #[test]
51    fn eigen_star_center_largest() {
52        // Center of a star has largest eigenvector centrality.
53        let mut g = AdjacencyList::new(4);
54        for v in 1..4 {
55            g.add_undirected_edge(0, v).expect("ok");
56        }
57        let c = eigenvector_centrality(&g, 200, 1e-10).expect("ok");
58        assert!(c[0] > c[1]);
59        assert!(c[0] > c[2]);
60    }
61}
oxicuda_graphalg/centrality/eigenvector.rs

oxicuda_graphalg/centrality/
eigenvector.rs
