> 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. Best, Tamas _______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
