11
$\begingroup$

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?

$\endgroup$
13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, this looks promising. I will take a look at the Gomez et al. article. Is there an implementation? $\endgroup$ – Philip Leifeld Jan 22 '14 at 17:42
  • 1
    $\begingroup$ Yes, I think you'll find the source code here: deim.urv.cat/~sgomez/radatools.php $\endgroup$ – Vincent Labatut Jan 22 '14 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 igraph using absolute weights in each partition? $\endgroup$ – Fr. Jan 24 '14 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$ – Vincent Labatut Jan 24 '14 at 19:54
6
$\begingroup$

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.

$\endgroup$
  • $\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 communities object using the modularity function. 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$ – Philip Leifeld Jan 22 '14 at 17:48
3
$\begingroup$

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.

Esmailian, P. and Jalili, M., 2015. Community detection in signed networks: the role of negative ties in different scales. Scientific reports, 5, p.14339

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.