Solved – Graph clustering algorithms which consider negative weights

Question

I have a graph instance with weighted directed edges which values can be in range [-1,1]. I need to do clustering on this graph, in order to find out groups in which vertices are more correlated.

I searched for several clustering or community detection graph based algorithms, but most of them don't work because the negative weights. Up to now I have applied spinglass (it is so called in igraph library, it is an algorithm based on Potts model) algorithm which seems to work with both positive and negative weights.

Are there any other algorithms for doing clustering or community detection on graphs which have negative and positive edge weights?

Update: the edge weights represent correlations, 1 means that two vertices are strongly correlated, -1 that are inversely correlated and 0 means that are indipendent.

Answer 1

Have you tried mapping the values to [0;2]?

Then many algorithms may work.

Consider e.g. Dijkstra: it requires non-negative edge weights, but if you know the minimum a of the edges, you can run it on x-a and get the shortest cycle-free path.

Update: for correlation values, you may either be interested in the absolute values abs(x) (which is the strength of the correlation!) or you may want to break the graph into two temporarily: first cluster on the positive correlations only, then on the negative correlations only if the sign is that important for clustering & the previous approaches don't work.