[igraph] cut_prob in igraph_motifs_randesu_estimate

[Eric Weese]

Hi all -

I'm getting some results that I don't understand using the R  
interface to igraph:

test.graph <- graph.formula(D-A-B-G, E-A-C-I, F-B-C-H)
replicate(10, graph.motifs.est(test.graph,sample=V 
(test.graph),cut.prob=c(0,0,0)))
replicate(10, graph.motifs.est(test.graph,sample=V 
(test.graph),cut.prob=c(0,0,0.5)))
replicate(10, graph.motifs.est(test.graph,sample=V 
(test.graph),cut.prob=c(0,0.5,0)))

the first two sets of results make sense to me (cutting half the time  
reduces the estimate in half), but the third one seems way too low.   
I see the following code around line 421 of motifs.c:

      if (level < size-1 &&
          !igraph_vector_empty(&adjverts) &&
          (cp==0 || RNG_UNIF01() > cp)) {
        /* yes, step down */
...

but this means if the random number is low, then we go to "else".   
Should this be


      if (level < size-1 &&
          !igraph_vector_empty(&adjverts)) {
        /* yes, step down */
        long int neifather=igraph_vector_pop_back(&adjverts);
        long int nei=igraph_vector_pop_back(&adjverts);
        IGRAPH_CHECK(igraph_stack_push(&stack, neifather));
        IGRAPH_CHECK(igraph_stack_push(&stack, nei));
        IGRAPH_CHECK(igraph_stack_push(&stack, level+1));
        if(cp==0 || RNG_UNIF01() > cp) {
          IGRAPH_CHECK(igraph_vector_push_back(&vids, nei));
...

instead?  This seems to work better for me...


Thanks!

-Eric
 (PhD candidate, Economics, MIT)