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

Collaborative graph exploration algorithm

Given an undirected graph G of (10 .. 500) vertices and (vertice_count .. 1000) edges.
A vertex can have (1 .. 6) edges. All edges have a unique cost of 1.

Given K agents, all starting from the same vertex START.

What would be the best way to explore the graph to visit all the vertices in as little time as possible?

I tried running a DFS from START which gives me all the shortest paths to the “leaves” of the graph and then sort the paths by their length.

Unfortunately there are often more paths than there are agents, so I have to re-assign agents which have explored the shortest paths. That’s where I’m stuck and would appreciate any kind of help (suggestions, ideas, algorithms…)

Go to Source
Author: ZogStriP