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 delta function, which is equal to 1 if x=y and 0 otherwise.
To understand the meaning of this equation, let's focus on each of the terms separately. A node i with ki edges has ki chances of being connected to any other node in the graph. So two nodes i and j have ki x kj chances of being connected to each other. Hence, the term kikj / (2m) corresponds to the probability...
