Correlation Clustering 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?
 A: 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. 
A: 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. 

You can spot natural clusters, like:


*

*center top right are the Financial companies likes GS, BAC, WFC etc.

*Tech companies are top right: GOOD, AMZN, AAPL

*Hardware is to the east: NVDA, AMD, ADBE, TXN

*"Peninsula of Japan" in the south east: MTU, TM, HMC.


here's the code used to generate images likes this:
github repo
A: 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.
