The modularity of a graph is defined on its Wikipedia page. In a different post, somebody explained that modularity can easily be computed (and maximized) for weighted networks because the adjacency matrix $A_{ij}$ can as well contain valued ties. However, I would like to know whether this would also work with signed, valued edges, ranging, for instance, from -10 to +10. Can you provide an intuition, proof or reference on this issue?
Solved – Does Newman’s network modularity work for signed, weighted graphs
clusteringdata visualizationmodularitynetworkspartitioning
Best Answer
The straightforward generalization of the modularity for weighted networks does not work if those weights are signed. By straightforward, I mean: just using the weight matrix instead of the adjacency one, like Newman does, for instance, in (Newman 2004). You need a specific version, such as that cited by BenjaminLind, or that of (Gomez et al. 2009).
In both articles, they explain the reason for this. In summary: the modularity relies on the fact some normalized degrees (or strengths in the case of weighted networks) can be considered as probabilities. The probability a link exists between nodes $i$ and $j$ is estimated using $p_ip_j=w_iw_j/(2w)^2$, where $w_i$ and $w_j$ are the respective strengths of nodes $i$ and $j$ and $w$ is the total strength over all the network nodes. If some weights are negative, then the original normalization doesn't guarantee having values in $[0,1]$ anymore, so the above $p_ip_j$ quantity cannot be considered as a probability.
To solve this problem, Gomez et al. consider positive and negative links separately. They obtain two distinct modularity values: one for positive links, one for negative ones. They substract the latter from the former to get the overall modularity.