Random walk centrality (RWC)
The
random walk centrality
(RWC) measures how quickly a node can be reached by information diffusing randomly through a network, accounting for all paths rather than only shortest paths [2].
Let \(A\) be the adjacency matrix of a network and \(D = \mathrm{diag}(d_1, \dots, d_N)\) the degree matrix. The transition probability matrix of a classical random walk is
\[
M = D^{-1} A,
\]
so that a walker at node \(i\) moves to a randomly chosen neighbor at each step.
Let \(P_{ij}(t)\) denote the probability that a walker starting at \(i\) is at node \(j\) after \(t\) steps, and let \(P_i^\infty = d_i / \sum_j d_j\) be the stationary probability. The random-walk centrality of node \(i\) is defined as
\[
c_{\rm RWC}(i) = \frac{P_i^\infty}{\sum_{t=0}^{\infty} \bigl(P_{ii}(t) - P_i^\infty\bigr)} = \frac{P_i^\infty}{τ_i},
\]
where \(τ_i\) is the
characteristic relaxation time
of node \(i\), i.e., the expected time for a random walker starting at \(i\) to approach its stationary distribution.
Nodes with larger RWC are, on average, reached more quickly by diffusive processes and thus serve as more effective recipients in network communication.