Эффективный алгоритм, который берет пользователя Твиттера и находит лучших пользователей в порядке того, сколько его последователей они следуют - PullRequest
Новая
       2

Эффективный алгоритм, который берет пользователя Твиттера и находит лучших пользователей в порядке того, сколько его последователей они следуют

2 голосов
/ 21 января 2012

Название очень многословно. Поэтому я объясню на примере.

У нас есть база данных из 10 000 пользователей Twitter, каждый из которых до 2000 пользователей. Алгоритм принимает в качестве входных данных одного случайного никогда ранее не виденного пользователя (включая людей, которые за ним следят) и возвращает пользователей Твиттера из базы данных в порядке того, сколько его последователей они отслеживают.

т.е. У нас есть:

Пользователь А следует за 1,2,3,4

Пользователь B следует 3,4,5,6

Пользователь C следует 4,8,9

Мы вводим пользователя X, у которого есть пользователи 3,4,5, следующие за ним.

Алгоритм должен вернуть:

B: 3 матча (3,4,5)

A: 2 совпадения (3,4)

C: 1 совпадение (4)

Ответы [ 3 ]

0 голосов
/ 21 января 2012

Сохраните данные в виде разреженной целочисленной матрицы A размером 10 ^ 5x10 ^ 5 с единицами в соответствующих местах.Затем, учитывая пользователя i, вычислите A[i,] * A (умножение матриц).Тогда сортируй.

0 голосов
/ 21 января 2012

что-то вроде этой работы? 

for f in followers(x)
    for ff in followers(f)
        count[ff]++  // assume it is initially 0

sort the ff-s by their counts

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

0 голосов
/ 21 января 2012

Предполагая, что у вас есть структура таблицы, подобная этой:

Пользователи таблицы 

Id (PK, uniqueidentifier, not null)
Username (nvarchar(50), not null)

Таблица UserFollowers 

UserId (FK, uniqueidentifier, not null)
FollowerId (uniqueidentifier, not null)

Вы можете использовать следующий запрос, чтобы получить common родителей последователей followers of the user in query

SELECT     Users_Inner.Username, COUNT(Users_Inner.Id) AS [Total Common Parents]
FROM         Users INNER JOIN
                  UserFollowers ON Users.Id = UserFollowers.FollowerId INNER JOIN
                  UserFollowers AS UserFollowers_Inner ON UserFollowers.FollowerId = UserFollowers_Inner.UserId INNER JOIN
                  Users AS Users_Inner ON UserFollowers_Inner.FollowerId = Users_Computed.Id
WHERE     (UserFollowers.UserId = 'BD34A1FF-FCF5-4D35-B8A3-EFFB1587A874')
GROUP BY Users_Inner.Username
ORDER BY COUNT(Users_Inner.Id) DESC
...