igraph-help
[Top][All Lists]

## Re: [igraph] Counting stars and cliques

 From: Tamás Nepusz Subject: Re: [igraph] Counting stars and cliques Date: Wed, 4 Apr 2012 13:17:06 +0200

```> 1. Is there a more efficient way than counting all motifs, since I am only
> interested in stars and cliques here?

For cliques, you may try searching for the maximal cliques using
igraph_maximal_cliques, or use igraph_cliques to enumerate all the cliques
explicitly. igraph_maximal_cliques is faster; igraph_cliques is just a
brute-force method that builds cliques of size 2 (these are the edges), size 3,
size 4 etc, until it reaches the desired clique size. However, with
igraph_maximal_cliques, you must evaluate pairwise intersections of maximal
cliques to avoid counting cliques more than once.

I don't think there is any efficient method for stars in igraph, apart from
iterating over all the vertices, and:

1. taking the subgraph consisting of the neighbors of the vertex only (not the
vertex itself) and
2. finding independent vertex sets in the neighborhood graph using
igraph_independent_vertex_sets. Since independent vertex sets do not have any
edges between them, the subgraph spanned by the independent vertex set and the
original vertex must be a star. Here, you may also employ the trick of finding
only the maximal independent vertex sets in the subgraph, since every subset of
the maximal independent vertex set is also an independent vertex set.

> 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