How does random_edge_walk compute the probabilities in r-igraph?

Lynd · 16 August 2022 07:36

Hi,
How is the probability of selecting an edge computed by random_edge_walk()? Is it the weight of this edge multiplied by a normalizing constant? If so, is it the same constant for all the edges?

Thanks

iosonofabio · 16 August 2022 13:18

Hey Lynd,

Welcome to the forums!

When the walk is sitting on a vertex and choosing which edge to follow, the probability of each edge is proportional to its weight. So the probability is equal to the edge’s weight divided by the sum of the weights of all outgoing edges from the same vertex.

The R function calls the underlying C library, see the code for more info:

github.com

igraph/igraph/blob/2fb0227d8768672907ca3acc4d92a132c9e19de1/src/paths/random_walk.c#L238


      
          /* are we stuck? */
          if (IGRAPH_UNLIKELY(degree == 0)) {
              igraph_vector_resize(edgewalk, i); /* can't fail since size is reduced, skip IGRAPH_CHECK */
              if (stuck == IGRAPH_RANDOM_WALK_STUCK_RETURN) {
                  break;
              } else {
                  IGRAPH_ERROR("Random walk got stuck.", IGRAPH_ERWSTUCK);
              }
          }
          
          
if (weights) { /* weighted: choose an out-edge with probability proportional to its weight */
              igraph_real_t r;
              igraph_vector_t **cd = (igraph_vector_t **) & (VECTOR(cdfs)[start]);
          
          
    /* compute out-edge cdf for this node if not already done */
              if (IGRAPH_UNLIKELY(! *cd)) {
                  long j;
          
          
        *cd = IGRAPH_CALLOC(1, igraph_vector_t);
                  if (*cd == NULL) {
                      IGRAPH_ERROR("Random edge walk failed.", IGRAPH_ENOMEM);

Cheers,
Fabio

Lynd · 17 August 2022 07:28

Thanks Fabio for the clarification.

Topic		Replies	Views
Sampling a simple path at random Usage R	2	197	21 June 2022
Longest path in a weighted DAG Usage R	4	848	31 July 2020
Will there be a significant improvement (>10 times speed) in shortest path calculation if using C instead of R version? Usage C , R	3	1900	30 January 2020
Question about the functionality of partial sum trees Usage C	9	293	2 July 2022
Is this a correct way to create an igraph object? Usage R	0	342	21 November 2020

How does random_edge_walk compute the probabilities in r-igraph?

Related Topics