I am trying to implement the Louvain Algorithm in Julia.

The paper describes the modularity gain as:

Where

Sum_inis the sum of the weights of the links inside C,Sum_totis the sum of the weights if the links incident to nodes in C,K_iis the sum of the weights if the links incident to node i,K_i_inis the sum of the weights of the links from i to nodes in C, andmis 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