Re: [igraph] Counting stars and cliques

[Gábor Csárdi]

On Wed, Apr 4, 2012 at 7:17 AM, Tamás Nepusz <address@hidden> wrote:
[...]
>> 2. Is there an easy way in igraph to generalize motif_randesu for higher 
>> order motifs, i.e., size>4? Particularly, for counting stars and cliques 
>> with size>4?
> I have checked the code in motifs.c quickly, and I think that in theory, 
> motifs_randesu could be generalized for higher order motifs as long as 1) the 
> "size" is fixed (so you cannot make it find motifs of an arbitrary size), and 
> 2) you can construct arrays similar to igraph_i_isoclass_3_idx and 
> igraph_i_isoclass2_3 etc that are found in topology.c. Honestly, I don't know 
> what these arrays mean, they provide some kind of mapping between a motif and 
> an index in the result array -- Gabor can probably tell more about this, or 
> you can try deciphering motifs.c to figure out what they mean.

The code itself works for motifs of any (fixed) size, except for the
part that categorizes the motif found. This is because at the time of
writing it we did not have a good graph isomorphism implementation. We
still not have everything implemented for directed graphs. I think
that for undirected graphs, igraph_canonical_permutation() could be
used to work out the isomorphism class of a motif, but I am not saying
it is trivial.

You might just be better off using the original randesu
implementation, which is not very flexible and only runs from a GUI
unfortunately. (If I remember well.)

You cannot simply use the same algorithms as for motifs of size 3 and
4, because there are just too many possible labeled graphs of size 5
already.

Best,
Gabor

> Best,
> Tamas
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help



-- 
Gabor Csardi <address@hidden>     MTA KFKI RMKI