Internal Design of Louvain Modularity

Overview

The Louvain method for community detection is a method to extract communities from large networks created by Blondel from the University of Louvain (the source of this method’s name). The method is a greedy optimization method that appears to run in time O(n cdot log n), if n is the number of nodes in the network.

Algorithm

PageRank 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