Random walks on directed graph in R

2
votes

I am new in R programming. I have a directed graph which has 6 nodes and also provided a probability matrix of 6 rows and 6 columns. If a random walker walk 100,000 steps on the graph should end up the output vector like the following: 0.1854753, 0.1301621,0.0556688, 0.1134808, 0.15344649, 0.3617481 corresponding to the probabilities of 6 nodes being visited in this random walk experiment(counts divided by the total number of steps, in this case, 100,000).

I need to create a function for this task and to demonstrate how to use it. The function takes a graph and number of steps as input.

The provided matrix as follows:

     [,1] [,2] [,3] [,4] [,5] [,6]

[1,]  0.0  0.5  0.3  0.0  0.0  0.2

[2,]  0.1  0.2  0.0  0.4  0.1  0.2

[3,]  0.5  0.0  0.0  0.0  0.0  0.5

[4,]  0.0  0.1  0.0  0.0  0.6  0.3

[5,]  0.0  0.0  0.0  0.4  0.0  0.6

[6,]  0.4  0.0  0.0  0.0  0.2  0.4

Can someone help me to solve the problem?

2
r

2 Answers

1
votes

Here is a step-by-step implementation using a Markov chain (through R library markovchain).

  1. We start by loading the library.

    library(markovchain);

  2. We define the transition matrix and states (here simply 1...6 for the graph nodes)

    mat <- matrix(c(
    0.0,  0.5,  0.3,  0.0,  0.0,  0.2,
    0.1,  0.2,  0.0,  0.4,  0.1,  0.2,
    0.5,  0.0,  0.0,  0.0,  0.0,  0.5,
    0.0,  0.1,  0.0,  0.0,  0.6,  0.3,
    0.0,  0.0,  0.0,  0.4,  0.0,  0.6,
    0.4,  0.0,  0.0,  0.0,  0.2,  0.4), ncol = 6, byrow = T)
states <- as.character(1:6);

  3. We define a Markov chain object.

    mc <- new(
    "markovchain",
    states = states,
    byrow = TRUE,
    transitionMatrix = mat,
    name = "random_walk");

  4. We now simulate a random walk consisting of nSteps (here 1e6) and obtain asymptotic probabilities for every state (node) with prop.table(table(...)) 

    nSteps <- 1e6;
random_walk <- markovchainSequence(nSteps, mc, t0 = "1");
prop.table(table(random_walk));
#random_walk
#       1        2        3        4        5        6
#0.185452 0.129310 0.055692 0.113410 0.153787 0.362349

    Note that asymptotic probabilities might change slightly if you re-run the code.

Wrapping this in a single function is straight-forward and I'll leave that up to you.

1
votes

Assuming you are giving probability matrix (prob_mat) for the directed graph and no of steps (no_of_steps) as input. This should do:

set.seed(150)

find_pos_prob <- function(prob_mat, no_of_steps){

                 x <- c(1:nrow(prob_mat))               # index for nodes
                 position <- 1                          # initiating from 1st Node
                 occured <- rep(0,nrow(prob_mat))       # initiating occured count

                 for (i in 1:no_of_steps)   {
                 # update position at each step and increment occurence
                 position  <-  sample(x, 1, prob = prob_mat[position,])      
                 occured[position] <- occured[position] + 1
                                            }
                 return (occured/no_of_steps)
                     }

find_pos_prob(prob_mat, 100000) 

#[1] 0.18506 0.13034 0.05570 0.11488 0.15510 0.35892

Data:

prob_mat <- matrix( c(0.0,  0.5,  0.3,  0.0,  0.0,  0.2,
                      0.1,  0.2,  0.0,  0.4,  0.1,  0.2,
                      0.5,  0.0,  0.0,  0.0,  0.0,  0.5,
                      0.0,  0.1,  0.0,  0.0,  0.6,  0.3,
                      0.0,  0.0,  0.0,  0.4,  0.0,  0.6,
                      0.4,  0.0,  0.0,  0.0,  0.2,  0.4), byrow = TRUE, ncol = 6)

Note: Simulation results will differ from analytical solutions. Ideally you should remove the seed, run the function 15-20 times and take the average of probabilities over the runs