Skip to main content

betweenness_centrality

sqlitegraph::algo

Function betweenness_centrality 

Source 
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:

  1. For each node s, run BFS to compute shortest paths
  2. Track predecessors and path counts during BFS
  3. Accumulate dependency values (how much s depends on each node)
  4. 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)?;