Function run

nodedb/src/engine/graph/algo/betweenness.rs:25–83

Run Betweenness Centrality on the CSR index. `params.sample_size`: if set, only sample that many source nodes (approximate). If `None`, compute exact centrality (all sources). Returns `(node_id, centrality)` sorted by centrality descending.

(csr: &CsrIndex, params: &AlgoParams)

///
/// Returns `(node_id, centrality)` sorted by centrality descending.
pub fn run(csr: &CsrIndex, params: &AlgoParams) -> AlgoResultBatch {
    let n = csr.node_count();
    if n == 0 {
        return AlgoResultBatch::new(GraphAlgorithm::Betweenness);
    }

    let mut cb = vec![0.0f64; n];

    // Determine source nodes: all or sampled subset.
    let sources: Vec<usize> = match params.sample_size {
        Some(sample) if sample < n => {
            // Deterministic sampling via LCG.
            let mut state: u64 = (n as u64).wrapping_mul(0x517cc1b727220a95).wrapping_add(1);
            let mut selected = Vec::with_capacity(sample);
            let mut used = vec![false; n];
            while selected.len() < sample {
                state = state
                    .wrapping_mul(6_364_136_223_846_793_005)
                    .wrapping_add(1);
                let idx = (state >> 33) as usize % n;
                if !used[idx] {
                    used[idx] = true;
                    selected.push(idx);
                }
            }
            selected
        }
        _ => (0..n).collect(),
    };

    let scale = if params.sample_size.is_some() && sources.len() < n {
        // Scale approximate centrality to estimate full centrality.
        n as f64 / sources.len() as f64
    } else {
        1.0
    };

    // Brandes' algorithm: BFS from each source, then reverse accumulation.
    for &s in &sources {
        brandes_from_source(csr, s, n, &mut cb);
    }

    // Scale and normalize.
    if scale != 1.0 {
        for c in cb.iter_mut() {
            *c *= scale;
        }
    }

    // Build result sorted by centrality descending.
    let mut scored: Vec<(usize, f64)> = cb.into_iter().enumerate().collect();
    scored.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap_or(std::cmp::Ordering::Equal));

    let mut batch = AlgoResultBatch::new(GraphAlgorithm::Betweenness);
    for (node, centrality) in scored {
        batch.push_node_f64(csr.node_name_raw(node as u32).to_string(), centrality);
    }
    batch