查找两个Twitter用户关系的算法

Question

我有一个6度的Kevin Bacon型问题.假设我有两个推特用户,我想通过朋友找出他们之间的关系(我用朋友来表示当你跟随某人跟他们跟随你时)和推特中的粉丝.我的数据库中有所有id.

例如:

乔尔和莎莉

乔尔跟随弗雷德,他是史蒂夫跟萨莉的朋友.

可能有多种方法可以达到目标,但我希望最短.

这似乎是一个众所周知的计算机科学问题(最短路径算法).

今天我有一个叫做"影响者"的桌子,我的所有twitter id都存储在那里,然后我有一张自助参考表(一方是粉丝,另一方是朋友).

这个图论也是如此？如果是这样,有人可以指向任何可能有用的实用程序/库/方法.我使用ruby,但可以解析大多数语言.

Answer 1

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

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

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

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

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

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