This question already has an answer here:

Consider an undirected graph $g$ with some edges having negative weight - all weights in $[-1,1]$. We are seeking communities or clusters. Negative edge weight means repulsion and positive means attraction. Most of the methods I've seen work with positive edges or somehow ignore the negative sign, for example, by rescaling $[-1,1]$ to $[0,2]$ or simply considering absolute value $\|[-1,1]\|$, - etc.

But I cannot ignore the sign. Consider for example a graph with only negative edge weights. If we ignore the negative sign (rescaling, or $\|x\|$, etc.) and use regular methods, then clustering communities will still appear. But by the meaning of repulsion, each node should form its own community in a graph with only negative edge weights, because it cannot cluster with a node that linked to it by an edge with negative weight.

Does anyone know of any method or algorithm that does this?

P.S. This stems from some applied problems, for example, finding communities in groups of people where hate-love relationships are allowed. Note this question was asked IMHO in a less precise formulation and got vague responses. I am still not sure if this is the same as mine, but in any case there are no useful (for me) answers there, and my repulsion seems absent their at all.


marked as duplicate by Nick Cox, John, gung, kjetil b halvorsen, Christoph Hanck Nov 27 '15 at 13:35

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 5
    $\begingroup$ Your 2nd link is broken. Did you have a look at this question? stats.stackexchange.com/questions/177507/… $\endgroup$ – Vincent Labatut Nov 26 '15 at 18:06
  • $\begingroup$ @VincentLabatut yes, that is exactly my 2nd link. fixed. $\endgroup$ – iLie Nov 26 '15 at 19:00
  • $\begingroup$ Well, then your question is similar, see my answer there :) $\endgroup$ – Vincent Labatut Nov 26 '15 at 20:27
  • $\begingroup$ @VincentLabatut some of works seem useful, but definition "Correlation clustering provides a method for clustering a set of objects into the optimum number of clusters without specifying that number in advance." has no mention of negativity specifically, sounds quite general. Why did you point to that? $\endgroup$ – iLie Nov 26 '15 at 23:02
  • $\begingroup$ If you read the rest of the page, you'll see that it actually mention negative links. $\endgroup$ – Vincent Labatut Nov 27 '15 at 7:28