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

Recently, I've been looking into motifs in networks (directed graphs) -- small connected induced subgraphs that appear significantly more frequently than in a "similar random graph".

In practice, we need to enumerate the induced subgraphs (up to isomorphism) in thousands of large random networks, which can take a long time, and requires some form of canonical labelling (e.g. FANMOD uses nauty). My feeling is that nauty is quite bulky and seems likely to be overkill for this feature because e.g. we only need to canonically label small graphs (in FANMOD they have at most 8 vertices -- although I haven't seen much interest in motifs with more than 4 vertices).

Question: Is there a package that specialises in the canonical labelling of small directed graphs?

In the case I'm interested in, we need to label millions of graphs on a small number of vertices.

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

Nauty really is optimized for small graphs, if you use the C library interface. McKay (and others, such as myself) frequently use this library to generate all graphs of a given small order, which requires canonical labeling of small graphs very quickly. This happens many many many times (see http://oeis.org/A000088 for the growth of the number of unlabeled graphs). In fact, McKay's program geng can compute all 12,005,168 graphs on 10 nodes in less than an hour on my laptop.

share|improve this answer
    
Thanks for that. It looks like others have avoided the bulkiness of nauty by chopping unused features (rather than use another package). –  Douglas S. Stones Jan 9 '11 at 2:31
add comment

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.