What is a good overlapping groups algorithm?

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 into开发者_开发知识库 my high school friends, my college friends, my family and my work friends.

The algorithm I used above (JUNG's VoltageClusterer) separates nodes into single clusters. But I want an algorithm that can assign nodes multiple clusters (e.g. a friend of mine can be both my high school friend and college friend).

How do I do this? It would be nice if I can have this algorithm work for weighted graphs too instead of just unweighted ones.

---

Palla et al have a nice Nature paper on detecting overlapping communities: http://www.nature.com/nature/journal/v435/n7043/full/nature03607.html They demonstrate its success in different types of networks, from social to protein interaction.

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

---

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

Any other papers/approaches would be helpful.

---

You might try fuzzy c-means, which is much like the old standby, k-means, but permits overlapping clusters. There is a reasonable introduction (including a small demonstration) at:

A Tutorial on Clustering Algorithms: Fuzzy c-Means