Today I learned about the Girvan–Newman algorithm. It's a fairly quick way to break up networks of interacting components into clustered communities. It doesn't really join components in any way they aren't already connected. It just removes connections which don't meet betweenness requirements. If the starting network is a hairball, the final product is either distinct clusters or just a bunch of smaller hairballs (I seem to be getting the latter, for the most part, but my current networks are several thousand nodes with more than 40 thousand edges).

The clusterMaker2 plugin for Cytoscape has an implementation of this kind of community clustering. It uses GLay. The plugin hasn't been quite as fast for me as the GLay authors report but I'm content to blame that on my old* Core2 Quad 2.4GHz and/or the massive changes in Cytoscape over the last few years.


*This one came with the lab and was originally used for working with sequencing data. I'm going to use it until it dies and/or catches on fire.