betweenness_centrality¶

betweenness_centrality
(G, k=None, normalized=True, weight=None, endpoints=False, seed=None)[source]¶ Compute the shortestpath betweenness centrality for nodes.
Betweenness centrality of a node is the sum of the fraction of allpairs shortest paths that pass through :
where is the set of nodes, is the number of shortest paths, and is the number of those paths passing through some node other than . If , , and if , [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 for graphs, and for directed graphs where 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.
 endpoints (bool, optional) – If True include the endpoints in the shortest path counts.
Returns: nodes – Dictionary of nodes with betweenness centrality as the value.
Return type: 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):163177, 2001. http://www.inf.unikonstanz.de/algo/publications/bfabc01.pdf [2] (1, 2) Ulrik Brandes: On Variants of ShortestPath Betweenness Centrality and their Generic Computation. Social Networks 30(2):136145, 2008. http://www.inf.unikonstanz.de/algo/publications/bvspbc08.pdf [3] Ulrik Brandes and Christian Pich: Centrality Estimation in Large Networks. International Journal of Bifurcation and Chaos 17(7):23032318, 2007. http://www.inf.unikonstanz.de/algo/publications/bpceln06.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