I’ve been playing around with Newman’s modularity measure recently. I wanted to find the subset of vertices with maximum modularity and wrote a quick exhaustive enumeration routine to do so. It works on graphs with up to 64 vertices, although only up to 36 vertices would be practical.
The code is here: https://gist.github.com/993867
At the moment, it takes ~8 seconds with 3 threads to exhaustively enumerate subsets of a 25 node graph on a 4-core Intel i7-960. I’m curious if others can make this faster. So please, fork this code and improve it :-). (If only it were actually that easy to get my code optimized!)
I’m guessing a 10-fold improvement is possible with implementation tweaks. My hunch is 2-5-fold improvement is possible with algorithmic tweaks. For instance, only enumerating over subsets of less than half the vertices should cut a significant fraction of time off. However, partitioning those calls over threads will be more difficult then. So there should be a 20-50-fold improvement waiting in the wings.
Hope this helps someone else.