Расчет чисел "Кевин Бэкон"

Question

Я играл с некоторыми вещами и придумал идею попытаться выяснить Кевин Бэкон числа. У меня есть данные для сайта, что для этого мы можем рассмотреть социальную сеть. Давайте представим, что это Facebook (для упрощения обсуждения). У меня есть люди, и у меня есть список их друзей, поэтому у меня есть связи между ними. Как я могу рассчитать расстояние от одного человека до другого (в основном, число Кевина Бэкона)?

Моя лучшая идея - это Двунаправленный поиск , с ограничением глубины (чтобы ограничить вычислительную сложность и избежать проблем людей, которые просто не могут быть связаны на графике), но я понимаю, что это скорее грубая сила.

Может быть, лучше составить небольшие подграфы (скажем, что-то, эквивалентное группам в Facebook), рассчитать кратчайшие расстояния между ними (возможно, заранее), а затем попытаться использовать ТЕ, чтобы найти ссылку? Хотя для этого требуется предварительный расчет, он может сделать возможным поиск гораздо меньшего количества узлов (узлы могут быть группами, а не отдельными лицами, что делает график намного меньше). Это все равно будет двунаправленный поиск.

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

Может кто-нибудь придумать более простой / быстрый способ сделать это? Мне бы хотелось найти самую короткую длину между двумя людьми, так что это не так просто, как всегда иметь одинаковую конечную точку (например, в задаче Кевина Бэкона).

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

Answer 1

Это стандартная проблема кратчайшего пути . Существует множество решений, в том числе алгоритм Дейкстры и Bellman-Ford . Вам может быть особенно интересно посмотреть на алгоритм A * и посмотреть, как он будет работать с функцией стоимости относительно обратного степени любого конкретного узла. Идея состояла бы в том, чтобы сначала посетить более популярные узлы (с более высокой степенью).

Answer 2

звучит как работа для алгоритм Дейкстры .

ED: Эх, я не должен был нажимать на курок так быстро. Дейкстра (и Беллман-Форд) сводится к поиску в ширину, когда веса равны 1, так что это не слишком полезно. Ну хорошо.

Алгоритм A * , упомянутый tvanfosson, может быть идеальным для этого. Идея состоит в том, что вместо поиска и рекурсии в любом порядке элементов на каждом уровне дерева (с корнями в начальной или конечной точке) вы используете эвристику, чтобы определить, какой элемент вы собираетесь попробовать первым. В вашем случае хорошей ставкой, вероятно, была бы степень узла (количество «друзей»), но вы могли бы хотеть использовать количество людей в пределах некоторого произвольного числа степеней данного человека (то есть парня, который имеет у него есть три друга, у каждого из которых по 100 друзей, вероятно, будет лучшим узлом, чем парень, у которого есть 20 друзей в клике, которая избегает посторонних). Есть множество других вещей, которые вы можете использовать в качестве эвристики (друзья получают 2 балла, друзья друзей получают 1 балл; что угодно, экспериментируйте).

Объедините это с пределом глубины (обрезанным после 6 градусов разделения или любого другого), и вы сможете значительно улучшить свой средний случай (наихудший случай остается тем же, что и базовый BFS).

Answer 3

Это может быть лучше в целом Флойд-Варшалл кратчайшее расстояние всех пар.

Answer 4

выполнить поиск в ширину в обоих направлениях (от каждой конечной точки) и остановиться, когда у вас есть соединение или вы достигли предела глубины