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?
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
4
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.
answered Jan 22, 2014 at 10:06
-
$\begingroup$ Thanks, this looks promising. I will take a look at the Gomez et al. article. Is there an implementation? $\endgroup$ Commented Jan 22, 2014 at 17:42
-
1$\begingroup$ Yes, I think you'll find the source code here: deim.urv.cat/~sgomez/radatools.php $\endgroup$ Commented Jan 22, 2014 at 19:34
-
$\begingroup$ the code looks blackboxed to EXE files, but if all you need is modularity for positive and negative weights, why not just (1) convert your matrix to a weighted edge list, (2) split the list between positively and negatively signed weights, and (3) compute modularity with
igraphusing absolute weights in each partition? $\endgroup$– Fr.Commented Jan 24, 2014 at 15:31 -
$\begingroup$ That's a good idea, but the modularity processed for negative weights must be minimized, and the methods in igraph only do maximization (as far as I know). As for the source code, I think you're right. Maybe you can contact directly one of the authors? $\endgroup$ Commented Jan 24, 2014 at 19:54
$\begingroup$
$\endgroup$
1
Yes, it can. Spin-glass models for community detection can compute modularity from weighted, signed graphs. You'll want Traag and Bruggeman "Community detection in networks with positive and negative links" as a reference. The function "spinglass.community()" in igraph can find the communities and return the graph's modularity.
-
$\begingroup$ Thank you. I am not really interested in the communities but rather in the tendency of the signed network to be polarized/fragmented into communities. But as far as I can see, the modularity can be retrieved from the resulting
communitiesobject using themodularityfunction. I will definitely take a look at the Traag and Bruggeman article. Since the implementation seems to be based on simulated annealing: how well does it perform? Can I actually make sure that the algorithm really returns the optimal modularity (since I want to measure polarization/fragmentation)? $\endgroup$ Commented Jan 22, 2014 at 17:48
$\begingroup$
$\endgroup$
0
We have pointed out the problem of Modularity[-alike] functions with signed networks in this paper. They tend to ignore the positive density of communities more as the absolute number of negative links in the network increases.
Also, here is our open source java project for weighted-signed networks, which is based on Constant Potts Model (similar to Modularity), fast Louvain algorithm, and community evaluation based on an extension of Map Equation.
