patternMinor
Correctness of the Betweenness centrality formula
Viewed 0 times
thecorrectnessbetweennesscentralityformula
Problem
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} \frac{\sigma_{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?
$$\sum_{s \neq v \neq t} \frac{\sigma_{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?
Solution
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 \frac{1}{m} = 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.
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 \frac{1}{m} = 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.
Context
StackExchange Computer Science Q#108582, answer score: 3
Revisions (0)
No revisions yet.