MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

Sagemath has three methods that can let you :

* detect a small subgraph -- induced or not, you can chose
* iterate the different occurences
* count them

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)

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

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

Your Answer


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.