Original ticket https://networkx.lanl.gov/trac/ticket/245
Reported 2009-06-17 by trac user dcurtis, assigned to @chebee7i.

Here is a version of the algorithm from "Finding community structure in very large networks" by Aaron Clauset, M.E.J. Newman, and Cristopher Moore.

I think there are some things I could probably do better but the algorithm is pretty intensive. If there was a maxheapq structure in Python it might save some time. Any improvements I'd love to see. It's not simple, consult the paper if you're curious why I did what I did.

One thing that I do that's somewhat crazyish is that I am building a dendrogram of the process. Thus, each node is actually a tuple containing what are supposed to be communities. In the end you'd have a single root node that is all communities as one.

The authors do provide a version of this written in C but of course they have lots of fun stuff to do because they don't have the Python datastructures. However, theirs runs faster. With that said, I did test my algorithm and it gives identical results.