Ulrik Brandes' algorithm for betweenness centrality.
This module provides the core building blocks for computing node and edge betweenness centrality. The algorithm consists of two phases:
- Discovery: A Dijkstra-like breadth-first search to find shortest paths.
- Accumulation: A back-propagation phase to calculate dependencies.
Reference
Brandes, U. (2001). A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25(2), 163-177.
Summary
Functions
Accumulates edge dependencies for betweenness calculation.
Accumulates node dependencies for betweenness calculation.
Runs the discovery phase of Brandes' algorithm.
Types
@type discovery_result() :: {[Yog.node_id()], %{required(Yog.node_id()) => [Yog.node_id()]}, %{required(Yog.node_id()) => number()}}
Functions
@spec accumulate_edge_dependencies( [Yog.node_id()], %{required(Yog.node_id()) => [Yog.node_id()]}, %{ required(Yog.node_id()) => number() } ) :: %{required({Yog.node_id(), Yog.node_id()}) => float()}
Accumulates edge dependencies for betweenness calculation.
Returns a map of {u, v} pairs (where u < v) to their dependency scores.
@spec accumulate_node_dependencies( [Yog.node_id()], %{required(Yog.node_id()) => [Yog.node_id()]}, %{ required(Yog.node_id()) => number() } ) :: %{required(Yog.node_id()) => float()}
Accumulates node dependencies for betweenness calculation.
Returns a map of node IDs to their dependency scores.
@spec discovery( Yog.graph(), Yog.node_id(), weight, (weight, weight -> weight), (weight, weight -> :lt | :eq | :gt) ) :: discovery_result() when weight: var
Runs the discovery phase of Brandes' algorithm.
Returns a tuple {stack, predecessors, sigmas}:
stack: Nodes in non-decreasing order of distance.predecessors: A map from node to a list of its predecessors on all shortest paths.sigmas: A map from node to the number of shortest paths from source to it.