Louvain algorithm implementation:
Louvain(G(V, E, W), Cid)
Q_old := 0
Q_new := 0
Cid_new := C_init
ColorSets = Coloring(V)
while true // Iterate until modularity gain becomes negligible.
for each node Vk in ColorSets
Cid_old := Cid_new
for each v in Vk
vCid := Cid_old[v]
for each e in e \cup (v, E, W)
maxQ := max(\Delta Q)
target := Cid_old[e]
if maxQ > 0 then
Cid_new[v] = target
Q_new := Q(Cid_new)
if Q_new < Q_old then
break
else
Q_old = Q_new
return {Cid_old, Q_old}
- undirected graph
- compressed sparse column (COO) format
The algorithm implemention is shown as the figure below:
Figure 1 : Louvain calculate modularity architecture on FPGA