Note
This is the documentation for the current state of the development branch of rustworkx. The documentation or APIs here can change prior to being released.
Working with Betweenness Centrality#
The betweenness centrality of a graph is a measure of centrality based on shortest paths. For every pair of nodes in a connected graph, there is at least a single shortest path between the nodes such that the number of edges the path passes through is minimized. The betweenness centrality for a given graph node is the number of these shortest paths that pass through the node.
This is defined as:
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\)
This tutorial will take you through the process of calculating the betweenness centrality of a graph and visualizing it.
Generate a Graph#
To start we need to generate a graph:
import rustworkx as rx
from rustworkx.visualization import mpl_draw
graph = rx.generators.hexagonal_lattice_graph(4, 4)
mpl_draw(graph)
![../_images/betweenness_centrality_0_0.png](../_images/betweenness_centrality_0_0.png)
Calculate the Betweeness Centrality#
The betweenness_centrality()
function can be used to calculate
the betweenness centrality for each node in the graph.
import pprint
centrality = rx.betweenness_centrality(graph)
# Print the centrality value for the first 5 nodes in the graph
pprint.pprint({x: centrality[x] for x in range(5)})
{0: 0.007277212457600987,
1: 0.02047046385621779,
2: 0.07491079688119466,
3: 0.04242324126690451,
4: 0.09205321351482312}
The output of betweenness_centrality()
is a
CentralityMapping
which is a custom
mapping type that
maps the node index to the centrality value as a float. This is a mapping and
not a sequence because node indices (and edge indices too, which is not
relevant here) are not guaranteed to be a contiguous sequence if there are
removals.
Visualize the Betweenness Centrality#
Now that we’ve found the betweenness centrality for graph
lets visualize it.
We’ll color each node in the output visualization using its calculated
centrality:
import matplotlib.pyplot as plt
# Generate a color list
colors = []
for node in graph.node_indices():
colors.append(centrality[node])
# Generate a visualization with a colorbar
plt.rcParams['figure.figsize'] = [15, 10]
ax = plt.gca()
sm = plt.cm.ScalarMappable(norm=plt.Normalize(
vmin=min(centrality.values()),
vmax=max(centrality.values())
))
plt.colorbar(sm, ax=ax)
plt.title("Betweenness Centrality of a 4 x 4 Hexagonal Lattice Graph")
mpl_draw(graph, node_color=colors, ax=ax)
![../_images/betweenness_centrality_2_0.png](../_images/betweenness_centrality_2_0.png)
Alternatively, you can use graphviz_draw()
:
from rustworkx.visualization import graphviz_draw
import matplotlib
# For graphviz visualization we need to assign the data payload for each
# node to its centrality value so that we can color based on this
for node, btw in centrality.items():
graph[node] = btw
# Leverage matplotlib for color map
colormap = matplotlib.colormaps["magma"]
norm = matplotlib.colors.Normalize(
vmin=min(centrality.values()),
vmax=max(centrality.values())
)
def color_node(node):
rgba = matplotlib.colors.to_hex(colormap(norm(node)), keep_alpha=True)
return {
"color": f"\"{rgba}\"",
"fillcolor": f"\"{rgba}\"",
"style": "filled",
"shape": "circle",
"label": "%.2f" % node,
}
graphviz_draw(graph, node_attr_fn=color_node, method="neato")
![../_images/betweenness_centrality_3_0.png](../_images/betweenness_centrality_3_0.png)