使用图形算法查找最近的连接

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试图从一个人的共同朋友最多的角度来计算一个人的最亲密的朋友。就该图而言，每个班次有一个节点，每个雇员有一个节点。每个员工节点都连接到他们工作的每个班次节点。

Answer 1

2.5亿行且有5000万个班次，平均每个班次有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 ...，您可以挑选出相同记录的运行并对其进行计数，并跟踪记录中每个第一个元素的最长运行时间碰到一对。