algorithm - 如何根据共同好友为 facebook 用户推荐好友列表？

Question

我正在构建一个应用程序，根据他/她与每个 friend 的共同 friend 为 facebook 用户推荐 friend 列表。我的想法是这样的:

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

我可以得到 A 和他/她的每个 friend (b1, b2...) 的所有共同 friend 。它是 b1, b2... (c1, c2...) 之间的交集 我想将 friend 分成一些组例如:

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

可能只选择了 b1、b2、b3 组，因为它更大，因为 b1 也在另一个组中。我尝试了一个想法:

1. 创建很多组(我试过 200 个)，每个组包含一些共同好友列表(它是“c”，我试过 5 个)。
2. 与一组人一起，找出交叉点并将其插入另一个列表。
3. 在第 2 步之后，我有一个包含交叉点的列表。我根据每个路口的大小排列它并获得最大的路口(我尝试了 3 和 5)。
4. 选择每个交叉点后，我找出有共同 friend 的 friend 包含该交叉点并插入一个组。

我就是这样。但我随机选择了“c”，所以结果不准确。因为我的初级好友列表最大所以他们总是出现在结果的 3 或 4 组中。你有什么主意吗 ？谢谢 :) 抱歉我的解释不当 :)

Answer 1

图聚类方面有很多工作可能会有所帮助。您可以将每个人建模为一个顶点，在 friend 之间建立一条边(权重可能取决于他们的“亲密程度”，例如，他们交换消息的频率)。然后使用图形聚类对顶点集进行分区以获得组。 (Ut 不必是一个分区，例如，您可以查找在它们之间具有高权重边的顶点子集。)

hMetis U Minn 的系统实现了许多图划分策略。