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.


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()

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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