Graph diffusion using a Markov random walk

Share:

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
random.walk(p0, graph, r = 0.5, ...)

Arguments

p0

an n-dimensional numeric non-negative vector 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

...

additional parameters

Value

returns the stationary distribution as numeric vector

Author(s)

Simon Dirmeier, simon.dirmeier@gmx.de

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)