6

我有一个 6 度的 Kevin Bacon 类型问题。假设我有 2 个 twitter 用户，我想通过朋友（我用朋友来表示你关注某人而不是他们关注你）和 Twitter 中的关注者来弄清楚他们之间的关系。我的数据库中有所有的 id。

例如：

乔尔和莎莉

乔尔跟随弗雷德，后者是跟随莎莉的史蒂夫的朋友。

可能有多种方法可以到达那里，但我想要最短的。

这似乎是一个众所周知的计算机科学问题（最短路径算法）。

今天我有一个名为“影响者”的表，其中存储了我所有的 twitter id，然后我有一个 follows 表，它是一个自引用表（一侧是关注者的 ID，另一侧是朋友的 ID。）

这是图论吗？如果是这样，有人可以向我指出任何有用的实用程序/库/方法。我使用 ruby​​，但可以解析大多数语言。

4

2 回答 2

1

正如您所说，这是一个众所周知的问题，您可以在Wikipedia中看到。

请注意，在您的情况下，所有边的权重都等于 1)，所以我认为 Djikstra 的算法对您不会很有用。

为了找到最小距离，我建议使用广度优先搜索。问题是 Twitter 网络可能是高度连接的，因此您可能会出现组合爆炸（想象每个人都连接到其他 20 个人 - 在第一级，您将访问 20 个个人资料，而在下一个您将访问 400 个，并且在接下来的 8000 中 - 如果你没有快速找到 Sally，你很快就会耗尽内存）。

还有一个线性规划公式，我不是 100% 熟悉。这些笔记很适合线性规划，但不适用于最短路径问题，而这些笔记似乎更侧重于应用程序。

网上有一个关于这个问题的视频讲座，看起来很完整。

我希望这些参考资料有所帮助。

于 2012-06-05T12:23:29.293 回答
1

这听起来像你需要 BFS http://en.wikipedia.org/wiki/Breadth-first_search

在线方法： 我认为它可能会很昂贵，具体取决于您要如何使用它。在最坏的情况下，您将迭代数据库中的所有数据：成本运行时O(n)（假设您有一个查找函数可以在运行时在图中找到用户O(1)）。

离线方法 您可以进行离线预定预计算并将距离存储为查找函数，但它需要一些额外的内存O(n*n)，其中 n 是用户数。查找功能的成本现在只是O(1)或O(logn)取决于您如何实现它 （忽略我认为将在该区域内的离线运行O(n)时O(n*n)）。

策略 您要遵循的策略可能取决于您可以预期的用户数量上限以及用户之间的连接程度。如果您的用户很少，在线方法可能会很好，如果您有数百万用户，那么您可能需要离线方法，但这会花费您一些内存。

其他注意事项

  • 线上线下相结合
  • 使用缓存策略
  • 每当为用户更新新参考时，更新距离查找函数

更新的答案有 17 个 mio。用户，我们将需要离线方法。

我会关注离线版本。您应该避免O(n*n)我认为可能的运行时。

数据库模型

您应该考虑如何对数据库进行建模，因为这将是此实现中最昂贵的部分。

可能是这样的：为每个用户创建一个表（表名可以是 userId）。每个表都有每个用户的条目（记录键是 userId）。这将导致 17 mio。有 17 米奥的桌子。每个条目（这是O(n*n)成本）。

离线运行一次 BFS，同时跟踪您访问过的用户以及您在 BFS 迭代中处于哪个级别，并保存与数据库的距离。我还没有考虑过这部分，但我认为这个策略是可行的。请记住在每个节点上运行 BFS，即，直到您访问了所有用户。如果此策略不可行，那么您可以从运行时的每个节点运行 BFS O(n*n)。这意味着在最坏的情况下运行可能需要一个月的时间，即您的距离数据可能是旧的。运行速度取决于您的用户的连接程度。

或者，如果可能，您可以采用“每当为用户更新新参考时，更新距离查找功能”的方法。这将运行一次 BFS O(n)，即几秒钟。在第一次事件时调用 BFS(userId)，然后在参考更新时调用。

在线您使用 userId 按表名获取表，并通过另一个 userId 获取条目以获取距离。

于 2012-06-05T12:38:36.790 回答