寻找两个Twitter用户之间关联的算法

Question

寻找两个Twitter用户之间关联的算法

algorithmtwitterrelationship

6

我有一个“六度分离”类似的问题。假设我有两个 Twitter 用户，我想通过在 Twitter 上的好友（我使用好友来表示当您关注某人时与他们相互关注）和粉丝之间找出他们彼此之间的关系。我已经在我的数据库中拥有所有的 id。

例如：

Joel 和 Sally

Joel 关注 Fred，Fred 是 Steve 的好友，Steve 关注 Sally。

可能有多种方法可以实现，但是我想要最短路径。

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

今天我有一个名为“influencers”的表，其中存储了所有我的 Twitter id，然后我有一个自引用表格“followings”（一方是粉丝的 id，另一方是朋友的 id）。

那么这是否属于图论？如果是，则有人可以指向任何有用的实用程序/库/方法。我使用 Ruby，但可以解析大多数编程语言。

- Joelio

2个回答

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)范围内）。

策略你想要遵循的策略取决于你所期望的用户数量上限以及用户之间的连接程度。如果你只有少量用户，在线方法可能就可以，但如果你有数百万用户，则可能需要离线方法，但这将耗费一些内存。

其他考虑事项

混合在线和离线方法
使用缓存策略
每当更新用户的新参考时，请更新距离查找功能

更新的答案 有1700万用户，我们需要采用离线方法。

我会选择离线版本。你应该避免O(n*n)运行时间，我认为这是可能的。

数据库模型

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

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

离线，您可以在运行BFS时跟踪已访问的用户和BFS迭代中的级别，并将距离保存到数据库中。我还没有完全考虑清楚这部分，但我认为这种策略是可行的。记得对每个节点运行BFS，即直到您访问了所有用户。

如果此策略不可行，则可以从每个节点运行BFS，其运行时间为O(n*n)。这意味着在最坏情况下可能需要一个月才能运行，即您的距离数据可能过时。运行速度取决于您的用户连接程度。

或者，如果可能的话，您可以采用“每当更新用户的新引用时，请更新距离查找函数”的方法。这将运行一次BFS，其运行时间为O(n)，即几秒钟。在第一次事件上调用BFS(userId)，之后在引用更新时调用。

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

- Kunukn

当你拥有一百万个用户时，O(n*n) 明显太慢了。 - maniek

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rlinden · Accepted Answer

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

请注意，在您的情况下，所有边缘的权重都等于1，因此我认为Djikstra算法对您来说并不是非常有用。

为了找到最小距离，我建议使用广度优先搜索。问题在于Twitter网络可能极其连接，因此您可能会遇到组合爆炸（想象一下每个人都与其他20个人相连 - 在第一层中，您将访问20个个人资料，而在下一层中，您将访问400个人，再下一层则是8000个人 - 如果您不能快速找到Sally，您很快就会耗尽内存）。

还有一种线性规划的表述方式，我不是100%熟悉。这些笔记对线性规划很好，但对最短路径问题不太适用，而这些则更专注于应用。

有一个在线视频讲座可以解决这个问题，看起来非常完整。

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