2
$\begingroup$

I don't exactly get the calculation method for computing the betweenness centrality of nodes. Given the following graph represented as below:

enter image description here

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – oldselflearner1959 Mar 26 '18 at 13:00
  • $\begingroup$ @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. $\endgroup$ – PSPACEhard Mar 27 '18 at 2:32
  • $\begingroup$ 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? $\endgroup$ – oldselflearner1959 Mar 27 '18 at 22:02
  • 1
    $\begingroup$ @oldselflearner1959 $s$ and $t$ cannot be equal to $v$. Yes, $g(3) = 3$. $\endgroup$ – PSPACEhard Mar 28 '18 at 11:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.