二分图边列表转换为节点对相似度关联列表的最优实现方法

问题本质 #

你需要计算的是二部图中两类节点（实体节点A/B/C、关联节点1/2/3）里，实体节点对的共同关联节点数量，也就是共现相似度。

原有自连接方案的缺陷 #

自连接逻辑需要将所有边按关联节点匹配，时间复杂度为O(E²)，当单个关联节点关联大量实体节点时，会产生指数级的冗余中间结果，大数据量下无论是计算资源消耗还是执行效率都极差。

最优实现方案 #

核心思路是按关联节点分组后局部生成实体对，再全局统计频次，步骤如下：

• 第一步：遍历输入边列表，按关联节点（边的第二个元素）分组，得到每个关联节点对应的所有实体节点列表
• 第二步：对每个关联节点对应的实体列表，仅当列表长度≥2时，生成所有不重复的无序实体对（避免(A,B)和(B,A)被识别为不同对）
• 第三步：统计所有实体对的出现次数，即为该实体对的相似度权重

代码示例（Python） #

from collections import defaultdict, Counter

def calculate_common_edge_weight(edge_list):
    # 按关联节点分组
    group_by_rel = defaultdict(list)
    for entity, rel in edge_list:
        group_by_rel[rel].append(entity)
    
    pair_counter = Counter()
    for rel, entities in group_by_rel.items():
        # 生成所有无序不重复对
        n = len(entities)
        for i in range(n):
            for j in range(i+1, n):
                # 统一按字典序排序节点对，避免重复计数
                pair = tuple(sorted((entities[i], entities[j])))
                pair_counter[pair] += 1
    
    # 转换为输出格式
    return [(pair[0], pair[1], count) for pair, count in pair_counter.items()]

# 测试示例
input_edges = [("A",1),("A",2),("B",1),("B",2),("C",2),("C",3)]
print(calculate_common_edge_weight(input_edges))
# 输出：[('A', 'B', 2), ('A', 'C', 1), ('B', 'C', 1)]

性能优势 #

• 时间复杂度从O(E²)降低到O(E + sum(C(k_i,2)))，其中k_i是第i个关联节点的关联实体数，绝大多数业务场景下这个值远小于E²
• 无冗余中间结果生成，内存占用远低于自连接方案
• 天然适配分布式计算场景，按关联节点分区后即可并行计算，shuffle量仅为分组的体量，远低于自连接的shuffle开销

内容的提问来源于stack exchange，提问作者user7481779