как работает предложение друзей или алгоритм 2-й степени (linkedin) - PullRequest
Новая
       3

как работает предложение друзей или алгоритм 2-й степени (linkedin)

10 голосов
/ 20 апреля 2011

Я размышлял о предложениях в Facebook и других подобных системах.

Я думаю, что предложение Facebook также основывалось на личных знаниях, таких как школьные годы, компании, в которых я работал, или что-то подобное.* Но если быть более конкретным, здесь приведена схема facebook suggestion scheme

Case1 выглядит простым, но когда количество друзей увеличивается (событие с 300 друзьями слишком много), это неэффективно.Как насчет Case2?Какой алгоритм может сделать эту работу.

Я понятия не имею о Case3, потому что я думаю, что это что-то особенное для facebook.но как я могу обнаружить человека 4. К какой степени относится?

Ответы [ 2 ]

5 голосов
/ 20 апреля 2011

Я не уверен, спрашиваете ли вы, как делать предложения или определять расстояние между друзьями. Делать предложения легко, но, как правило, их размер увеличивается.

Первые два случая могут быть охвачены одним и тем же алгоритмом, а третий - небольшим расширением.

Первые два в основном ищут всех людей, которых знают ваши знакомые друзья: 

FriendHash = {}
foreach Friend in me.getFriends()
    foreach FriendOfFriend in Friend.getFriends()
        FriendHash{FriendOfFriend} += 1

foreach PotentialFriend in keys FriendHash
    if FriendHash{PotentialFriend} > 1
        me.suggestFriend(PotentialFriend)

В случае 1 связь между друзьями 1 и 2 могла бы стать дополнительным ограничением, которое фактически усложнило бы реализацию случая. Требуя, чтобы у друзей 1 и 2 была ссылка, вам нужно будет обнаруживать потенциальных друзей во время перебора пар друзей, а не один раз в конце. 

foreach Friend in me.getFriends()
    foreach SecondFriend in me.getFriends()
        # skip already processed friends and Friend == SecondFriend
        if Friend.getFriends() contains SecondFriend
            foreach FriendOfFriend in Friend.getFriends()
                # skip already suggested friends
                if SecondFriend.getFriends() contains FriendOfFriend
                    me.suggestFriend(PotentialFriend)

Конечно, есть некоторая оптимизация, которая может пропустить повторные сравнения. На практике это, вероятно, бесполезный поиск для запуска в любом случае. Все, что вы собираетесь сделать, это исключить потенциальных друзей, которые являются общими для двух разных групп друзей.

В последнем случае изменяется первый сегмент псевдокода, распространяя предложение друга на всех друзей ваших знакомых общих друзей: 

foreach PotentialFriend in keys FriendHash
    if FriendHash{PotentialFriend} > 1
        foreach ExtendedFriend in PotentialFriend.getFriends()
            me.suggestFriend(ExtendedFriend)

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

Если вы на самом деле смотрите на определение расстояния между другом и предложением, это, вероятно, не имеет значения.

1 голос
/ 10 июля 2012

Facebook, вероятно, получает информацию из вашего профиля, сообщения и использует количество подключений и т. Д. Расстояние может быть одним из факторов, который снова включается во взвешенную матрицу, такую ​​как вычисление.Затем суммируются и лучшие предложения выбираются с использованием порога для этой суммы.Информация об общих лайках, прямых комментариях и т. Д. Сбрасывается с серверов в журнал, возможно.Затем этот журнал анализируется каждую неделю или около того, чтобы предложить друзьям использовать Hadoop MapReduce.Этот результат для каждого человека может быть передан в веб-сервис, который предоставляет информацию пользователям при входе в систему.

Простое предложение друга с использованием MapReduce

Измененопредложение друга с использованием Mahout и MapReduce

...