pub fn betweenness_centrality(
graph: &SqliteGraph,
) -> Result<Vec<(i64, f64)>, SqliteGraphError>Expand description
Computes betweenness centrality for all nodes in the graph.
Betweenness centrality measures how often a node appears on shortest paths between other nodes. Bridge nodes (connecting different parts of the graph) score higher. Useful for finding bottlenecks or control points in networks.
§Arguments
graph- The graph to analyze
§Returns
Vector of (node_id, centrality) tuples sorted by centrality descending. Values are normalized by default (divide by 2 for undirected graphs).
§Complexity
Time: O(|V| * |E|) for unweighted graphs (Brandes’ algorithm) Space: O(|V| + |E|) for BFS traversal and accumulation
§Algorithm Details
Implements Brandes’ algorithm for unweighted graphs:
- For each node s, run BFS to compute shortest paths
- Track predecessors and path counts during BFS
- Accumulate dependency values (how much s depends on each node)
- Sum dependencies across all source nodes
Handles disconnected components gracefully (pairs with no path are ignored).
§Caveats
- Expensive for large graphs (O(VE) time complexity)
- Does not support edge weights (unweighted only)
- For graphs > 10K nodes, consider sampling approximation
§References
- Brandes, U. (2001). “A Faster Algorithm for Betweenness Centrality.”
§Example
use sqlitegraph::{SqliteGraph, algo::betweenness_centrality};
let graph = SqliteGraph::open_in_memory()?;
// ... add nodes and edges ...
let centrality = betweenness_centrality(&graph)?;