I am trying to implement the Louvain Algorithm in Julia.
The paper describes the modularity gain as:
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