Date: Sat, 30 Aug 2008 13:14:07 +0200
From: Csardi Gabor <address@hidden>
Subject: Re: [igraph] cut_prob in igraph_motifs_randesu_estimate
To: Help for igraph users <address@hidden>
Message-ID: <address@hidden>
Content-Type: text/plain; charset=us-ascii
Eric, thanks for your mail, sorry for the delay, I was away for a
while.
I think the igraph code is correct, 'cut.prob' gives the cutting
probability at each level of the search tree. In other words, we
_stop_
with this probability.
Your second test case is simple, it indeed finds about half of the
motifs.
The third test case is more complicated, however. I could not
calculate
the expected number of motifs with pen and paper, and it might depend
on how "clustered" the triads are in your graph.
See e.g.:
g1 <- graph.star(100, mode="undirected")
g2 <- graph.ring(100, circ=FALSE)
graph.motifs.no(g1)
[1] 4851
graph.motifs.no(g2)
[1] 98
mean(replicate(100, graph.motifs.est(g1, sample=V(g1), cut.prob=c
(0,0.5,0))))
[1] 29.08667
mean(replicate(100, graph.motifs.est(g2, sample=V(g2), cut.prob=c
(0,0.5,0))))
[1] 29.01
The purpose of having 'cut.prob' for 'graph.motifs.est' is that
you might want to know how many motifs you expect to find with
'graph.motifs', without actually classifying them, because much of the
running time is the classification part. (Especially if bigger
motifs will be supported some time in the near future.)
Best,
Gabor
On Tue, Aug 26, 2008 at 02:17:11PM -0400, Eric Weese wrote:
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)
_______________________________________________
igraph-help mailing list
address@hidden
http://lists.nongnu.org/mailman/listinfo/igraph-help