Why the normalization constant of betweenness centrality is $(N-1)(N-2)/2$? As stated by Wikipedia, the betweenness centrality of a node $v$ is given by the expression:
$$g(v)=\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.
The calculation may be rescaled by $(N-1)(N-2)/2$ for undirected graphs, where $N$ is the number of nodes. I can't explain why this quantity.
 A: The fraction $\frac{\sigma_{st}(v)}{\sigma_{st}}$ is certainly between $0$ and $1$; in some cases, all paths between $s$ and $t$ pass through $v$, and then it is equal to $1$.
In an $N$-vertex graph, there are $\binom{N-1}{2} = \frac{(N-1)(N-2)}{2}$ ways to choose a pair $\{s,t\}$ where $s$, $t$, and $v$ are all distinct. Therefore, when we define $g(v)$ to be the sum of $\frac{\sigma_{st}(v)}{\sigma_{st}}$ over all such pairs $\{s,t\}$, the possible values of $g(v)$ range from $0$ to $\binom{N-1}{2}$. Both extremes are possible:

*

*When $v$ has degree $1$, there are no paths that pass through $v$ but do not start or end there: $\sigma_{st}(v) = 0$ for all pairs $\{s,t\}$ in the sum. Therefore $g(v) = 0$ as well.

*Suppose the graph only has $N-1$ edges: the edges from $v$ to every other vertex. Then $\sigma_{st}(v) = \sigma_{st} = 1$ for every pair $\{s,t\}$ in the sum, and we get $g(v) = \binom{N-1}{2}$.

We divide by $\binom{N-1}{2}$ to obtain a measure of betweenness centrality that ranges between $0$ and $1$.
One reason we might want to do this is if we want to compare how central two vertices are in different graphs. If we did not normalize, then we'd generally expect all (or almost all) vertices in a large graph to be "more central" than the vertices in a small graph, which is a bit silly.

Wikipedia does not mention this, but the sum defining $g(v)$ should also be different for directed graphs - not just the normalization constant. In undirected graphs, $\sigma_{st} = \sigma_{ts}$, $\sigma_{st}(v) = \sigma_{ts}(v)$, and so we might as well sum over unordered pairs $\{s,t\}$. In directed graphs, these path counts are not necesssarily symmetric, so we should some over ordered pairs $(s,t)$ - though we still require that $s \ne t$. This doubles the number of terms in the sum, so then we divide by $(N-1)(N-2)$ to normalize.
We could also sum over ordered pairs $(s,t)$ for both kinds of graphs, and divide by $(N-1)(N-2)$ to normalize for both. This causes no harm for undirected graphs, we'd just have $\binom{N-1}{2}$ pairs of identical terms in the sum.
