python - 寻找最近连接的图算法

Question

我有一个数据集，记录员工每个轮类的工作情况。对于每位员工，我想找到与他们共事最多的同事。

该表大约有 2.5 亿行，有 5000 万个类次和 10 万个唯一员工。举个例子，表格开头如下:

+----------+--------+
| Shift ID | Emp ID |  
+----------+--------+
|        1 | A      |  
|        1 | B      |  
|        2 | A      |
|        2 | C      | 
|        3 | A      |  
|        3 | C      |
+----------+--------+

员工 A 与员工 B 合作过一次，但与员工 C 合作过两次。因此，员工 A 最常来的同事是员工 C。

什么算法可以找到每个员工最常联系的同事？天真地试图找到成对共同移位的数量太慢了:

solution = {}
for e in employees:
    maxCommonShifts = 0
    for c in employees:
        if e != c:
            commonTrips = len(e.trips ∩ c.trips)
            if commonTrips > maxCommonShifts:
                maxCommonShifts = commonTrips
                solution[e] = c

我相信图算法将是这里的解决方案。具体来说，这个问题似乎类似于 FB 试图计算一个人最亲密的 friend ，即他们拥有最多的共同 friend 。从图中来看，每个类次有一个节点，每个员工有一个节点。每个员工节点都连接到他们工作过的每个轮类节点。

Answer 1

2.5 亿行加上 50M 类次，平均每个类次有 5 行，因此为每个类次创建一组记录，给出该类次中的员工对，将使数据大小增加超过 5 倍，即很贵但也不算太糟糕。因此，您的第一个类次，看到 1A 和 1B，将创建记录 AB 和 BA 对的两条记录。如果您有 1A、1B 和 1C，那么您将创建记录 AB、AC、BA、BC、CA、CB。

通过这种格式的输入，您可以使用小程序和排序实用程序(unix 和 windows 都有排序程序)或在数据库中使用 SQL 来执行您想要的操作。对第一个成员生成的大约 2000M 对的列表进行排序，然后对第二个成员生成的列表进行排序。然后按顺序处理这个列表。您将看到按顺序排序的记录，例如 AB AB AB AC AC AD AD AD AD AD AE AE...，您可以挑选出相同记录的运行并对它们进行计数，跟踪每个第一个元素的最长此类运行当你遇到它时就一对。