Network graphs are interesting data structures. You can compute all kinds of metrics on a graph, including several measures of centrality. Centrality metrics indicate how important a node is in some way. Different centrality measures give you different information.

Betweenness centrality is a measure of how “between” other nodes a particular node is. If a node has a high betweenness centrality value, more information passes through the node.

Betweenness centrality (BC) is a bit tricky to compute. To compute BC for node 1 in the graph below you examine all pairs of nodes that don’t start or end with 1. For each pair, you find the total number of shortest paths, and the number of those shortest paths that contain 1 on those paths. You sum the proportions.

So for node 1, BC(1) = 2.5

(2,3): 1 / 1 = 1.0
(2,4): 0 / 1 = 0.0
(2,5): 1 / 2 = 0.5
(2,6): 0 / 1 = 0.0
(3,4): 1 / 1 = 1.0
(3,5): 0 / 1 = 0.0
(3,6): 0 / 1 = 0.0
(4,5): 0 / 1 = 0.0
(4,6): 0 / 1 = 0.0
(5,6): 0 / 1 = 0.0
               ===
               2.5

There is only one shortest path from (2,3) and it is 2-1-3. This path contains 1. There are two shortest paths from (2,5) and they are 2-1-3-5 and 2-4-6-5. Of these, one path contains 1. And so on.

The BCs for the other nodes would be computed in the same way.

I enjoy working with graphs, but for some reason, I don’t love working with graphs.

“The Judgement of Paris”, Georges Barbier. Circa 1925.