Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

networkx.algorithms.centrality.edge_betweenness_centrality

edge_betweenness_centrality(G, k=None, normalized=True, weight=None, seed=None)[source]

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

cB(e)=s,tVσ(s,t|e)σ(s,t)

where V is the set of nodes, σ(s,t) is the number of shortest (s,t)-paths, and σ(s,t|e) is the number of those paths passing through edge e [2].

Parameters:
  • G (graph) – A NetworkX graph.
  • k (int, optional (default=None)) – If k is not None use k node samples to estimate betweenness. The value of k <= n where n is the number of nodes in the graph. Higher values give better approximation.
  • normalized (bool, optional) – If True the betweenness values are normalized by 2/(n(n1)) for graphs, and 1/(n(n1)) for directed graphs where n is the number of nodes in G.
  • weight (None or string, optional (default=None)) – If None, all edge weights are considered equal. Otherwise holds the name of the edge attribute used as weight.
Returns:

edges – Dictionary of edges with betweenness centrality as the value.

Return type:

dictionary

See also

betweenness_centrality(), edge_load()

Notes

The algorithm is from Ulrik Brandes [1].

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

[1]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
[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