NetworkX

Previous topic

betweenness_centrality

Next topic

current_flow_closeness_centrality

edge_betweenness_centrality

edge_betweenness_centrality(G, normalized=True, weight=None)

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 [R131].

Parameters :

G : graph

A NetworkX graph

normalized : bool, optional

If True the betweenness values are normalized by 2/(n(n-1)) for graphs, and 1/(n(n-1)) for directed graphs where n is the number of nodes in G.

weight : None or string, optional

If None, all edge weights are considered equal. Otherwise holds the name of the edge attribute used as weight.

Returns :

edges : dictionary

Dictionary of edges with betweenness centrality as the value.

Notes

The algorithm is from Ulrik Brandes [R130].

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

[R130](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
[R131](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