Dtjytyk

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. Assuming each shortest path 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$. In particular, the extent of $v$ between $s$ and $t$ is 0 if none of the shortest paths from $s$ to $v$ goes through $v$ while it is 1 if all of them must go through $v$.

Assigning the same weight to each pair of starting node and destination node, 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 through $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 through $v_3$ while we must pass through $v_5$ to reach $v_6$ by a 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 shows that it does not make much sense to divide by 2 or, in fact, any constant if we want to normalize the measurement.

Exercises

Exercise 1. What are the centers of the graph above in terms of the betweenness centrality? (Note there could be multiple centers.)

Exercise 2. Suppose we define the betweenness centrality of $v$ as $sum_s neq v neq t fractau_st(v)tau_st$, where $tau_st$ is the total number of distinct edges in the union of all shortest paths from $s$ to $t$ and $tau_st(v)$ is the number of those edges that are also incident to $v$. Would you consider the above definition a better definition of betweenness centrality?

Exercise 3. Suppose we define the betweenness centrality of $v$ as $sum_s neq v neq t fracrho_st(v)rho_st$, where $rho_st$ is the total number of distinct edges in the union of all shortest paths from $s$ to $t$ and $rho_st(v)$ is the number of distinct edges that are on a shortest path from $s$ to $t$ that passes through $v$. Would you consider the above definition a better definition of betweenness centrality?