Julia implementation of Louvain algorithm

I am trying to implement the Louvain Algorithm in Julia.

The paper describes the modularity gain as:

Modularity gain formula

Where Sum_in is the sum of the weights of the links inside C, Sum_tot is the sum of the weights if the links incident to nodes in C, K_i is the sum of the weights if the links incident to node i, K_i_in is the sum of the weights of the links from i to nodes in C, and m is the sum of the weights of all the links in the network.

My implementation is:

function linksIn(graph, communities, c)::Float32
    reduce(+,
        map(
            e-> (communities[e.src] == c && communities[e.dst] == c)
                ? e.weight
                : 0
            , edges(graph)
        )
    )
end

function linksTot(graph, communities, c)::Float32
    reduce(+,
        map(
            e-> (communities[e.src] == c || communities[e.dst] == c)
                ? e.weight
                : 0
            , edges(graph)
        )
    )
end

function weightsIncident(graph, node)::Float32
    reduce(+,
        map(
            n-> get_weight(graph, node, n)
            , neighbors(graph, node)
        )
    )
end

function weightsIncidentComunity(graph,communities, node, c)::Float32
    reduce(+,
        map(
            n-> (c == communities[n])
                ? get_weight(graph, node, n)
                : 0
            , neighbors(graph, node)
        )
    )
end

function modulGain(graph, communities, node, c)::Float32

    # Calculate the variables of the modularity gain equation
    wIn = linksIn(graph, communities, c);
    wTot = linksTot(graph, communities, c);
    k = weightsIncident(graph, node);
    k_com = weightsIncidentComunity(graph, communities, node, c);
    m = reduce(+, map(e->e.weight, edges(graph)));


    # return the result of the modularity gain equation

    return ((wIn +k_com) / (2*m) - ((wTot+k)/(2m))^2 )
        - ((wIn/(2m)) - (wTot/(2m))^2 - (k/(2m))^2 )
end

If I compare the results of the funcion modulGain the the difference in modularity I get the following examples for the first pass where each node is in its own comunity in this graph.

  • modulGain(graph, communities, 1, 1) -> 0.00010885417
  • modulDifference(graph, communities, 1, 1) -> 0.0

and

  • modulGain(graph, communities, 1, 3) -> 4.806646e-5
  • modulDifference(graph, communities, 1, 3) -> 5.51432459e-5

When running the algorithm using the Modularity Gain equation it tends to get stuck in an infinite loop.
And I want to avoid to use the modularity difference since there is a clear performance improvement when using the Modularity Gain Equation.

Can someone explain me what is wrong with my implementation?
Thank you.

Go to Source
Author: D. Saby