exact modularity: A quick benchmark for threaded graph subset enumeration.

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.


This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s