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

Question

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

У меня были бы эти элементы:

1. Несколько пользователей, для которых я хотел бы доказать теорию шести степеней
2. Для каждого пользователя я знаю список друзей в социальной сети

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

Answer 1

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

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

Answer 2

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

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

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

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