Just uploading this short note/paper here in case anyone ever finds it useful and so I won't lose it again. I wrote this last year, during the summer as I worked on networks.

I implemented a fast - O(lg^3(n)n), almost linear - modularity optimization (community detection) algorithm based on the extremal optimization algorithm of Duch and Arenas (in turn based on Boettcher and Percus on other problems). The pdf details the algorithm and also has notes on the dataset I downloaded from arXiv to run the algorithm on.

I've glossed over a lot of details, but on the off chance it's useful, feel free to contact me for more information.

Download: Efficient Implementation of Community Detection Using Extremal Optimization (pdf, 112KB)