友誼關係跟蹤算法

Question

我在想一個應用程序，它會試圖證明了一組是一個社交網絡的一部分用戶的「Six degrees of separation」理論。

我會有這些元素：

1. 一對夫婦，我想爲其證明六度理論
2. 對於每個用戶的用戶，我知道朋友的社交網絡
列表

這是看如果兩個用戶連接，與學歷，並顯示在連接的最終步驟的最好的算法？

Answer 1

找到社交網絡的兩個人之間的分離度處於圖中尋找兩點間的最短路徑的一個特例。最常見的方法是Dijkstra's algorithm，但也見Shortest path problem較長的討論。

此外，通過運行全配對最短路徑算法，您可以找出整個網絡的最小值，最大值和平均分離度數。

Answer 2

一些額外的背景材料：

一般解決這個問題，你想避免網頁抓取等特設技術所特有的一個社交網絡。相反，你可能會想看看XHTML Friends Network (XFN)這是使用rel =「辦法」的超鏈接的屬性，並指示超鏈接和你的目標之間的關係。還有一個稱爲FOAF的競爭標準，其使用RDF。

這些microformats已經有一段時間了，但對他們的支持已經成長了很多剛剛結束。 StackOverflow在您的個人資料頁面的鏈接中使用「我」。 WordPress博客爲blogroll的編輯界面提供了一種簡單的方法來添加這些標籤。許多社交網站在朋友之間的鏈接中使用這些來指示關係。

正因爲如此，谷歌已經了興趣，這一點，並開始挖掘這個數據。他們有一個Social Graph API可以挖掘XFN和FOAF數據來完成你想要做的一些事情。我建議你從那裏開始。有關谷歌的API的好處是因爲它們挖掘這一切都在網上，你可以拓寬你的搜索超出你腦子裏的特定的社會網絡。