algorithm - 采访树桩 : friends of friends of friends

Question

假设您有一个拥有十亿用户的社交网络。在每个用户的页面上，您想要显示该用户的 friend 数、 friend 的 friend 等等，最多五度。友谊是相互的。计数不需要立即更新，但它们应该是精确的。

我仔细阅读了图表，但没有发现任何建议可以解决此问题的可扩展方法。我能想到的任何事情都会占用太多时间，太多空间，或两者兼而有之。这让我抓狂!

Answer 1

一种有趣的方法是将 friend 图转换为邻接矩阵，然后将该矩阵提高到 5 次方。这为您提供了一个邻接矩阵，其中包含每个节点之间长度为 5 的路径数的计数。

请注意，您需要一个可以利用稀疏矩阵的矩阵乘法算法，因为 friend 邻接矩阵在前几个级别可能是稀疏的。幸运的是，人们已经在如何有效地乘以巨大的矩阵(尤其是稀疏矩阵)方面做了大量工作。

这是一个 video where Twitter's Oscar Boykin mentions this approach用于计算 Twitter 上关注者的关注者。