Betweenness Centrality

Betweenness Centrality

• The higher a node’s centrality is the more “dependent” other nodes are on it
• Based on shortest paths between nodes and the number of paths that pass through two points and the total number of paths
• BC(i) = SUM_{s≠i≠ t∈V}μ_st(i) / μ_st where μ_st is the number of paths from s and t and μ_st(i) is the number of paths from s and t that pass through node i

Algorithm

Input: V, a vertex and G, a graph

1. For all pairs of vertices (v₁ and v₂) in graph G, compute every shortest path between them
2. Using v₁ and v₂, compute the fraction of paths between these vertices that pass through V
3. Sum over all pairs of vertices

More Information and other Algorithms:

1. Approximating Betweenness Centrality
2. Better Approximation of Betweenness Centrality

1. Collaboration and Integration of Community-Based Health and Human Services in a Nonprofit Managed Care System
2. The Peer Context of Adolescent Substance Use: Findings from Social Network Analysis
3. Peer Standing and Substance Use in Early-Adolescent Grade-Level Networks: A Short-Term Longitudinal Study