python中二部图的高效投影（使用networkx）

Question

使用 networkx 模块，我在 Python 3.2 下进行了一些网络分析，其中我需要将一个二分图（链接到其牢房的囚犯：在下面的代码中输入图 B）投影到一个子图（如果牢房中的囚犯都有同一单元中的重叠咒语：使用定义图 B 的囚犯节点的集合节点的输入，生成输出图 G）。我不需要特殊的算法来提出任何匹配或最佳匹配，我只需要收集满足某些条件的所有链接。因此我发现的其他 SO 帖子并不真正适用。但：

当我给它提供越来越多的数据时，我当前的代码正在崩溃（RAM、交换和 CPU 方面）。如果您发现使用 5 层循环简化下面代码的方法，请告诉我。我不确定是否需要任何有关 networkx 的知识，或者我的边缘属性标签的详细信息是否相关。谢谢！

def time_overlap_projected_graph_parallel(B, nodes):
    G=nx.MultiGraph()
    G.add_nodes_from((n,B.node[n]) for n in nodes)
    for u in nodes:
        unbrs = set(B[u])
        nbrs2 = set((n for nbr in unbrs for n in B[nbr])) - set([u])
        for v in nbrs2:
            for mutual_cell in set(B[u]) & set(B[v]):
                for uspell in B.get_edge_data(u,mutual_cell).values():
                    ustart = uspell[1]
                    uend = uspell[2]
                    for vspell in B.get_edge_data(v,mutual_cell).values():
                        vstart = vspell[1]
                        vend = vspell[2]
                        if uend > vstart and vend > ustart:
                            ostart = max(ustart,vstart)
                            oend = min(uend,vend)
                            olen = (oend-ostart+1)/86400
                            ocell = mutual_cell
                            if (v not in G[u] or ostart not in [ edict[1] for edict in G[u][v].values() ]):
                                G.add_edges_from([(u,v,{0: olen,1: ostart,2: oend,3: ocell})])
    return G

Answer 1

这是我的看法。根据每个牢房的平均囚犯数量，它可能会提高性能。如果您有更好的方法来获取单元格（例如节点属性？），请替换

cells = [n for n in B.nodes() if n[0] not in nodes]

这样（这里我假设节点是所有囚犯的列表）。

from itertools import combinations

def time_overlap_projected_graph_parallel(B, nodes):
    G=nx.MultiGraph()
    G.add_nodes_from((n,B.node[n]) for n in nodes)
    cells = [n for n in B.nodes() if n[0] not in nodes]
    for cell in cells:
        for u,v in combinations(B[cell],2):
            for uspell in B.get_edge_data(u,cell).values():
                ustart = uspell[1]
                uend = uspell[2]
                for vspell in B.get_edge_data(v,cell).values():
                    vstart = vspell[1]
                    vend = vspell[2]
                    if uend > vstart and vend > ustart:
                        ostart = max(ustart,vstart)
                        oend = min(uend,vend)
                        olen = (oend-ostart+1)/86400
                        ocell = cell
                        if (v not in G[u] or ostart not in [ edict[1] for edict in G[u][v].values() ]):
                            G.add_edge(u,v,{0: olen,1: ostart,2: oend,3: ocell})
    return G