Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

In learning about network motifs, I discover claims that Mfinder (circa 2004) is the "the first motif-mining tool" (Kashani et al. 2009). Motifs are connected induced subgraphs that occur more frequently than in "similar random graphs" (these graphs may be directed or undirected).

While Mfinder might be the first specifically aimed at finding motifs, I suspect there will have been earlier packages that could count the number of induced subgraphs isomorphic to a small graph H in a large graph G.

Question: What are some earlier packages that enable counting the number of induced subgraphs in G that are isomorphic to some given small graph H?

After Mfinder a range of motif finding packages have been developed. The ones I've heard of are MAVisto, FanMod, NoMoFinder, an unnamed package by Grochow and Kellis and Kavosh. I'd also be interested in hearing about any other packages that can perform subgraph enumeration.

share|improve this question

1 Answer 1

Sagemath has three methods that can let you :

* detect a small subgraph -- induced or not, you can chose
  http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.subgraph_search
* iterate the different occurences
  http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.subgraph_search_iterator
* count them
  http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.subgraph_search_count

All three are about labelled occurences, so if you count the number of occurences of a $C_6$ in a $C_6$, you will find

sage: g = graphs.CycleGraph(6)
sage: g.subgraph_search_count(g)
12

Hopefully, you can divide the number by the cardinality of the automorphism group

sage: g.subgraph_search_count(g)/g.automorphism_group().order()
1
share|improve this answer
    
Thanks for that, I forgot about Sage! –  Douglas S. Stones Jan 17 '11 at 22:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.