Я думаю о приложении, которое попытается доказать теорию "Шести степеней разделения". с набором пользователей, которые являются частью социальной сети.
У меня были бы эти элементы:
Каков наилучший алгоритм, чтобы увидеть, связаны ли два пользователя, с какой степенью и показать возможные шаги в соединении?
Нахождение степени разделения между двумя людьми в социальной сети — это всего лишь частный случай нахождения кратчайшего пути между двумя точками на графе. Наиболее распространенным подходом является алгоритм Дейкстры, но см. также более подробное обсуждение Проблема с кратчайшим путем.
Кроме того, запустив алгоритм кратчайшего пути All-pairs, можно было узнать минимальное, максимальное и среднее количество степеней разделения для всей сети.
Некоторые дополнительные справочные материалы:
Чтобы решить эту проблему в целом, вам следует избегать парсинга веб-страниц и других специальных методов, характерных для одной социальной сети. Вместо этого вы, вероятно, захотите заглянуть в Сеть друзей XHTML (XFN), которая является способом использования rel Атрибут ="" гиперссылки для указания отношения между целью этой гиперссылки и вами. Существует также конкурирующий стандарт под названием FOAF, в котором используется RDF.
Эти микроформаты существуют уже некоторое время, но совсем недавно их поддержка значительно возросла. StackOverflow использует «я» в ссылке на странице вашего профиля. Блоги WordPress предоставляют простой способ добавления этих тегов в интерфейс редактирования списка блогов. Многие социальные сайты используют их в ссылках между друзьями для обозначения отношений.
Из-за этого Google заинтересовался этим и начал добывать эти данные. У них есть API Social Graph, который может собирать данные как XFN, так и FOAF, чтобы выполнять определенные действия. вещи, которые вы хотите сделать. Я предлагаю вам начать там. Хорошая вещь в Google API заключается в том, что, поскольку они исследуют это по всему Интернету, вы можете расширить свой поиск за пределы конкретной социальной сети, которую вы имели в виду.
