友情关系跟踪算法

Question

我正在考虑一个试图证明“六个分离度”一>＆QUOT;理论与一组用户是社交网络的一部分。

我会有这些元素：

1. 我想证明六度理论的几个用户
2. 对于每个用户，我都知道社交网络中的朋友列表

哪个是最好的算法来查看两个用户是否已连接，具有哪种程度并显示连接中的最终步骤？

Answer 1

在社交网络中查找两个人之间的分离程度只是在图表中找到两个点之间的最短路径的特殊情况。最常见的方法是 Dijkstra的算法，但另见最短路径问题。

此外，通过运行全对最短路径算法，您可以找出整个网络的最小，最大和平均分离度数。

Answer 2

一些其他背景材料：

为了解决这个问题，您需要避免网络抓取和其他特定于一个社交网络的特殊技术。相反，您可能希望查看 XHTML Friends Network（XFN），这是一种使用rel的方法= QUOT;＆QUOT;超链接的属性，用于指示该超链接的目标与您之间的关系。还有一个名为 FOAF 的竞争标准，该标准使用 RDF 。

这些微格式已经存在了一段时间，但最近才对它们提供了大量支持。 StackOverflow使用“我”。在您的个人资料页面上的链接中。 WordPress博客在blogroll的编辑界面中提供了一种简单的方法来添加这些标签。许多社交网站在朋友之间的链接中使用这些网站来表示关系。

正因如此，谷歌对此感兴趣，并开始挖掘这些数据。他们有一个社交图谱API ，可以挖掘XFN和FOAF数据以完成某些操作你想做的事情。我建议你从那里开始。关于Google API的优点在于，因为他们正在整个网络中挖掘这些内容，您可以将搜索范围扩展到您想到的特定社交网络之外。