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

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

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

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

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

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