php - 要求社交网络分析（SNA）算法

Question

我收到了制作社交图的任务，其中一个用户位于中心，它显示了他拥有的连接。

但在实现这一目标之前，我们的重点是如何确定2 个用户之间的最短路径。

我找到了一些算法来做到这一点，但它似乎需要很多时间，而且因为它是关于社交链接的，我们正在寻找一个最快的，因为我们需要定期运行它以跟上朋友的更新。

那么，您知道哪种方法是确定两个用户之间最短路径的最快方法吗？

PS：如果你知道 PHP & MySQL 的例子，我会给你一个虚拟啤酒（或可乐）。:D

Answer 1

Dijkstra 算法找到图上两个节点之间的最短路径。

Answer 2

你想要的是一个全对最短路径算法；如果您必须为图形全局生成对，则它比为每一对运行最短路径算法要快。保持更新是另一个问题 - 请注意，每次向图表添加连接时都必须这样做，而不仅仅是每次添加人员时。如果这是用于生产站点，则可能值得将图形生成维护为以比 php 更快的语言编写的离线任务，并将其结果写回数据库。您可能会在那里找到现有的 c++ 实现。

Answer 3

在我看来，如果你要绘制整个图表，最简单的方法是跟踪每个人的路径，因为他们被添加到图表中。所以对于人的朋友来说，路径就是“主要人->朋友”。然后，当您将他们的每个朋友添加到图表时，存储路径“主要人物 -> 朋友 1 -> 朋友 2”等。

如果我脑海中的画面是准确的，那似乎是最简单的方法，但我可能会有些误解。

Answer 4

Dijsktra 的算法在加权图上效果很好。在社交图中，所有边都具有相同的权重。所以 Dijkstra 的算法变成了 BFS。然而，在密集图上，每个级别检查的节点列表将是巨大的。您可以做的一项优化是从两端（A 和 B）开始搜索。