Random-Walk Closeness Centrality


Definition

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.

Consider a weighted network – either directed or undirected – with n nodes denoted by j=1, …, n; and a random walk process on this network with a transition matrix M. The m_{jk} element of M describes the probability of the random walker that has reached node i, proceeds directly to node j. These probabilities are defined in the following way.

Random-Walk Closeness Centrality

where  a_{ij} is the (i,j)th element of the weighting matrix A of the network. When there is no edge between two nodes, the corresponding element of the A matrix is zero.

The random walk closeness centrality of a node i is the inverse of the average mean first passage time to that node:

Random-Walk Closeness Centrality

Mean first passage time

The mean first passage time from node i to node j is the expected number of steps it takes for the process to reach node j from node i for the first time:

Random-Walk Closeness Centrality

where P(i,j,r) denotes the probability that it takes exactly r steps to reach j from i for the first time. 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 Random-Walk Closeness Centrality. As the probability of a process starting at i and being in k after r-1 steps is simply given by the (i,k)th element of Random-Walk Closeness Centrality, P(i,j,r) can be expressed as

Random-Walk Closeness Centrality

Substituting this into the expression for mean first passage time yields

Random-Walk Closeness Centrality

Using the formula for the summation of geometric series for matrices yields

Random-Walk Closeness Centrality

where I is the n-1 dimensional identity matrix.

For computational convenience, this expression can be vectorized as

Random-Walk Closeness Centrality

where Random-Walk Closeness Centrality is the vector for first passage times for a walk ending at node j, and e is an n-1 dimensional vector of ones.

Mean first passage time is not symmetric, even for undirected graphs.
[Random walk closeness centrality. (2013, March 7). In Wikipedia]

References

  • NOH, J. D. & RIEGER, H. 2004. Random walks on complex networks. Physical review letters, 92, 118701.
  • Random walk closeness centrality. (2013, March 7). In Wikipedia, The Free Encyclopedia. Retrieved 07:56, August 6, 2014, from http://en.wikipedia.org/w/index.php?title=Random_walk_closeness_centrality&oldid=542550793