Mryntu

Betweenness centrality is defined as the number of shortest paths that go through a node in the graph.The formula is:

$$sum_s neq v neq t fracsigma_st(v)sigma_st$$

Where $sigma_st$ is the total number of shortest paths from node $s$ to node $t$ and $sigma _st(v)$ is the number of those paths that pass through $v$.

However it doesn't seem to me that the formula calculates what is defined. Why do we divide by the total number of shortest paths between $s$ and $t$ each time? Shouldn't we just divide by $2$ to compensate the fact that $s$ and $t$ will appear twice in different orders?

However it doesn't seem to me that the formula calculates what is defined.

The formula is right. The betweenness centrality is a value in an interval $[0, ldots, 1]$. Thus, if the betweenness centrality of node $v$ is equal to $1$, then all shortest paths between two nodes of this graph pass through $v$. I will explain the correctness of this summation below.

Why do we divide by the total number of shortest paths between s and t each time?

You are developing a summation of the percentages. This is needed to ensure that this sum will never exceed $1$. Suppose that you have $m$ different $s$-$t$ pairs of vertices in your graph. Thus, $sigma_st = m$ and your summation goes through all $m$ $s$-$t$ pairs.

One can note that the term $sigma_st(v)$ on this equation is binary (the shortest $s$-$t$ path passes through $v$ or not). Thus, if all $s$-$t$ paths go through $v$, you will have $m cdot frac1m = 1$.

Shouldn't we just divide by 2 to compensate the fact that s and t will appear twice in different orders?

Indirectly, you're right. This formula measures the percentage of the shortest $s$-$t$ paths that pass through node $v$. In fact, a simple optimization of this algorithm for undirected graphs is to consider only $s$-$t$ paths where $s < t$. However, you can't divide it by $2$.

Curiosity: The only graph topology who has a node with betweenness centrality equal to $1$ is a star graph, like the examples shown in the figure below.

Suppose we want to quantify the extent to which $v$ is between $s$ and $t$. There could be a few ways.

One way to describe that extent is the probability of passing through $v$ if we want to reach from $s$ to $t$ by a randomly-selected shortest path. Assume each shortest is selected with equal probability, we will get $fracsigma_st(v)sigma_st$, where $sigma_st$ is the total number of shortest paths from node $s$ to node $t$ and $sigma _st(v)$ is the number of those paths that pass through $v$.

Assigning the same weight to each pair of starting vertex and destination vertex, we can see that $sum_s neq v neq t fracsigma_st(v)sigma_st$ measure the extent in which $v$ is the center of betweenness.

_{The graph is created by https://graphonline.ru/}

If you use $fracsigma_st(v)2$ to quantify the extent to which $v$ is between $s$ and $t$, there is no problem if you just care about $v$ considering $s$ and $t$ as fixed. However, take a look at the above graph.

• How much is $v_3$ between $v_0$ and $v_4$? There are 3 shortest paths from $v_0$ to $v_4$, 2 of which pass through $v_3$. We get $fracsigma_v_0v_4(V_3)2 = 2/2=1$.


• How much is $v_5$ between $v_0$ and $v_6$? There is only 1 shortest path from $v_0$ to $v_6$, which passes $v_5$. We get $fracsigma_v_0v_6(v_5)2 = 1/2=0.5$.

Since $1>0.5$, we would like to conclude that $v_3$ is more between $v_0$ and $v_4$ than $v_5$ is between $v_0$ and $v_6$. However, we can go to $v_4$ without passing $v_3$ while we must pass $v_5$ to reach $v_6$ by shortest path. So $v_3$ should be less between $v_0$ and $v_4$ than $v_5$ is between $v_0$ and $v_6$. This simple example show that dividing by 2 is not the right way to normalize the measurement.