How Does Betweenness Centrality Work?

Betweenness Undirected Network

Freeman introduced in 1977 a formal definition for the network measurement betweenness centrality in an undirected network [1]. Previous authors have only described this centrality intuitively.

This centrality measures the bridgeness of a node. Each node is given a score based on the number of shortest paths that pass through the node. Nodes that are more often on these shortest paths will have a higher centrality.

For most centrality measurements, important means popular. Betweenness centrality captures a very different kind of importance: individuals controlling the flow around a network. They are also the ones whose removal from the network will disrupt interactions the most.

How to Calculate?

To determine the betweenness centrality, we must first list the unique pairs of nodes of a network. Betweenness centrality uses the geodesic distance or shortest paths between all pairs of nodes in a network to calculate the bridgeness. The shortest path between two nodes goes through the fewest links. Now we can compute the betweenness centrality.

1. Calculate unique pairs of nodes in a network: n(n-1)/2 pairs*
2. Determine the shortest paths (geodesic distance) between these
3. Calculate the fraction of the shortest paths that pass through a node
4. Normalise by dividing by (n-1)(n-2)/2

*) n = number of nodes in a network

The video shows more details, betweenness centrality examples, and an exercise to practice this.

Betweenness Normalisation

If we want to compare networks of different sizes, we have to normalise the betweenness centrality score. In an undirected network, we do this by dividing the betweenness score by the number of pairs of nodes not included.

Assumption Betweenness

An important thing to keep in mind is that betweenness centrality is based on the shortest path and ignores other paths between nodes. In real life, this is more complicated, and the chosen path is not always the shortest.

Betweenness Directed Network

In practice, most use cases are directed networks; fortunately, we can also measure the betweenness centrality for these networks [3]. Since these networks are not symmetrical, there are a few minor differences with an undirected network.

1. Calculate all pairs of nodes in a network: n(n-1) pairs
2. Determine the shortest paths (geodesic distance) of these
3. Calculate the fraction of the shortest paths that pass through a node
4. Normalise by dividing by (n-1)(n-2)

Betweenness Weighted Network

You can compute betweenness centrality with weighted networks as well. Now, not all distances between nodes are the same. Instead of the shortest path, we now take the minimally weighted path.

1. Calculate pairs of nodes in a network
2. Determine the minimal weighted paths (geodesic distance) of these
3. Calculate the fraction of minimally weighted paths that pass through a node
4. Normalise

Pros Betweenness Centrality

• Entire network: A major advantage of betweenness is that the position of a node is related to the whole network.
• Flow perspective: This is a different kind of importance compared to other centralities.

Cons Betweenness Centrality

• Assumption shortest path: In real life, a flow doesn't always take the shortest path.
• Calculation time: Calculating the betweenness centrality can take a lot of time in a huge network. Several solutions have been proposed to reduce the computation time, mainly by approximating the distance.
• Use with care: a bridge can also be on the periphery of the network and this centrality is also sensitive to changes in the network.

Related Centrality Measures

Betweenness centrality is just one of many measures of centrality. There are also variations on the betweenness centrality. Some relax the assumption of the shortest path by considering all possible paths. Alternatives are, for instance, delta centrality, information centrality, random walk centrality, local clustering coefficient, stress centrality, and percolation centrality.

Conclusion

Betweenness centrality measures another interesting property of nodes in a network. This may be why it is a popular centrality.