algorithm - 友谊关系追踪算法

Question

我正在考虑一个应用程序，它试图用一组属于社交网络的用户来证明“六度分离”理论。

我会有这些元素：

哪个是查看两个用户是否连接、连接程度以及显示连接中最终步骤的最佳算法？

score 4 · Accepted Answer

求社交网络中两个人之间的分离程度只是求图中两点之间最短路径的一个特例。最常见的方法是Dijkstra 算法，但另请参阅对最短路径问题的更长讨论。

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

score 3 · Accepted Answer

一些额外的背景材料：

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

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

正因为如此，谷歌对此产生了兴趣，并开始挖掘这些数据。他们有一个社交图谱 API，可以挖掘 XFN 和 FOAF 数据来做一些你想做的事情。我建议你从那里开始。谷歌 API 的好处是因为他们在整个网络上挖掘这个，你可以扩大你的搜索范围，超出你所想的特定社交网络。

2 回答 2