Betweenness Centrality
Find bridges and critical connectors
Betweenness measures how often a node appears on shortest paths between other nodes - high betweenness = critical connector or bottleneck.
What It Computes
For each node, a score (0 to 1) representing the fraction of shortest paths passing through it.
When to Use It
- Critical infrastructure: Identify single points of failure
- Bottleneck detection: Find network choke points
- Bridge identification: Discover nodes connecting communities
Parameters
| Parameter | Type | Description |
|---|---|---|
k | int | Sample k nodes (optional, for approximation) |
normalized | bool | Normalize scores (default: true) |
Performance
Time: O(V × E) - Expensive!
Approximation: O(k × E) with k samples
Scales to: 1M edges (exact), 10M+ (approximate)
Example
Use Cases
Infrastructure Monitoring
Find services whose failure breaks the system:
Attack Surface
Cybersecurity: Which nodes provide access to most others?
Network Optimization
Remove bottlenecks for better flow
Performance Tips
- Use k-sampling for graphs >1M edges
- Progressive sampling: Start with k=50, increase if needed
- Cache results: Expensive to recompute
See Also
- PageRank - For influence vs bridging
- Degree Centrality - Simple connectivity