友谊关系跟踪算法

在一个社会网络中,找到两个人之间的分离程度,只是在图中找到两点之间最短路径的一个特例。最常见的方法是 Dijkstra's algorithm ,但另请参见 Shortest path problem .

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

一些附加背景材料:

为了一般地解决这个问题,您需要避免Web抓取和其他特定于一个社交网络的特殊技术。相反,你可能想调查一下 XHTML Friends Network (XFN) 这是一种使用超链接的rel=“”属性来指示该超链接的目标与您之间的关系的方法。还有一个相互竞争的标准叫做 FOAF 其中使用 RDF .

这些 microformats 已经存在一段时间了,但是最近对他们的支持增加了很多。StackOverflow在配置文件页面的链接中使用“我”。WordPress博客为blogroll添加这些标签提供了一种简单的编辑界面。许多社交网站在朋友之间的链接中使用这些来表示关系。

正因为如此,谷歌对这一点产生了兴趣,并开始挖掘这些数据。他们有一个 Social Graph API 这可以同时挖掘XFN和FOAF数据,以执行您想要执行的某些操作。我建议你从那里开始。谷歌的API的好处在于,由于它们在网络上到处挖掘这些信息,你可以将搜索范围扩大到你心目中特定的社交网络之外。