The Louvain algorithm was proposed in 2008 by researchers from the university of Louvain in Belgium, giving the algorithm its name. It relies on a measure of the density of connections within a community compared to the connections toward other nodes. This metric is called modularity, and it is the variable we are going to understand first.
Defining modularity
Modularity is a metric quantifying the density of links within nodes in the same community, compared to links between nodes in different communities.
Mathematically speaking, its definition is as follows:
Q = 1/(2m) * Σij [ Aij - kikj / (2m)] δ(ci, cj)
Where:
- Aij is 1 if nodes i and j are connected, 0 otherwise.
- ki is the degree of node i.
- m is the sum of all weights carried by the edges. We also have the relation Σi ki = 2m, since the sum over all nodes will count each edge twice.
- ci is the community the node i is assigned to by the algorithm.
- δ(x, y) is the Kronecker...
