Function modularity should consider directed graphs

[vgauthier]

The definition of the modularity could easily be extended to directed graphs (cf. ref. [1]) with minor tweak of the original algorithm.

[1] E. A. Leicht and M. E. J. Newman. Community structure in directed networks. Physical Review
Letter, 100:118703, 2008. (PDF)

[jpfairbanks]

This would make a good hacktoberfest PR.

[simonschoelly]

Would it be a good idea to also add optional weights to this algorithm?

[vgauthier]

I would be nice addon indeed, but LightGraphs is not suppose to handle weighted graphs right ?

How do you propose to handle the weighted case: by the SimpleWeightedGraphs or by passing an array of weights to the function ?

[jpfairbanks]

You would take a keyword argument with the weights which would default to weights(g). For SimpleGraph the weight(g) is a struct that represents the matrix ones(Int, nv(g), nv(g)).

[vgauthier]

@jpfairbanks Thank for your advice, I am almost done with the implementation of the modularity for directed and weighted graphs. However, for the weighted case I need to compute the sum of the weight of a graph. This operation is okay when I use SimpleWeightedGraph

julia> g = SimpleWeightedGraph(3);
julia> add_edge!(g, 1, 2, 1);
julia> add_edge!(g, 2, 3, 1);
julia> add_edge!(g, 3, 1, 1);
julia> barbell = blockdiag(g, g);
julia> add_edge!(barbell, 1, 4, 5);

julia> sum(weights(g))
22

However when I do the same operation with SimpleGraph I get a weird answer (the sum of a matrix where all elements are equals to 1) instead of getting a matrix with a one in all entries where there is an edge and zero elsewhere. Is it an expected behavior ?

julia> g = SimpleGraph(3);
julia> add_edge!(g, 1, 2);
julia> add_edge!(g, 2, 3);
julia> add_edge!(g, 3, 1);
julia> barbell = blockdiag(g, g);
julia> add_edge!(barbell, 1, 4);

julia> sum(weights(g))
36

[jpfairbanks]

yeah that is the expected behavior. It is a little non-intuitive, but the idea was that you are only supposed to use weights(g)[u,v] for known edges in g. We might want to override the definition of sum for that struct.

[vgauthier]

@jpfairbanks okay, thanks for the explanation. I finished the implementation of the modularity for directed and weighted case. Do you want me to open a new PR or update the PR I already opened about the modularity ?

[jpfairbanks]

I just reviewed the other PR. I'll merge it into master and then you can base your new PR against master.