diffusr (version 0.1.4)

random.walk: Graph diffusion using a Markov random walk

Description

A Markov Random Walk takes an inital distribution p0 and calculates the stationary distribution of that. The diffusion process is regulated by a restart probability r which controls how often the MRW jumps back to the initial values.

Usage

random.walk(p0, graph, r = 0.5, niter = 10000, thresh = 1e-04,
  do.analytical = FALSE, correct.for.hubs = FALSE)

# S4 method for numeric,matrix random.walk(p0, graph, r = 0.5, niter = 10000, thresh = 1e-04, do.analytical = FALSE, correct.for.hubs = FALSE)

# S4 method for matrix,matrix random.walk(p0, graph, r = 0.5, niter = 10000, thresh = 1e-04, do.analytical = FALSE, correct.for.hubs = FALSE)

Arguments

p0

an n x p-dimensional numeric non-negative vector/matrix representing the starting distribution of the Markov chain (does not need to sum to one).

graph

an (n x n)-dimensional numeric non-negative adjacence matrix representing the graph

r

a scalar between (0, 1). restart probability if a Markov random walk with restart is desired

niter

maximal number of iterations for computation of the Markov chain. If thresh is not reached, then niter is used as stop criterion.

thresh

threshold for breaking the iterative computation of the stationary distribution. If the absolute difference of the distribution at time point $t-1$ and $t$ is less than thresh, then the algorithm stops. If thresh is not reached before niter, then the algorithm stops as well.

do.analytical

boolean if the stationary distribution shall be computed solving the analytical solution or rather iteratively

correct.for.hubs

if TRUE multiplies a correction factor to the nodes, such that the random walk gets not biased to nodes with high degree. In that case the original input matrix will be normalized as: $$ P(j | i) = 1 /degree(i) * min(1, degree(j)/degree(j))$$ Note that this will not consider edge weights.

Value

returns a list with the following elements

  • p.inf the stationary distribution as numeric vector

  • transition.matrix the column normalized transition matrix used for the random walk

References

Tong, H., Faloutsos, C., & Pan, J. Y. (2006), Fast random walk with restart and its applications. Koehler, S., Bauer, S., Horn, D., & Robinson, P. N. (2008), Walking the interactome for prioritization of candidate disease genes. The American Journal of Human Genetics

Examples

# NOT RUN {
 # count of nodes
 n <- 5
 # starting distribution (has to sum to one)
 p0    <- as.vector(rmultinom(1, 1, prob=rep(.2, n)))
 # adjacency matrix (either normalized or not)
 graph <- matrix(abs(rnorm(n*n)), n, n)
 # computation of stationary distribution
 pt    <- random.walk(p0, graph)

# }