Randomized shortest paths (RSP) betweenness centrality
Randomized shortest paths (RSP) betweenness centrality
is a variant of betweenness centrality that refines traditional measures based solely on either shortest paths or random walks [2]. The RSP model defines a Boltzmann probability distribution over all possible paths between node pairs, giving higher probability to short (near-optimal) paths while still assigning nonzero probability to longer alternatives. The balance between optimality and randomness is governed by an inverse temperature parameter \(β\).
Formally, the simple RSP betweenness of node \(i\), denoted by \(c_{\mathrm{RSP}}(i)\), is defined as
\begin{equation}
c_{\mathrm{RSP}}(i) = \sum_{s=1}^{N}\sum_{t=1}^{N} \bar{n}_i(s,t),
\end{equation}
where \(\bar{n}_i(s,t)\) represents the total flow transiting from node \(s\) to node \(t\) through node \(i\), computed as
\begin{equation*}
\bar{n}_i(s,t) = \sum_{(i,j) \in \mathcal{L}} \bar{η}_{ij}(s,t)
= \left( \frac{z_{si}}{z_{st}} - \frac{z_{ti}}{z_{tt}} \right) z_{it}.
\end{equation*}
Here, \(\bar{η}_{ij}(s,t)\) denotes the expected number of passages through edge \((i,j)\) over all \(s\)-\(t\) walks, and \(z_{st}\) is the \((s,t)\)-element of the fundamental matrix \(Z\) of non-absorbing paths, given by
\[
Z = (I - W)^{-1} = \left( I - D^{-1}A \odot e^{-β C} \right)^{-1},
\]
where \(A\) is the adjacency matrix, \(C\) is the cost matrix, and \(D\) is the diagonal matrix of row sums of \(A\). The elements of matrix \(C\) represents the traversal cost, or distance, between a pair of adjacent nodes.
For large values of \(β\), the path distribution concentrates on the shortest paths, while for small \(β\), longer and more random paths receive higher weight. In the limiting case \(β \rightarrow 0\), the RSP betweenness converges to the stationary distribution of a random walk on the network [2].