The Betweenness Centrality

Let’s study a centrality measure that usually has an interpretation of how much information flows through a node inside the network. In other words, the number of parts of a network are connected by this node.

The betweenness centrality

One thing that can happen when we’re dealing with shortest paths, and in fact, happens a lot in bigger graphs, is to have several paths that have a minimum distance. In this case, the closeness centrality doesn’t change because it uses only the distance value, not the paths themselves.

The betweenness centrality, on the other hand, takes the number of paths into account. Let’s start building it block by block.

Let’s define a function that returns the number of shortest paths there are between two nodes:

Now, let’s define another function. This function returns the number of shortest paths between two nodes that pass through a third defined node:

If this function returns a number greater than zero, then it means that there’s at least one shortest path from $s$ to $t$ that passes through the node ...