# Calculating the betweenness centrality of this small graph?

I don't exactly get the calculation method for computing the betweenness centrality of nodes. Given the following graph represented as below: I want to calculate the betweenness centrality of each node. The formula I believe should be $$g(v) = \sum_{s\neq t \neq v} \frac{\sigma_{st}(v)}{\sigma_{st}}$$

where $\sigma$ means the shortest path from one node s to another node t, for a certain node v involved in the path.

Question: does the $s$ and $t$ nodes represent every possible pair of nodes? To give an example, suppose $s = 1$ and $t = 4$. Then my $\sigma_{14}(2) = 1$, and similarly $\sigma_{13}(2) = 1$, and $\sigma_{15}(2) = 0$. So summing it all up, I have $g(v) = 2 / 3$, since there are 3 paths? But with the above data, how can I quickly compute by hand the betweeness centrality of each node?

If for example I have node 5 isolated from the rest of the nodes, then is $\sigma_{st}$ still 3? Because then there will be no shortest path from 1 to 5.

Going by the above example, I say the betweenness centrality of nodes 1 to 5 is 0, 2/3, 3/3, 2/3, 0, will this be correct?

But if I look at it from another perspective, there could be theoretically 10 shortest paths (5 choose 2 = 10).

Using the above information, what if I want to compute further statistics like edge centrality? Is there an efficient way to do this?

## 1 Answer

For a vertex $v$, the pairs $(s, t)$ under consideration are such that (1) $s \neq v$, $t \neq v$ and (2) there is a shortest path from $s$ to $t$. Take your graph and vertex $2$ as an example, we have \begin{align} g(2) &= \frac{\sigma_{13}(2)}{\sigma_{13}}+\frac{\sigma_{14}(2)}{\sigma_{14}} + \frac{\sigma_{15}(2)}{\sigma_{15}}+\frac{\sigma_{34}(2)}{\sigma_{34}} + \frac{\sigma_{35}(2)}{\sigma_{35}} + \frac{\sigma_{45}(2)}{\sigma_{45}}\\ &= \frac{1}{1} + \frac{1}{1} + \frac{0}{1} + \frac{0}{1} + \frac{0}{1} +\frac{0}{1} \\ &= 2 \end{align} You can compute the betweenness of other vertices as above.

• I get that node 2 will be used as the shortest path only twice at most, but do I also have to include variables like $\sigma_{23}$ as the denominator? Because the total number of shortest paths possible is 10, so do I have to divide by this number for all my counts? As a quick check, in the calculation you have, it seems that the betweenness value will always be integer, but I've seem values that are floats strangely. – oldselflearner1959 Mar 26 '18 at 13:00
• @oldselflearner1959 No. You do not have to include variables like $\sigma_{23}$ since $s = v$ in this case. When computing the betweenness of a vertex $v$, for each eligible pair $(s, t)$, you add the term $\frac{\sigma_{st}(v)}{\sigma_{st}}$ to the betweenness of $v$. The total number of shortest paths in the graph is irrelevant here. Finally, the betweennesses are not necessarily integers. It happens to be an integer in the example. – PSPACEhard Mar 27 '18 at 2:32
• Thanks for clarifying. In this case, why do we not have to include values like $\sigma_{12}$, since this is also a valid shortest path? Using the method you shown, does this mean $g(3) = 3$ as well? – oldselflearner1959 Mar 27 '18 at 22:02
• @oldselflearner1959 $s$ and $t$ cannot be equal to $v$. Yes, $g(3) = 3$. – PSPACEhard Mar 28 '18 at 11:35