Вычислить социальную дистанцию между двумя пользователями

Как бы вы написали эффективный алгоритм, который может вернуть социальное "расстояние" между двумя пользователями.

Например, когда вы посещаете профиль в LinkedIn, вы можете видеть, какое расстояние между вами и пользователем.

- > пользователь A является другом с пользователем B - и B является другом с C., когда A посетит C (расстояние будет 1)

Граф огромен, и поэтому мне интересно, как это можно выполнить так быстро.

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

Ответ 1

предполагая, что у вас нет эвристической функции относительно расстояния до цели, наилучшим решением является двунаправленный BFS:
Идея алгоритма: выполнять поиск BFS одновременно из источника и цели: [BFS до глубины 1 в обоих, до глубины 2 в обоих,....].
Алгоритм завершится, когда вы найдете вершину v, которая находится в обоих фронтах BFS.

Поведение алгоритма. Вершина v, которая завершает работу алгоритма, будет точно посередине между источником и целью.
Этот алгоритм даст гораздо лучший результат в большинстве случаев, тогда BFS из источника [объяснение, почему это лучше, чем BFS следует), и обязательно предоставит ответ, если он существует.

почему это лучше, чем BFS из источника? Предположим, что расстояние между источником до цели равно k, а коэффициент ветвления B [каждая вершина имеет B ребра].
BFS откроет: 1 + B + B^2 + ... + B^k вершины.
Двунаправленная BFS откроет: 2 + 2B + 2B^2 + 2B^3 + .. + 2B^(k/2) вершины.

для больших B и k, вторая, очевидно, намного лучше первой.

EDIT: УКАЗАНИЕ, что это решение НЕ требует хранения всего графика в памяти, требуется только реализация функции: successor(v), которая возвращает всех преемников вершины [все вершины, которые вы можете получить, в течение одного шага от v], При этом сохраняются только те узлы, которые вы открываете [2 + 2B + ... + 2B^(k/2), как описано выше]. Для дальнейшего сохранения памяти вы можете использовать Iterative Deepening DFS с одного направления вместо BFS, но он будет потреблять больше времени.

Ответ 2

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

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

Изменить: Изменен алгоритм согласно комментариям.

Ответ 3

Сначала граф должен быть заполнен. Я не могу сказать о том, как вы подключаете граф, возможно, создавая BFS или DFS узлов, обнаруживайте графики и устанавливайте ссылки. Чтобы найти расстояние между двумя лучшими, нужно сделать BFS из источника node и остановиться, когда цель будет найдена. Я думаю, ссылки не имеют веса, если вы не подразумеваете что-то другое.

В этом случае вам нужно применить BFS для поиска расстояния между каждой парой, когда источник node отличается. Кроме того, вы можете реализовать алгоритм Floyd Warshall, чтобы получить все исходные все конечные кратчайшие пути, и поскольку каждая ссылка имеет одинаковый вес, она получит то, что вы хотите. В этом случае после создания структуры для любого источника и места назначения можно найти кратчайшее расстояние. Одна из проблем заключается в том, что сеть всегда меняется, поэтому необходима переработка. Поэтому BFS, я думаю, будет хорошо.

Чтобы быстрее выполнить обработку, вы можете реализовать BFS для параллельной работы. Взгляните на Разработка и анализ недетерминированного алгоритма параллельного алгоритма ширины