What is a good overlapping group algorithm?

Question

I am familiar with various clustering algorithms (k-means, etc.), but for my specific use case (social networks) I need an algorithm that detects overlapping groups. This algorithm neatly separates my Facebook friends from my high school friends, my college friends, my family, and my friends.

The algorithm used above (JUNG VoltageClusterer) divides the nodes into separate clusters. But I need an algorithm that can assign nodes to multiple clusters (for example, my friend can be both my high school friend and college friend).

How can I do it? It would be nice if I could use this algorithm for weighted graphs, and not just unweighted ones.

Answer 1

Palla et al. have a good Nature document on detecting overlapping communities: http://www.nature.com/nature/journal/v435/n7043/full/nature03607.html They demonstrate their success in various types of networks, from social to protein interactions.

The algorithm is called k-clique percolation. It is implemented in the C-finder program: http://www.cfinder.org/

Answer 2

Answering my own question, I found a decent piece of paper: http://www.springerlink.com/content/y44484587755k478/

Any other documents / approaches are useful.

Answer 3

You can try fuzzy c-tools, which are very similar to the old k standby mode, but allow overlapping clusters. There is a reasonable introduction (including a small demo) at:

Tutorial on Clustering Algorithms: Fuzzy C-Tools