Warning

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

# networkx.algorithms.centrality.betweenness_centrality¶

betweenness_centrality(G, k=None, normalized=True, weight=None, endpoints=False, seed=None)[source]

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$$

$c_B(v) =\sum_{s,t \in V} \frac{\sigma(s, t|v)}{\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|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$$ [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-1)(n-2)) for graphs, and 1/((n-1)(n-2)) 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. endpoints (bool, optional) – If True include the endpoints in the shortest path counts. seed (integer, random_state, or None (default)) – Indicator of random number generation state. See Randomness. Note that this is only used if k is not None. nodes – Dictionary of nodes with betweenness centrality as the value. dictionary

Notes

The algorithm is from Ulrik Brandes [1]. See [4] for the original first published version and [2] 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 [3].

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] Ulrik Brandes: A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Sociology 25(2):163-177, 2001. http://www.inf.uni-konstanz.de/algo/publications/b-fabc-01.pdf
 [2] (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
 [3] 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
 [4] Linton C. Freeman: A set of measures of centrality based on betweenness. Sociometry 40: 35–41, 1977 http://moreno.ss.uci.edu/23.pdf