# random-walk-methods: Graph diffusion using a Markov random walk In diffusr: Network Diffusion Algorithms

## 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

 ``` 1 2 3 4 5 6 7 8 9 10``` ```random.walk(p0, graph, r = 0.5, niter = 10000, thresh = 1e-04, do.analytical = FALSE, correct.for.hubs = FALSE) ## S4 method for signature 'numeric,matrix' random.walk(p0, graph, r = 0.5, niter = 10000, thresh = 1e-04, do.analytical = FALSE, correct.for.hubs = FALSE) ## S4 method for signature '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

 ```1 2 3 4 5 6 7 8``` ``` # 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) ```

diffusr documentation built on May 2, 2019, 3:42 a.m.