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

Question

Я думаю о приложении, которое попыталось бы доказать шесть степеней разделения & Quot; теория с набором пользователей, которые являются частью социальной сети.

Я хотел бы иметь эти элементы:

<Ол>

Несколько пользователей, для которых я хотел бы доказать теорию шести степеней

Для каждого пользователя я знаю список друзей в социальной сети

Какой лучший алгоритм, чтобы увидеть, связаны ли два пользователя, с какой степенью и показать возможные шаги в соединении?

Answer 1

Определение степени разделения между двумя людьми в социальной сети - это всего лишь частный случай поиска кратчайшего пути между двумя точками на графике. Наиболее распространенным подходом является алгоритм Дейкстры , но см. Также более подробное обсуждение Проблема кратчайшего пути .

Кроме того, запустив алгоритм кратчайшего пути для всех пар, вы можете узнать минимальное, максимальное и среднее количество степеней разделения для всей сети.

Answer 2

Некоторые дополнительные справочные материалы:

Чтобы решить эту проблему в целом, вы должны избегать использования веб-страниц и других специальных методов, специфичных для одной социальной сети. Вместо этого вы, вероятно, захотите заглянуть в XHTML Friends Network (XFN) , которая является способом использования rel = & Quot; & Quot; Атрибут гиперссылки, чтобы указать отношения между целью этой гиперссылки и вами. Существует также конкурирующий стандарт FOAF , в котором используется RDF .

Эти микроформаты существуют уже давно, но их поддержка значительно выросла в последнее время. StackOverflow использует " me " в ссылке на странице вашего профиля. Блоги WordPress обеспечивают простой способ редактирования тегов в интерфейсе редактирования. Многие социальные сайты используют их в ссылках между друзьями, чтобы указать отношения.

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