rustworkx.betweenness_centrality

betweenness_centrality(graph, normalized=True, endpoints=False, parallel_threshold=50)

Returns the betweenness centrality of each node in the graph.

Betweenness centrality of a node $v$ is the sum of the fraction of all-pairs shortest paths that pass through :math`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 :math`(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$

The algorithm used in this function is based on:

Ulrik Brandes, A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Sociology 25(2):163-177, 2001.

This function is multithreaded and will run in parallel if the number of nodes in the graph is above the value of parallel_threshold (it defaults to 50). If the function will be running in parallel the env var RAYON_NUM_THREADS can be used to adjust how many threads will be used.

See Also

edge_betweenness_centrality

param PyDiGraph graph:

The input graph

param bool normalized:

Whether to normalize the betweenness scores by the number of distinct paths between all pairs of nodes.

param bool endpoints:

Whether to include the endpoints of paths in path lengths used to compute the betweenness.

param int parallel_threshold:

The number of nodes to calculate the the betweenness centrality in parallel at if the number of nodes in the graph is less than this value it will run in a single thread. The default value is 50

returns:

A dictionary mapping each node index to its betweenness centrality.

rtype:

dict