Betweenness Centrality

Introduction

Betweenness centrality is a measure used in graph theory to identify the importance of a node within a network or graph. It is based on the number of shortest paths between all pairs of nodes that pass through the node of interest. In other words, it quantifies the extent to which a particular node acts as a bridge or intermediary between other nodes in the network. Nodes with high betweenness centrality are often considered critical points of control, communication, or influence within the network.

How to compute betweenness?

To compute betweenness centrality, we first need to find the shortest paths between all pairs of nodes using a shortest path algorithm like Dijkstra's algorithm that we study in the last lesson. Once we have the shortest paths, we can count the number of paths passing through each node and normalize the values by dividing by the total number of possible pairs of nodes.

Let's take a look at this example to illustrate the concept:

Suppose we have a small social network with six people: A, B, C, D, E, and F. The connections between them are as follows: