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

Question

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

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

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

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

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

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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

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