实现LinkedIn的有效方式,如"你如何连接"功能？

Question

LinkedIn有这个很酷的功能,在访问某些用户的个人资料时,LinkedIn会提示你如何通过网络连接到该用户.

假设访问者和配置文件所有者是图的两个节点,其中节点表示用户,边表示友谊,一个简单的解决方案可以是从两个节点开始直到某个级别的bfs并查看是否存在任何交叉点.交叉点将是网络链路节点.

虽然这听起来很整洁,但问题在于,为了确定每个人的朋友,需要单独的数据库查询.当网络深度超过2级时,算法将是非常耗时的.有更好的有效替代方案吗？如果没有,我们如何才能增加更好的硬件支持(并行计算,网格,分布式数据库等)以减少计算所需的时间？

Answer 1

您可以在数据库中的图形文章中看到如何做到这一点:SQL与 Lorenzo Alberton的社交网络相遇.示例代码是使用CTE为PostgreSQL编写的.但是,我怀疑使用RDBMS会很好.我写了一篇关于如何使用本机图形数据库执行相同内容的文章,在这种情况下Neo4j:数据库中的社交网络:使用图形数据库.除了性能上的差异之外,图形数据库还通过提供图形API来简化任务,该图形API使得在SQL中(或通过使用存储过程)编写极其复​​杂的遍历变得容易.我在这个帖子中写了一些关于图形数据库的内容,并且也看到了这个.