有向图网络 x 的大型网络实例上最快的迭代是多少？

Question

我正在编写一个类，它继承自Python中开源networkx包的DiGraph.py。

在我的类中的某些方法中，我需要搜索具有一定度数的节点（有向图的出度或入度）并返回它们。

该类将与数据挖掘项目\自然语言处理一起使用，它将用于非常大的网络。我需要的是所描述的方法的快速实现（返回具有特定出度或特定入度的节点列表）。

超类中已经定义了一些内容： 1. 方法network.out Degree()： 返回带有节点键和出度值的字典。

{'school': 4, 'middle school': 0, 'university': 0, 'commercial': 0, 'private': 5, 'institution': 2, 'high school': 0, 'college': 0, 'elementary school': 0, 'central': 0, 'company': 0, 'public': 3, 'bank': 2}

1. 一个方法是

network.out_ Degree_iter()

<generator object out_degree_iter at 0x02EEB328>

我不知道如何使用这个方法，如果有人可以解释它是如何使用的，我将不胜感激。

3.我有一个属性network.nodes，它是我的网络中所有节点的列表。

问题：我可以迭代所有节点并返回出度为 2 的节点，例如，通过对 network.nodes 进行列表理解，或者我可以迭代字典并返回值为 2 的节点列表，或者可以使用out_ Degree_iter() 我不知道它是如何使用的，也不知道它与 for 循环中迭代字典项有什么不同（ for k,v in dict.iteritems() ）？对于一个非常大的节点和边缘网络来说，哪一个更快，为什么？

谢谢

Answer 1

最简单的方法是按照您的建议使用带有列表理解的 out_ Degree_iter() 方法。方法如下：

import networkx as nx
G=nx.DiGraph(nx.gnp_random_graph(1000,0.001))
t1=[n for n,k in G.out_degree_iter() if k==2

最快的方法需要访问内部数据结构：

t2=[n for n,nbrs in G.succ.items() if len(nbrs)==2]

对于入度，我们使用 in_ Degree_iter() 和 G.pred.items()。

以下是一些时间安排

In [41]: %timeit t1=[n for n,k in G.out_degree_iter() if k==2]
1000 loops, best of 3: 368 us per loop

In [42]: %timeit s2=[n for n,nbrs in G.succ.items() if len(nbrs)==2]
1000 loops, best of 3: 198 us per loop

Answer 2

迭代器更适合大型图，因为您不需要构建字典的副本。像这样的事情怎么样：

list_of_2 = []
for g in G.out_degree_iter():
    if g[1]==2:
        list_of_2.append(g[0])

或者，

list_of_2 = map(lambda x:x[0],filter(lambda x:(x[1]==2),G.out_degree_iter()))