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

Question

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

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

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

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

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

Answer 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), которая возвращает всех преемников вершины [все вершины, к которым вы можете добраться, в пределах 1 шага от v] , При этом должны храниться только те узлы, которые вы открываете [2 + 2B + ... + 2B^(k/2), как описано выше]. Для дальнейшего сохранения памяти вы можете использовать Итеративное углубление DFS в одном направлении вместо BFS, но это займет больше времени.

Answer 2

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

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

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

Answer 3

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

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

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