database - 实现 LinkedIn like "How you are connected to"功能的有效方法？

Question

LinkedIn 有一项很酷的功能，在访问某些用户的个人资料时，LinkedIn 会提示您如何通过网络连接到该用户。

假设访问者和个人资料所有者是图中的两个节点，其中节点代表用户，边缘代表友谊，一个简单的解决方案可以是从两个节点开始到一定级别的 bfs，看看是否有任何交集.交叉点将是网络链接节点。

虽然这听起来不错，但问题是为了确定每个人的 friend ，需要单独的数据库查询。当网络深度超过 2 层时，这将是非常耗时的算法。有没有更有效的选择？如果不是，我们如何添加更好的硬件支持(并行计算、网格、分布式数据库等)以减少计算所需的时间？

Answer 1

您可以在文章 Graphs in the database: SQL meets social networks 中了解如何完成此操作洛伦佐·艾伯顿。示例代码是使用 CTE 为 PostgreSQL 编写的。但是，我怀疑使用 RDBMS因为这将表现良好。我写了一篇关于如何使用 native 图形数据库执行与上述文章相同的操作的文章，在本例中为 Neo4j : Social networks in the database: using a graph database .除了性能上的差异之外，图形数据库还通过提供图形 API 简化了任务，该 API 可以轻松处理用 SQL 编写(或使用存储过程)极其复杂的遍历。我在 this thread 中写了更多关于图形数据库的文章并查看 this one也是。