Algorithm - 2023.2 English

Vitis Libraries

Release Date
2023-12-20
Version
2023.2 English

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}
  1. undirected graph
  2. compressed sparse column (COO) format

The algorithm implemention is shown as the figure below:

Figure 1 : Louvain calculate modularity architecture on FPGA

Figure 1 Louvain calculate modularity architecture on FPGA