Использование Python поиска в ширину в социальной сети - PullRequest
Новая
       23

Использование Python поиска в ширину в социальной сети

2 голосов
/ 20 декабря 2010

Я читал много вопросов о стековом потоке о том, как использовать поиск в ширину, dfs, A * и т. Д., Вопрос в том, что является оптимальным использованием и как его реализовать в графах, смоделированных в реальности.Например,

Учитывая, что у вас есть социальный график в Twitter / Facebook / на каком-либо сайте социальной сети, мне кажется, что алгоритм поиска будет работать следующим образом:

Если у пользователя А было 10 друзей, то одиниз них было 2 друга и еще 3. Поиск сначала определил, кто были друзья пользователя А, а затем должен был бы найти, кто из друзей был у каждого из десяти пользователей.Мне кажется, что это похоже на bfs?

Однако я не уверен, что это способ реализации алгоритма.

Спасибо,

Ответы [ 2 ]

0 голосов
/ 13 июня 2011

У меня есть около 300 друзей в Facebook, и у некоторых из моих друзей в среднем также есть 300 друзей. Если ты собираешься построить из этого график, он будет огромным. Поправь меня, если я не прав? , В этом сценарии BFS будет требовать много лота?

Спасибо J

0 голосов
/ 06 июня 2011

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

Я просто пытаюсь пройти весь график

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

С учетом вышесказанного, Facebook и Twitter очень разные графические структуры, которые влияют на то, как вы их проходите:

  1. Facebook - это принципиально неориентированный граф. Если X дружит с Y, Y ДОЛЖЕН дружить с X. (Или в отношениях с, или связанных с, и т. Д.).

  2. Twitter - это принципиально ориентированный граф. Если вы X следует Y, Y не обязательно следует X.

Эти проблемы будут существенно влиять на алгоритм обхода графа. Если честно, если вы просто хотите посетить все узлы, нужен ли вам график? Почему бы просто не повторить их все? Если у вас есть все узлы в некоторой структуре данных MY_DATA, которая является итеративной, вы можете просто получить выражение генератора, например: 

def nodeGenerator(MY_DATA)
    for node in MY_DATA:
        yield node

Понятно, что вам нужно настроить внутренние компоненты nodeGenerator, чтобы справиться с тем, как вы фактически получаете доступ к узлам. При этом большинство структур графов реализует итератор узла. Тогда вы можете просто создать итератор в любое время, когда захотите, с помощью: 

 for node in nodeGenerator(MY_DATA):
     (Do something here)

Возможно, я просто упускаю суть вопроса здесь, но в настоящее время вы задали вопрос об алгоритмах поиска без проблемы поиска. Из-за характера оптимизации и поиска No Free Lunch ценность любого алгоритма поиска будет полностью зависеть от проблемы поиска, которую вы пытаетесь исследовать.

Это верно даже для одного и того же набора данных. В конце концов, если бы вы искали всех, чье имя начинается с буквы D, отличный способ - просто отсортировать всех по алфавиту и выполнить бинарный поиск. Если вместо этого вы пытаетесь найти степень отделения каждого от Кевина Бэкона, вам понадобится алгоритм, который начинается с мистера Бэкона и рекурсивно перебирает всех, кто его знает, и всех, кого они знают. Это обе вещи, которые вы МОЖЕТЕ сделать в Facebook или Twitter, но без каких-либо подробностей на самом деле нет способа рекомендовать алгоритм. Следовательно, если вы ничего не знаете, просто переберите всех в виде списка. Это так же хорошо, как и все остальное. Если вы хотите оптимизировать, кэшируйте любые вычисления.

...