Я играл с некоторыми вещами и придумал идею попытаться выяснить Kevin Bacon. У меня есть данные для сайта, для которого мы можем рассматривать социальную сеть. Пусть притворяется, что это Facebook (для упрощения обсуждения). У меня есть люди, и у меня есть список их друзей, поэтому у меня есть связи между ними. Как я могу рассчитать расстояние от одного человека к другому (в основном, номер Кевина Бэкона)?
Моя лучшая идея - Двунаправленный поиск с ограничением глубины (чтобы ограничить вычислительную сложность и избежать проблемы людей, которые просто могут" t подключен на графике), но я понимаю, что это довольно грубая сила.
Может быть, лучше сделать небольшие субграфы (скажем, что-то, что эквивалентно группам на Facebook), рассчитать кратчайшие расстояния между ними (возможно, раньше времени), а затем попытаться использовать THOSE, чтобы найти ссылку? В то время как для этого требуется предварительный расчет, он может обеспечить поиск по нескольким узлам (узлы могут быть группами вместо отдельных лиц, что делает график намного меньшим). Это все равно будет двунаправленный поиск.
Я мог бы также предварительно вычислить количество людей, к которым подключено отдельное лицо, сначала поиск узлов для "популярных" людей, так как они могли бы наилучшим образом подключиться к данному получателю. Я понимаю, что это будет компромисс скорости для возможного кратчайшего пути. Я бы подумал, что также хочу использовать поиск по глубине вместо поиска ширины в первый раз, который я планировал использовать в других случаях.
Может кто-нибудь подумать о более простом/более быстром способе сделать это? Я бы хотел найти самую короткую длину между двумя людьми, поэтому это не так просто, как всегда, с той же конечной точкой (например, в проблеме Кевина Бэкона).
Я понимаю, что есть такие проблемы, как я мог бы получить цепочки из 200 человек и т.д., но это может быть решено, что у меня есть предел для глубины, которую я хочу искать.
