algorithm - 小世界理论的实现——就像在 XING 中一样

Question

有些人可能不知道 XING 是什么:它是一个类似于 linkedIn 等的在线网络社区。您可以添加新联系人、管理这些联系人、搜索新联系人等。

整个应用程序是用 Ruby 完成的，并且在某种程度上受到了小世界理论的启发，至少是这样说的。

有一个具体功能，我真的无法想象它是如何完成的。如果您搜索某个不在您的联系人列表中的人 Z，然后单击 Z 的个人资料，则会显示从您到 Z 的所有可能联系。示例:

• 你 -> B -> C -> E -> Z
• 你 -> M -> N -> I -> Z
• 你 -> M -> K -> J -> Z

等等

特别是如果您有很多联系人，那么也有很多可能的联系。而且应用速度很快!

那么，我的问题是:这样的功能是如何实现的？它背后有什么样的系统/数据库？我只对像 mySQL 和 MSSQL 服务器这样的标准 RDMBS 有经验，我真的无法想象如何在标准数据库系统中做上面提到的事情。

是否有任何算法可以帮助计算可能的关系？目前我正在阅读一本关于算法的有趣书籍，例如计算两个事物的相似性等。因此“小世界理论的实现”对我来说会非常有趣。

提前感谢您的任何提示。

Answer 1

这可能是预缓存您可能点击的人以及各种最小生成树算法的某种组合。例如，您可能会查看 Kruskal 算法 ( http://en.wikipedia.org/wiki/Kruskal%27s_algorithm )。它没有您所描述的行为，但对于加权树很有用，您对两个人之间的联系强度有一些了解。

有关更多一般信息，请查看有关生成树的信息: http://en.wikipedia.org/wiki/Minimum_spanning_tree

更一般地说，阅读 Goodrich 和 Tomassia 的“Java 中的数据结构和算法”的第 13 章(关于图表)。