rustworkx.graph_betweenness_centrality

graph_betweenness_centrality(graph, /, normalized=True, endpoints=False, parallel_threshold=50)

Compute the betweenness centrality of all nodes in a PyGraph.

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 \((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

graph_edge_betweenness_centrality

param PyGraph 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 pathlengths 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 read-only dict-like object whose keys are the node indices and values are the betweenness score for each node.

rtype:

CentralityMapping