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
computation time of distances() significantly increases with edge weights?! Usage C , R	3	234	27 November 2022
weighted edge in degree calculation Usage R	2	659	11 August 2022
Sampling a simple path at random Usage R	2	269	21 June 2022
Shortest paths weights in C Usage C	3	708	8 June 2021
R igraph: edge weights should be interpreted as connection strenghts or distances? Usage R	3	1487	13 January 2023

How does random_edge_walk compute the probabilities in r-igraph?

Related topics