[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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 
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.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]