How to suggest friend lists for facebook user based on mutual friends ?

Question

Hi everyone, I'm building a application to suggest friend lists for facebook user based on his/her mutual friends with each friend. My idea looks like that:

http://i219.photobucket.com/albums/cc213/DoSvn/example03.png

I can get all mutual friends of A with each his/her friend (b1, b2...). It's the intersection between b1, b2... (c1, c2...) I want to separate friends into some groups such as:

b1, b2, b3 in a group; b1, b4 in a group; b5, b6 in a group; b7, b8 in a group

Maybe only the group of b1, b2, b3 is chosen because it's bigger through b1 is also in another group. I tried an idea:

1. Create many group (I tried 200), each group contains some lists of mutual friends (It's "c", I tried 5).
2. With a group, find out the intersection and push it into another list.
3. After step 2, I have a list which contain intersections. I arrange it based on the size of each intersection and get the biggest intersections (I tried 3 and 5).
4. With each intersection chosen, I find out the friend who has mutual friends contain the intersection and push into a group.

It's how I do. But I chose "c" randomly so the result is not exact. Because my elementary friends list is biggest so they always appear in 3 or 4 groups of the result. Do you have any idea ? Thank you :) and sorry for my poor explanation :)

Answer 1

There's a lot of work in graph clustering that may be helpful. You could model each person as a vertex, with an edge between friends (possibly with a weight beased on how "close" they are, e.g., how often they exchange messages). Then partition the set of vertices using graph clustering to get groups. (Ut doesnt have to be a partition, e.g. you could look for subsets of vertices that have high-weight edges between them.)

The hMetis system from U Minn implements many strategies for partitioning graphs.