facebook - 最大可能的共同 friend 群体？

Question

我试图找出理论上能够相处的尽可能多的 friend 群体，即群体中的每个人都应该至少认识群体中其他人的 50%。

我正在尝试为此提出一种算法，该算法不会花费太长的时间； Facebook 的 API/跨服务器对话速度相当慢。

我想可以先从和我共同好友最多的 friend 开始，然后再一一加人。但接下来我会选择谁？

只对理论感兴趣，不需要代码。

<小时/>

编辑:当我说“理论”时，我真正的意思是用简单的英语来说下一个逻辑步骤是什么:)我希望我能在一个下午编写这个代码，但我想这是比我预期的要复杂一些，而且我不确定我是否愿意花几周时间深入研究图论。尽管如此，也许其他人会觉得这很有趣。

Answer 1

MIT不久前做了一些关于社交图表的工作。尽管它使用了手机数据，但聚类算法和其他系统应该仍然适用，即使它们是使用不同的输入和标准构建的。

有more MIT chatter关于目前正在进行的社交图表。绝对是寻找此类事情的技术指导的地方。

虽然对于大多数有用的问题来说，从给定节点到其边缘的图枚举问题是 NP 完全的……图遍历的应用和丰富的信息可能会帮助您提高效率:

1. 对于任何节点(配置文件)N，您可以使用 Google 或其他工具进行数据抓取，以找到相关的边。这意味着您可以利用页面缓存和 Google 搜索技术来减少自己遍历边缘的情况。

2. 社交资料包含大量元数据。开发一种统计分析方法来计算 A 在没有直接路径的情况下了解 B 的可能性可能会很有用。毕竟 friend 们 a) 相似的地点 b) 相似的兴趣

3. 其他看似无关的数据可以提供一种方法来定位可能彼此认识的人，然后您可以仔细检查边缘。比如在论坛上谈论乐队或演出，或者当凯特打玛丽的嘴时人们提到“猫打架”。

只需以正确的方式查看数据，就像麻省理工学院通过电话查看地理统计数据来确定关系一样。

祝你好运