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
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)