Compute the shortest-path betweenness centrality for nodes.
Betweenness centrality of a node \(v\) is the sum of the fraction of all-pairs shortest paths that pass through \(v\):
where \(V\) is the set of nodes, \(\sigma(s, t)\) is the number of shortest \((s, t)\)-paths, and \(\sigma(s, t|v)\) is the number of those paths passing through some node \(v\) other than \(s, t\). If \(s = t\), \(\sigma(s, t) = 1\), and if \(v \in {s, t}\), \(\sigma(s, t|v) = 0\) [R169].
Parameters: | G : graph
k : int, optional (default=None)
normalized : bool, optional
weight : None or string, optional
endpoints : bool, optional
|
---|---|
Returns: | nodes : dictionary
|
See also
Notes
The algorithm is from Ulrik Brandes [R168]. See [R169] for details on algorithms for variations and related metrics.
For approximate betweenness calculations set k=#samples to use k nodes (“pivots”) to estimate the betweenness values. For an estimate of the number of pivots needed see [R170].
For weighted graphs the edge weights must be greater than zero. Zero edge weights can produce an infinite number of equal length paths between pairs of nodes.
References
[R168] | (1, 2) A Faster Algorithm for Betweenness Centrality. Ulrik Brandes, Journal of Mathematical Sociology 25(2):163-177, 2001. http://www.inf.uni-konstanz.de/algo/publications/b-fabc-01.pdf |
[R169] | (1, 2, 3) Ulrik Brandes: On Variants of Shortest-Path Betweenness Centrality and their Generic Computation. Social Networks 30(2):136-145, 2008. http://www.inf.uni-konstanz.de/algo/publications/b-vspbc-08.pdf |
[R170] | (1, 2) Ulrik Brandes and Christian Pich: Centrality Estimation in Large Networks. International Journal of Bifurcation and Chaos 17(7):2303-2318, 2007. http://www.inf.uni-konstanz.de/algo/publications/bp-celn-06.pdf |