40 Algorithms Every Programmer Should Know

Betweenness

Betweenness is the measure of centrality in a graph. In the context of social media, it will quantify the probability that a person is part of the communication in a subgroup. For a computer network, betweenness will quantify the negative effect on communication between the graph nodes, in the event of vertex failure.

To calculate the betweenness of vertex a in a certain aGraph = (𝓥, 𝓔), follow these steps:

1. Compute the shortest paths between each pair of vertices in aGraph. Let's represent this with .

2. From , count the number of shortest ...