Was ist die schnellste Iteration über ein großes Netzwerk Instanz von digraph NetworkX?

Question

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

In einigen Verfahren in meiner Klasse, ich brauche für Knoten mit bestimmtem Grad (outdegrees oder indegrees für gerichtete Graphen) zu suchen und sie zurück.

Diese Klasse mit einem Data-Mining-Projekt \ Verarbeitung natürlicher Sprache verwendet werden soll, seine auf extrem großen Netzwerken verwendet werden würde. was ich brauche, ist eine schnelle Durchführung des Verfahrens beschrieben (Rückgabeliste der Knoten mit einem gewissen Grad aus oder bestimmt in Grad).

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

{'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 ist

network.out_degree_iter ()

<generator object out_degree_iter at 0x02EEB328>

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

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

Frage: Ich kann alle Knoten durchlaufen und das Rück die, die mit outdegree 2 zum Beispiel durch eine Liste Verständnis auf network.nodes tun, oder ich kann meinen Wörterbuch iterieren und eine Liste von Knoten mit Werten 2, oder vielleicht nutzen die out_degree_iter(), die ich weiß nicht, wie das verwendet wird, oder wie ist das anders Iterieren über Wörterbuch Artikel in einer for-Schleife (für k, v in dict.iteritems ()) ?? Welcher dieser wäre schneller für ein sehr großes Netzwerk von Knoten und Kanten und WARUM ??

Danke

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 erfordert die interne Datenstruktur zugreifen:

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 so etwas wie folgt aus:

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()))