Introduction

diffusr implements algorithms for network diffusion such as Markov random walks with restarts and weighted neighbor classification. Network diffusion has been studied extensively in bioinformatics, e.g. in the field of cancer gene prioritization. Network diffusion algorithms generally spread information in the form of node weights along the edges of a graph to other nodes. These weights can for example be interpreted as temperature, an initial amount of water, the activation of neurons in the brain, or the location of a random surfer in the internet. The information (node weights) is iteratively propagated to other nodes until a equilibrium state or stop criterion occurs.

Tutorial

First load the package:

library(diffusr)

Markov random walks

A Markov random walk with restarts calculates the stationary distribution: \[\begin{equation} \mathbf{p}_{t+1} = (1 - r) \mathbf{W} \mathbf{p}_t + r \mathbf{p}_0, \end{equation}\]

where \(r \in (0,1)\) is a restart probability of the Markov chain, \(\mathbf{W}\) is a column-normalized stochastic matrix (we do the normalization for you) and \(\mathbf{p}_0\) is the starting distribution of the Markov chain. We calculate the iterative updates, it is also possible to do the math using the nullspace of the matrix (comes later).

If you want to use Markov random walks just try something like this:

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

The stationary distribution should have changed quite a bit from the starting distribution:

  print(t(p0))
##      [,1] [,2] [,3] [,4] [,5]
## [1,]    1    0    0    0    0
  print(t(pt))
##      p.inf     transition.matrix
## [1,] Numeric,5 Numeric,25

You can also use a matrix p0:

   p0 <- matrix(c(p0, runif(20)), nrow=n)
   pt <- random.walk(p0, graph)
   pt
## $p.inf
##            [,1]       [,2]      [,3]      [,4]      [,5]
## [1,] 0.55226905 0.22799117 0.1357461 0.2243023 0.2140069
## [2,] 0.13281860 0.23605919 0.2810219 0.1407579 0.2016140
## [3,] 0.10869530 0.20979157 0.1575636 0.2776249 0.2242563
## [4,] 0.16549612 0.23813009 0.2947860 0.2401973 0.2275582
## [5,] 0.04072094 0.08802797 0.1308825 0.1171176 0.1325647
## 
## $transition.matrix
##            [,1]       [,2]        [,3]       [,4]      [,5]
## [1,] 0.00000000 0.22009731 0.457688510 0.07243764 0.3330862
## [2,] 0.29633695 0.00000000 0.004210365 0.50145966 0.4553723
## [3,] 0.13110101 0.55640971 0.000000000 0.39438324 0.1423866
## [4,] 0.48242069 0.06276502 0.491559010 0.00000000 0.0691549
## [5,] 0.09014135 0.16072797 0.046542114 0.03171946 0.0000000

In the later case, a random walk is done over all columns of p0 separately.

Analytical vs iterative solution

In the last section we computed the iterative solution of the stationary distribution. You can also choose to do this analytically. In that case we need to take the inverse of the transition matrix which might lead to numerical instability, though. However, it usually runs faster than the iterative version.

   pt <- random.walk(p0, graph, do.analytical=TRUE)
   pt
## $p.inf
##            [,1]       [,2]      [,3]      [,4]      [,5]
## [1,] 0.55226569 0.22799017 0.1357432 0.2243022 0.2140061
## [2,] 0.13282468 0.23606025 0.2810242 0.1407588 0.2016151
## [3,] 0.10868831 0.20979240 0.1575691 0.2776222 0.2242561
## [4,] 0.16550190 0.23812921 0.2947807 0.2401996 0.2275581
## [5,] 0.04071942 0.08802798 0.1308829 0.1171171 0.1325645
## 
## $transition.matrix
##            [,1]       [,2]        [,3]       [,4]      [,5]
## [1,] 0.00000000 0.22009731 0.457688510 0.07243764 0.3330862
## [2,] 0.29633695 0.00000000 0.004210365 0.50145966 0.4553723
## [3,] 0.13110101 0.55640971 0.000000000 0.39438324 0.1423866
## [4,] 0.48242069 0.06276502 0.491559010 0.00000000 0.0691549
## [5,] 0.09014135 0.16072797 0.046542114 0.03171946 0.0000000

Nearest neighbors

Diffusion using nearest neighbors is done by traversing through a (weighted) graph and take all the neighbors of a node until a certain depths in the graph is reached. We find shortest paths using priority queues:

  # count of nodes
  n <- 10
  # indexes(integer) of nodes for which neighbors should be searched
  node.idxs <- c(1L, 5L)
  # the adjaceny matrix (does not need to be symmetric)
  graph <- rbind(cbind(0, diag(n-1)), 0)
  # compute the neighbors until depth 3
  neighs <- nearest.neighbors(node.idxs, graph, 3)

Let’s see what which nodes we got:

  print(neighs)
## $`1`
## [1] 2 3 4
## 
## $`5`
## [1] 6 7 8

Heat diffusion

A Laplacian heat diffusion process calculates the heat distribution over a graph after at a specific time \(t\): \[\begin{equation} h_i(t) = h_i(0)\exp(-\lambda_i t) \end{equation}\]

where \(\mathbf{h}_0\) is the initial heat distribution, \(\mathbf{h}_t\) is the heat distribution at time \(t\) and \(\boldsymbol \lambda\) are the eigenvalues of the of your graph.

You can use the Laplacian heat diffusion process like this:

  # count of nodes
  n <- 5
  # starting distribution (has to sum to one)
  h0    <- 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
  ht    <- heat.diffusion(h0, graph)

Here are the results:

  print(t(h0))
##      [,1] [,2] [,3] [,4] [,5]
## [1,]    0    1    0    0    0
  print(t(ht))
##            [,1]      [,2]      [,3]       [,4]       [,5]
## [1,] 0.09531005 0.6233521 0.1017696 0.03874001 0.07685937

As before, p0 can also be a matrix:

   h0 <- matrix(c(h0, runif(20)), nrow=n)
   ht <- heat.diffusion(h0, graph)
   ht
##            [,1]      [,2]      [,3]       [,4]      [,5]
## [1,] 0.09531005 0.4464796 0.2096083 0.37831190 0.4715880
## [2,] 0.62335207 0.6152682 0.2679380 0.15742189 0.6026093
## [3,] 0.10176964 0.6913712 0.3308819 0.19546185 0.6427944
## [4,] 0.03874001 0.2099435 0.5496193 0.07000514 0.6931768
## [5,] 0.07685937 0.5613325 0.5680021 0.19615201 0.2657943