gonum / graph

Graph packages for the Go language [DEPRECATED]
250 stars 39 forks source link

community: add directed Louvain implementation #160

Closed kortschak closed 8 years ago

kortschak commented 8 years ago

We have a directed->undirected converter type that allows Louvain to work on directed graphs, however this may give slightly different results when directed edges show significant asymmetry. So add the directed Louvain implementation.

The algorithm is pretty much the same as the undirected case and the mathematics is outlined in louvain.tex, but the details are left as an exercise for the reader. The first step is to add the final few lines to the derivation beyond Eq.29 to give a directed case update function analogous to Eq.19. (Also some typos need fixing in that file which can happen at the same time during review).

/cc @Armadilloa16

Armadilloa16 commented 8 years ago

Hmm this was awhile ago, I'll review it to refresh my memory and then have a think about it properly -- might take me a little while to find the time though. I have the memory of a goldfish haha.

Armadilloa16 commented 8 years ago

I had a look through this today, found some typos and one or two minor mistakes, and made a start on the details for the extension to the directed case. I suspect alot of the details will fall out and turn out to be trivially similar but I'm not confident so I want to do all the work, then if alot of it turns out to be equivalent I'll cut it back later. This is where I've been working on it for the time being: https://github.com/Armadilloa16/graph/commit/e3298f5940e89f342280bcb642b3512c84e052ad

kortschak commented 8 years ago

I'll wait until you're ready for review before I comment - it's easier there to do that than in commits and the comments don't get lost in the sea of changes.

kortschak commented 8 years ago

Fixed by #164.