rust_igraph/algorithms/properties/
katz_centrality.rs

1//! Katz centrality — attenuated walk-count centrality.
2//!
3//! Katz centrality for node *i* is defined as:
4//!   `c_i = alpha * sum_j A_ji * c_j + beta`
5//!
6//! where `alpha` is an attenuation factor (must be less than `1/lambda_max`
7//! for convergence) and `beta` is a baseline score for each node.
8//!
9//! Reference: Katz, L. "A New Status Index Derived from Sociometric Analysis",
10//! Psychometrika 18(1), 39–43, 1953.
11
12use crate::core::error::{IgraphError, IgraphResult};
13use crate::core::graph::Graph;
14
15/// Compute Katz centrality for all vertices using power iteration.
16///
17/// `alpha` is the attenuation factor — must satisfy `0 < alpha < 1/lambda_max`
18/// where `lambda_max` is the largest eigenvalue of the adjacency matrix.
19/// A safe default for most graphs is `0.1`.
20///
21/// `beta` is the baseline centrality for each node (typically `1.0`).
22///
23/// `max_iter` caps the number of iterations (default: 1000 if `None`).
24///
25/// `tol` is the convergence tolerance on the L2-norm change (default: 1e-6
26/// if `None`).
27///
28/// For directed graphs, centrality counts walks *arriving* at each node
29/// (i.e. uses in-neighbors).
30///
31/// # Errors
32///
33/// Returns an error if `alpha <= 0`, `max_iter` is 0, or if the iteration
34/// does not converge within `max_iter` steps.
35///
36/// # Examples
37///
38/// ```
39/// use rust_igraph::{Graph, katz_centrality};
40///
41/// let g = Graph::from_edges(&[(0,1),(1,2),(2,3),(3,0)], false, None).unwrap();
42/// let c = katz_centrality(&g, 0.1, 1.0, None, None).unwrap();
43/// // Symmetric graph → all centralities equal
44/// let diff = c[0] - c[2];
45/// assert!(diff.abs() < 1e-6);
46/// ```
47pub fn katz_centrality(
48    graph: &Graph,
49    alpha: f64,
50    beta: f64,
51    max_iter: Option<u32>,
52    tol: Option<f64>,
53) -> IgraphResult<Vec<f64>> {
54    if alpha <= 0.0 || alpha.is_nan() {
55        return Err(IgraphError::InvalidArgument(
56            "alpha must be positive and finite".into(),
57        ));
58    }
59    let max_iter = max_iter.unwrap_or(1000);
60    if max_iter == 0 {
61        return Err(IgraphError::InvalidArgument(
62            "max_iter must be positive".into(),
63        ));
64    }
65    let tol = tol.unwrap_or(1e-6);
66    let n = graph.vcount() as usize;
67
68    if n == 0 {
69        return Ok(Vec::new());
70    }
71
72    // Precompute adjacency for efficiency: for each vertex, store its
73    // in-neighbors (for directed) or all neighbors (for undirected).
74    let mut in_adj: Vec<Vec<u32>> = vec![Vec::new(); n];
75    for (u, v) in graph.edges() {
76        // Edge u → v: v receives from u
77        in_adj[v as usize].push(u);
78        if !graph.is_directed() {
79            // Undirected: u also receives from v
80            in_adj[u as usize].push(v);
81        }
82    }
83
84    let mut c = vec![0.0_f64; n];
85    let mut c_new = vec![0.0_f64; n];
86
87    for _ in 0..max_iter {
88        for i in 0..n {
89            let mut sum = 0.0_f64;
90            for &u in &in_adj[i] {
91                sum += c[u as usize];
92            }
93            c_new[i] = alpha * sum + beta;
94        }
95
96        // Check convergence (L2 norm of difference)
97        let mut norm_sq = 0.0_f64;
98        for i in 0..n {
99            let diff = c_new[i] - c[i];
100            norm_sq += diff * diff;
101        }
102        std::mem::swap(&mut c, &mut c_new);
103
104        if norm_sq.sqrt() < tol {
105            return Ok(c);
106        }
107    }
108
109    Err(IgraphError::DidNotConverge {
110        iters: max_iter as usize,
111        residual: {
112            let mut norm_sq = 0.0_f64;
113            for i in 0..n {
114                let diff = c_new[i] - c[i];
115                norm_sq += diff * diff;
116            }
117            norm_sq.sqrt()
118        },
119    })
120}
121
122#[cfg(test)]
123mod tests {
124    use super::*;
125
126    #[test]
127    fn empty_graph() {
128        let g = Graph::with_vertices(0);
129        let c = katz_centrality(&g, 0.1, 1.0, None, None).unwrap();
130        assert!(c.is_empty());
131    }
132
133    #[test]
134    fn single_vertex() {
135        let g = Graph::with_vertices(1);
136        let c = katz_centrality(&g, 0.1, 1.0, None, None).unwrap();
137        assert!((c[0] - 1.0).abs() < 1e-10);
138    }
139
140    #[test]
141    fn symmetric_graph_equal_centrality() {
142        let g = Graph::from_edges(&[(0, 1), (1, 2), (2, 3), (3, 0)], false, None).unwrap();
143        let c = katz_centrality(&g, 0.1, 1.0, None, None).unwrap();
144        for i in 1..4 {
145            assert!((c[i] - c[0]).abs() < 1e-6);
146        }
147    }
148
149    #[test]
150    fn star_center_higher() {
151        let g = Graph::from_edges(&[(0, 1), (0, 2), (0, 3), (0, 4)], false, None).unwrap();
152        let c = katz_centrality(&g, 0.1, 1.0, None, None).unwrap();
153        // Center (vertex 0) should have higher centrality
154        assert!(c[0] > c[1]);
155    }
156
157    #[test]
158    fn directed_asymmetric() {
159        let g = Graph::from_edges(&[(0, 1), (0, 2), (1, 2)], true, None).unwrap();
160        let c = katz_centrality(&g, 0.1, 1.0, None, None).unwrap();
161        // Vertex 2 has most in-edges
162        assert!(c[2] > c[0]);
163    }
164
165    #[test]
166    fn invalid_alpha() {
167        let g = Graph::with_vertices(2);
168        assert!(katz_centrality(&g, 0.0, 1.0, None, None).is_err());
169        assert!(katz_centrality(&g, -0.1, 1.0, None, None).is_err());
170    }
171
172    #[test]
173    fn isolated_vertices_get_beta() {
174        let g = Graph::with_vertices(3);
175        let c = katz_centrality(&g, 0.1, 2.0, None, None).unwrap();
176        for &v in &c {
177            assert!((v - 2.0).abs() < 1e-10);
178        }
179    }
180}
rust_igraph/algorithms/properties/katz_centrality.rs

rust_igraph/algorithms/properties/
katz_centrality.rs
