Was ist die schnellste Iteration über eine große Netzwerkinstanz von DiGraph networkx?

Question

Ich schreibe eine Klasse, die von DiGraph.py aus dem Open-Source-networkx-Paket in Python erbt.

In einigen Methoden in meiner Klasse muss ich nach Knoten mit bestimmten Graden (outdegrees oder indegrees für gerichtete Graphen) suchen und sie zurückgeben.

Diese Klasse wird mit einem Data Mining-Projekt \ Natural Language Processing verwendet, das in sehr großen Netzwerken verwendet wird. Was ich brauche, ist eine schnelle Implementierung der beschriebenen Methode (Rückkehrliste von Knoten mit einem bestimmten Grad oder Grad).

Es gibt ein paar Dinge bereits in der Superklasse definiert: 1. Verfahren network.outdegree(): ein Wörterbuch mit Knotenschlüssel und outdegree Werte zurückgibt.

{'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. ein Verfahren, das

network.out_degree_iter ist()

<generator object out_degree_iter at 0x02EEB328> 

Ich weiß nicht, wie diese Methode zu verwenden, kann, wenn jemand erklären, wie die verwendet wird, , Ich werde dankbar sein.

3. Ich habe ein Attribut network.nodes, die eine Liste aller Knoten in meinem Netzwerk ist.

Frage: Ich kann über alle Knoten iterieren und die mit outdegree 2 zurückgeben, indem ich zum Beispiel ein Listenverständnis auf network.nodes mache, oder ich kann über mein Wörterbuch iterieren und eine Liste von Knoten mit Werten 2 zurückgeben. oder vielleicht die out_degree_iter(), die ich nicht weiß, wie ist das verwendet oder wie unterscheidet sich das Iterieren über Wörterbuch-Elemente in einer for-Schleife (für k, v in dict.iteritems()) ?? Welcher von diesen wäre schneller für ein sehr großes Netzwerk von Knoten und Kanten und WARUM?

Dank

Answer 1

Der einfachste Weg ist es, die out_degree_iter() -Methode mit einer Liste Verständnis zu verwenden, wie Sie vorgeschlagen. Hier ist, wie:

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 

Der schnellste Weg, um die interne Datenstruktur erfordert den Zugriff auf:

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

Für in-Grad uns in_degree_iter() und G.pred.items().

Hier sind einige Timings

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

Iteratoren sind besser für große Graphen, weil Sie keine Kopie des Wörterbuchs konstruieren. Wie wäre es etwa so:

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

Oder

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