Запрашивать алгоритм анализа социальной сети (SNA)

Question

Я получил задание сделать social graph, где с одним пользователем в center он показывает соединения, которые у него есть.

Но прежде чем мы сможем достичь этого, мы сосредоточимся на том, как мы можем определить shortest path между двумя пользователями.

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

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

PS: Если вы знаете пример в PHP & MySQL, я дам вам виртуальное пиво (или кокс). : D

Answer 1

Dijkstra's Algorithm находит кратчайший путь между двумя узлами на графике.

Answer 2

Мне кажется, что если вы все равно нарисуете весь график, самым простым было бы отслеживать пути каждого человека, поскольку они добавляются в график. Поэтому для друзей человека путь - это просто «главный человек -> друг». Затем, когда вы добавите каждого из своих друзей на график, сохраните путь «главный человек -> друг 1 -> друг 2» и т. Д.

Если картина в моем уме точна, это кажется самым простым способом сделайте это, но я, возможно, немного недопонимаю.

Answer 3

что вы хотите - это алгоритм all-pairs shortest path; если вам нужно генерировать пары глобально для графика, это быстрее, чем запуск алгоритма кратчайшего пути для каждой пары. сохранение этого обновления - еще одна проблема - обратите внимание, что вам придется делать это каждый раз, когда вы добавляете соединение с графиком, а не только каждый раз, когда вы добавляете человека. если это для производственного сайта, возможно, стоит сохранить генерацию графика как автономную задачу, написанную на языке быстрее, чем php, и записать ее результаты обратно в db. вы, вероятно, найдете существующие реализации C++.

Answer 4

Алгоритм Дийсктры хорошо работает на взвешенных графиках. В социальном графе все ребра имеют одинаковый вес. Таким образом, алгоритм Дейкстры становится BFS. Однако на плотном графе список узлов, рассмотренных на каждом уровне, будет огромным. Одна из оптимизаций, которую вы можете сделать, - начать поиск с обоих концов (A и B).