1

Correlation Clustering : Given a signed graph where the edge label indicates whether two nodes are similar (+) or different (−), the task is to cluster the vertices so that similar objects are grouped together.

Papers report that task is NP-Complete and suggest Approximation Algorithms. Can one recommend me a fast-implementation of a naive algorithm to do the task?

damned
  • 221
  • 2
    The closely related question at http://stats.stackexchange.com/questions/2976/ concerns clustering by similar values of the correlations themselves. Although this is not precisely what is being asked here, perhaps it offers some partial help. However, I suspect the present question has been stated ambiguously. As it is, there is an obvious and trivial solution: remove all "-" edges and report the connected components of the graph that remains. This clearly groups the similar objects and is unique; it's definitely not NP-complete. So what really is your question? – whuber Apr 26 '13 at 13:31

3 Answers3

5

Here are references for a graph theoretic / social networks approach to clustering:

Guimera , R., Sales-Pardo, M., Amaral, L. (2004). Modularity From Fluctuations In Random Graphs and Complex Networks. Physical Review E. 70 (2), 025101

Reichardt, J., and Bornholdt, S. (2006). Statistical Mechanics of Community Detection, Phys. Rev. E, 74, 016110 (2006), URL: http://arxiv.org/abs/cond-mat/0603718.

The algorithm is implemented in an R package called igraph and is called spinglass.community().

The subfield is often called "community detection," "graph clustering," or "network clustering" and there are many algorithms. This one happens to handle signed and weighted edges.

The following reference compares many algorithms for efficiency:

Danon, Díaz-Guilera, Duch & Arenas. (2005). Comparing Community Structure Identification. Journal of Statistical Mechanics: Theory and Experiment. 2005 (9), P09008.

ndoogan
  • 1,340
  • 1
    To say that the subfield is called community detection is oversimplifying it. In most disciplines the field is simply called 'graph clustering' or 'network clustering'. Refer to my answer here: http://stats.stackexchange.com/questions/15824/what-is-the-difference-between-graph-clustering-and-community-detection-methods/60265#60265. Clustering algorithms that one might want to consider additionally (all these have implementations available as well) are DBSCAN, Louvain clustering, RNSC and MCL. – micans Jun 12 '13 at 11:02
4

My quick and dirty way to find visualize clusters in graphs is to use the Fruchterman-Reingold force-directed algorithm. The algorithm works as follows:

  • take each node, which has weighted (both positive and negative) edges to other nodes, and random toss them on a 2-d plane.
  • At each iteration (up to 50 or so), the edges act as springs connecting nodes, and there is a calculable force on each node according to the forces acting on it: edges with a high weight attract nodes, and edges with a negative weight repel nodes.

That's it! Nodes eventually start to cluster together. Here's an example I did for a finance project: The nodes are stocks and the edges are correlations.

enter image description here

You can spot natural clusters, like:

  1. center top right are the Financial companies likes GS, BAC, WFC etc.
  2. Tech companies are top right: GOOD, AMZN, AAPL
  3. Hardware is to the east: NVDA, AMD, ADBE, TXN
  4. "Peninsula of Japan" in the south east: MTU, TM, HMC.

here's the code used to generate images likes this:

github repo

Cam.Davidson.Pilon
  • 12,153
2

Here you can find a simple correlation clustering algorithm.

http://en.wikipedia.org/wiki/Correlation_clustering#Algorithms

Even though the algorithm is very easy to implement, if you want, I can give you the python implementation.

Naffi
  • 121