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

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

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