高效的算法，采用 Twitter 用户并按照其关注者数量的顺序找到顶级用户

Question

标题很罗嗦。所以我会用一个例子来解释。

我们有一个包含 10,000 个 Twitter 用户的数据库，每个用户最多可关注 2000 个用户。该算法将一个从未见过的随机用户（包括关注他的人）作为输入，并按照关注者数量的顺序从数据库中返回 Twitter 用户。

IE 我们有：

用户 A 关注 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)

Answer 1

将数据存储为大小为 10^5x10^5 的稀疏整数矩阵 A，并在适当的位置添加 1。然后，给定用户i，计算A[i,] * A（矩阵乘法）。然后排序。

Answer 2

假设您有一个与此类似的表结构：

Table Users

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

Table UserFollowers

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

您可以使用以下查询来获取关注者的common父级查询中用户的关注者

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

Answer 3

像这样的东西会起作用吗？

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

sort the ff-s by their counts 

与矩阵解决方案不同，其复杂性与涉及的人数成正比，而不是与 Twitter 上的用户数量成正比。