Compute betweenness centrality for edges.
Betweenness centrality of an edge e is the sum of the fraction of all-pairs shortest paths that pass through e:
c_B(v) =\sum_{s,t \in V} \frac{\sigma(s, t|e)}{\sigma(s, t)}
where V is the set of nodes, \sigma(s, t) is the number of shortest (s, t)-paths, and \sigma(s, t|e) is the number of those paths passing through edge e [R59]..
Parameters : | G : graph
normalized : bool, optional
weighted_edges : bool, optional
|
---|---|
Returns : | edges : dictionary
|
See also
Notes
The algorithm is from Ulrik Brandes [R58].
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
[R58] | (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 |
[R59] | (1, 2) 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 |