Python中对二分图进行高效投影的方法（使用NetworkX）

Question

使用networkx模块，在Python 3.2下进行一些网络分析，需要将二分图（由囚犯与他们的牢房链接组成：在下面的代码中输入图B）投影到一个子图上（如果两个囚犯在同一牢房中有重叠的时间，则将它们联系起来：使用定义图B中囚犯节点的节点集作为输入，生成输出图G）。我不需要特殊算法来得出任何或最佳匹配，我只需要收集满足某些条件的所有链接。因此，我找到的其他SO帖子并不真正适用。但是：

随着我提供越来越多的数据，我的当前代码正在爆炸（RAM、swap和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

- László

---

你能再解释一下吗？我猜B是原始图，那么节点是什么？而且我不确定我理解你的意思。你有一个细胞和囚犯的二分图。然后你想要一个什么样的图？只有囚犯吗？如果他们在同一个单元里，就连接起来吗？ - Avaris

好的。术语“子图”让我感到困惑，因为从技术上讲，新图不会是一个子图。那么，为什么不只是迭代单元格并在新图中连接单元格的相邻单元格呢？ - Avaris

循环在Python中并不是非常高效的（http://wiki.python.org/moin/PythonSpeed/PerformanceTips#Loops）。如果你的两个内部循环变得很大，它可能会变得非常慢。你正在循环的东西的典型大小是什么？ - steabert

@Avaris：我认为这正是我在发布的代码中所做的，但我正在以无法接受的速度消耗资源。我正在寻找减少内存使用的方法。 - László

试图从代码中理解（如果我理解错了，请纠正）：nodes = 囚犯，u = 第一个囚犯，unbrs = u所在的单元格，nbrs2 = 所有留在unbrs中的囚犯，v = 另一个囚犯，mutual_cell = 他们共享的单元格。 - Avaris

Answer 1

现在可以使用二分图，例如：

import networkx as nx
from networkx.algorithms import bipartite

B.add_nodes_from(inmates_list, bipartite=0)
B.add_nodes_from(cells_list, bipartite=1)

inmates = set(n for n,d in B.nodes(data=True) if d['bipartite']==0)
cells = = set(B) - inmates
G = bipartite.projected_graph(B, inmates)

(http://networkx.lanl.gov/reference/algorithms.bipartite.html)

- Mario Alemi

---

在NetworkX 2.0中，您可以执行类似于inmates = {n for n, is_inmate in B.nodes(data='bipartite') if is_inmate}的操作，这样会更好一些（假设您反转了bipartite属性值1和0）。 - argentpepper

Answer 2

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

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

在这里我假设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

- Avaris

Answer 3

我发表这篇回答是为了提出一些改进意见。我假设你的二分图不是多重图，而是普通的nx.Graph。我将B更改为bi，将G更改为uni，因为按照惯例，大写名称保留给类。顺便问一下，如果拼写在完全相同的时间开始和结束会怎样？

def time_overlap_projected_graph_parallel(bi, nodes):
    uni = nx.MultiGraph()
    for u in nodes: #inmate
        uni.add_node(u) # do this to prevent iterating nodes twice
        u_adj = bi.adj[u] # bi.adj is a dict of dicts
        for (w, uw_attr) in u_adj.iteritems(): # cell
            w_adj = bi.adj[w]
            for (v, wv_attr) in w_adj.iteritems():#cellmate
                if v == u:
                    continue
                elif uni.has_edge(u, v): # avoid computing twice
                    continue
                for uspell in uw_attr.itervalues():
                    ustart = uspell[1]
                    uend = uspell[2]
                    for vspell in wv_attr.itervalues():
                        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 # this assumes floats or Python 3 otherwise will be 0
                            ocell = w
                            # I would change this to uni.add_edge(u, v, length=olen, start=ostart, end=oend, cell=ocell)
                            # or to uni.add_edge(u, v, spell=[olen, ostart, oend, ocell])
                            uni.add_edge(u, v, **{0: olen, 1: ostart, 2: oend, 3: ocell})
    return uni

- Midnighter

---

谢谢，我现在无法重新运行它以检查它有多快。你为什么认为它会更快呢？关于咒语：如果它们以错误的方式开始并结束，我可以放弃这些咒语。 - László

这应该会更快的主要原因是检查 uni.has_edge(u, v)。由于您正在循环遍历所有节点，因此在到达逆 uni.had_edge(v, u) 时，这将避免许多步骤已经计算。您的代码还检查一个拼写的交集是否已经存在于列表中，这是一个 O(n) 操作。不确定这些列表有多长。整个拼写计算可以进行改进。我会相应地进行编辑。总的来说，对于非常大的网络，networkx 可能不是正确的工具。 - Midnighter

@László，我在谈论if uend >= vstart and vend >= ustart的情况。 - Midnighter

谢谢，我认为那只会重复计算相同的东西，不是吗？ - László

Answer 4

考虑修订后的代码，可能使用迭代器完成相同的功能（尽管我也修改了一些与networkx相关的函数/方法调用---但我仍在检查是否出现错误）：

def time_overlap_projected_graph_parallel(B, nodes):
    G=nx.MultiGraph()
    G.add_nodes_from(nodes)
    for u in G.nodes_iter():#inmate
        for w in B.neighbors_iter(u):#cell
            for v in B.neighbors_iter(w):#cellmate
                if v == u:
                    continue
                for uspell in B[u][w].values():
                    ustart = uspell[1]
                    uend = uspell[2]
                    for vspell in B[v][w].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 = w
                            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

- László