Random walk closeness centrality is a measure of centrality in a network, which describes the average speed with which randomly walking processes reach a node from other nodes of the network.
It is similar to the closeness centrality except that the farness is measured by the expected length of a random walk rather than by the shortest path.
To calculate these probabilities of reaching a node for the first time in r steps, it is useful to regard the target node as an absorbing one, and introduce a transformation of M by deleting its j-th row and column and denoting it by
, P(i,j,r) can be expressed as Substituting this into the expression for mean first passage time yields Using the formula for the summation of geometric series for matrices yields where I is the n-1 dimensional identity matrix.
In such a network, the random walk closeness centrality of a node is roughly proportional to, but does not increase monotonically with its degree.
Random walk closeness centrality is more relevant measure than the simple closeness centrality in case of applications where the concept of shortest paths is not meaningful or is very restrictive for a reasonable assessment of the nature of the system.
This is the case for example when the analyzed process evolves in the network without any specific intention to reach a certain point, or without the ability of finding the shortest path to reach its target.
One example for a random walk in a network is the way a certain coin circulates in an economy: it is passed from one person to another through transactions, without any intention of reaching a specific individual.
Furthermore, as shortest paths are not influenced by self-loops, random walk closeness centrality is a more adequate measure than closeness centrality when analyzing networks where self-loops are important.
[3] A related concept, proposed by Newman,[4] is random walk betweenness centrality.
Calculating random walk betweenness in large networks is computationally very intensive.
The expectation of the standard deviation of the return times of a random walk to a node constitutes its centrality.
Calculating the second order betweenness on large arbitrary graphs is also intensive, as its complexity is