面试难题：朋友的朋友的朋友

Question

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

我研究了图形，但没有找到任何建议可扩展解决此问题的方法。我所能想到的任何方法都需要太多的时间、太多的空间或两者兼而有之。这让我感到非常痛苦！

- user2680535

---

使用广度优先搜索。BFS保证在搜索1度好友之前搜索所有1度好友，搜索2度好友之前搜索所有2度好友，以此类推。当访问每个未发现的朋友时，请将其标记为已发现，并将计数增加一。有一个变量来跟踪搜索的程度。当访问完所有5度好友时停止搜索。 - Jason L

@JasonL- 在一个大型社交网络中，这将探索如此之多的节点，以至于成本会变得非常昂贵。 - templatetypedef

这个问题能否通过一次初始昂贵的全图搜索（也许使用矩阵而不是BFS），然后每当添加或删除连接或用户时，你就会去“我的第k度朋友是我一度朋友的所有(k-1)度朋友的并集”来明智地解决？如果你只想列出适用于他们的最小k的人，这显然意味着在该集合操作之后需要进行一些清理。 - G. Bach

我对这个任务的可行性感到疑惑。假设“六度分隔”并不遥远，这将表明在五度时，您可以获得整个图形的两位数百分比作为您的第五度朋友。您将如何管理每十亿用户的信息量？即使只是为每个用户分配一个数字作为其ID，并使用位向量来存储信息，这也需要超过100 MB的存储空间来存储第五度朋友，从而给我们提供了大约100 PB的信息存储要求，以存储所有10亿用户的第五度朋友。 - G. Bach

@G.Bach 我认为关键是不要计算每个主页的朋友，而只计算当前显示的主页的朋友。 - Patricia Shanahan

我是否已经忘记了关于图算法的一切？BFS 为什么这么慢？对于这样稀疏的图，它的运行时间是 O(n)。更好的是，当我们从当前节点访问一个未访问的节点并且 degreeOfSeparation == 5 时，我们可以停止（与 Jason L 建议的相同，只是我不明白他如何跟踪分离度）。我没有任何确切的数字，但我想象中长度小于等于 5 的路径子图不会超过几百万个。在几百万个节点上进行 BFS 是非常快的...不是吗？我更加困惑的是为什么矩阵方法会更快。 - rliu

Answer 1

一种有趣的方法是将好友图转换成邻接矩阵，然后将其提高到5次方。这样可以得到一个包含每个节点之间长度为5的路径数量的邻接矩阵。

请注意，你需要一种能够利用稀疏矩阵的矩阵乘法算法，因为好友邻接矩阵在前几个级别上很可能是稀疏的。幸运的是，人们已经在如何高效地乘大矩阵（特别是稀疏矩阵）方面做了很多工作。

以下是Twitter的Oscar Boykin在视频中提到的一种计算关注者的关注者的方法。： video

- Craig Gidney

---

这会不会重复计算朋友的朋友？假设A有朋友B和C，他们都是D的朋友。A有两个朋友，但只有一个朋友的朋友。 - Patricia Shanahan

啊，为了避免这个问题，在每次矩阵乘法后，你需要将所有非零的矩阵元素缩减为1。 - Craig Gidney

我认为对此的任何合理方法都必须假设一个超稀疏图。我不喜欢的唯一一件事是它会一口气完成整个计算。当需要显示主页时，可以按需运行BFS。 - Patricia Shanahan

你是如何得出 O(n^3) 的？即使是一个朴素的 BFS 最多也不应该需要超过 O(E) = O(n^2)。将其与 Strassen 的 O(n^2.8) 和 Coppersmith-Winograd 的 O(n^2.38) 进行比较。 - collapsar

@Strilanc 你可以在一次BFS遍历中完成所有层级。 - G. Bach

Answer 2

我认为问题实际上归结为如何对10亿用户进行哈希/跟踪，因为我们需要计算每一层的好友数量。（请注意，我们只需要计数，不需要存储）

如果我们假设对于每个人，他们的朋友以及他们的朋友的朋友都非常少（比如小于1000和小于100,000），那么在数据库表中存储这些信息似乎是可行的。整个数据库只需要两次可管理的遍历，然后在创建“新”关系时直接添加到表中。

如果我们在用户表中存储了第一和第二度朋友，我们可以利用它们扩展到需要的范围-

例如：要计算第三度朋友，我们需要哈希和跟踪所有二度朋友的一度朋友。(对于第四度，你要做所有二度的二度朋友，对于更高的程度，你需要创建第四度，然后适当地扩展到第五或第六度)。

因此，在那一点上(第五和第六度的朋友)，您开始接近需要跟踪、哈希和计数的10亿人数。

我在考虑问题的本质是，当你“计算”更高层次关系中的朋友时，如何以最有效的方式拥有10亿条记录ID。

我不知道该如何做到这一点，有什么想法吗？

- tom stratton