Алгоритм отслеживания отношений дружбы

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 использует «me» в ссылке на странице вашего профиля. Блоги WordPress предоставляют простой способ в интерфейсе редактирования для blogroll для добавления этих тегов. Многие социальные сайты используют их в ссылках между друзьями, чтобы указать на отношения.

Из-за этого Google заинтересовался этим и начинает добывать эти данные. У них есть Social Graph API, которые могут обрабатывать как данные XFN, так и данные FOAF, чтобы сделать именно то, что вы хотите сделать. Я предлагаю вам начать там. Самое приятное в API Google - это то, что они разрабатывают эту программу в Интернете, вы можете расширить свой поиск за пределами конкретной социальной сети, о которой вы говорили.