假设您有一个拥有十亿用户的社交网络。在每个用户的页面上，您要显示该用户的朋友、朋友的朋友等的数量，最多五度。友谊是相互的。计数不需要立即更新，但它们应该是准确的。
我阅读了图表，但没有找到任何建议解决此问题的可扩展方法。我能想到的任何事情都会占用太多时间、太多空间，或者两者兼而有之。这让我发疯！
问问题
1463 次
2 回答
4
一种有趣的方法是将朋友图转换为邻接矩阵，然后将矩阵提高到 5 次方。这为您提供了一个邻接矩阵，其中包含每个节点之间长度为 5 的路径数的计数。
请注意，您需要一个可以利用稀疏矩阵的矩阵乘法算法，因为朋友邻接矩阵对于前几个级别可能是稀疏的。幸运的是，人们在如何有效地乘以巨大的矩阵（尤其是稀疏矩阵）方面做了大量工作。
这是一段视频，Twitter 的 Oscar Boykin 提到了这种计算 Twitter 追随者追随者的方法。
于 2013-08-14T01:46:12.947 回答
0
在我看来，问题真的归结为我们如何散列/跟踪 10 亿用户，因为我们正在计算每个级别的朋友。（请注意，我们只需要计算它们，而不是存储它们）
如果我们假设对于每个人，他们的朋友和他们朋友的朋友的顺序非常小（例如 <1000 和 <100,000），将这些存储在每个用户的数据库表中似乎是可行的。它只需要对整个数据库进行两次可管理的传递，然后在创建“新”关系时直接添加到表中。
如果我们将 1 级和 2 级朋友存储在用户表中，我们可以利用它们来扩展我们需要的范围 -
EG：要计算 3 级朋友，我们需要散列和跟踪所有 2 级朋友的 1 级朋友。（对于第 4 度，您执行所有第 2 秒，对于更高的度，您创建第 4 度，然后适当地扩展到第 5 或第 6 度）。
因此，到那时（5 度和 6 度的朋友），您开始接近 10 亿作为您需要跟踪、散列和计数的人数。
我认为问题就变成了，当您“计算”高阶关系中的朋友时，拥有 10 亿个记录 ID 的最有效方法是什么。
你是怎么做到的，我不知道——有什么想法吗？
于 2013-08-25T16:55:06.197 回答