Python Mit einer Verbindung/Netzwerk-Graphen erzeugen

Question

ich eine Textdatei in Form mit etwa 8,5 Millionen Datenpunkte haben:

Company 87178481 
Company 893489 
Company 2345788 
[...] 

Ich möchte Python verwenden, um eine Verbindung Graphen zu erstellen, was das Netz zu sehen, zwischen Unternehmen sieht so aus. Aus dem obigen Beispiel würden sich zwei Unternehmen eine Kante teilen, wenn der Wert in der zweiten Spalte gleich ist (Klärung von/für Hooked).

Ich habe das NetworkX Paket verwendet und bin in der Lage, ein Netzwerk für ein paar tausend Punkte zu generieren, aber es ist nicht durch die volle 8,5 Millionen Knoten Textdatei. Ich lief es und ging für etwa 15 Stunden, und als ich zurückkam, blinkte der Cursor in der Shell immer noch, aber es gab kein Ausgabediagramm.

Ist es sicher anzunehmen, dass es noch lief? Gibt es einen besseren/schnelleren/einfacheren Ansatz, um Millionen von Punkten grafisch darzustellen?

Answer 1

Wenn Sie 1000K Datenpunkte haben, benötigen Sie eine Möglichkeit, das Gesamtbild zu betrachten. Abhängig davon, was Sie genau suchen, können Sie, wenn Sie eine "Entfernung" zwischen Unternehmen angeben können (z. B. Anzahl der Verbindungen getrennt), Beziehungen (oder Clustering) über eine Dendrogram visualisieren.

Scipy tut clustering:

http://docs.scipy.org/doc/scipy/reference/cluster.hierarchy.html#module-scipy.cluster.hierarchy

und hat eine Funktion, um sie in Dendrogramme zur Visualisierung drehen:

http://docs.scipy.org/doc/scipy/reference/generated/scipy.cluster.hierarchy.dendrogram.html#scipy.cluster.hierarchy.dendrogram

Ein Beispiel für einen kürzesten Funktion Bahnweg über networkx:

http://networkx.lanl.gov/reference/generated/networkx.algorithms.shortest_paths.generic.shortest_path.html#networkx.algorithms.shortest_paths.generic.shortest_path

Schließlich müssen Sie entscheiden, wie Sie die Entfernung zwischen zwei Firmen (Vertices) in Ihrem Diagramm gewichten möchten.

Answer 2

Sie haben zu viele Datenpunkte und wenn Sie das Netzwerk visualisiert haben, ergibt das keinen Sinn. Sie müssen Möglichkeiten haben, 1) die Anzahl der Unternehmen zu reduzieren, indem Sie diejenigen entfernen, die weniger wichtig/weniger verbunden sind. 2) das Diagramm irgendwie zusammenfassen und dann visualisieren.

Um die Größe der Daten zu reduzieren, ist es möglicherweise besser, das Netzwerk unabhängig zu erstellen (mit Ihrem eigenen Code, um eine Edge-Liste von Unternehmen zu erstellen). Auf diese Weise können Sie die Größe Ihres Graphen reduzieren (z. B. durch Entfernen von Singletons, die viele sein können).

Zur Zusammenfassung empfehle ich, einen Clustering- oder Community-Erkennungsalgorithmus auszuführen. Dies kann sehr schnell auch für sehr große Netzwerke durchgeführt werden. Verwenden Sie die „fastgreedy“ -Methode in der IGRAPH Paket: http://igraph.sourceforge.net/doc/R/fastgreedy.community.html (es ist ein schneller Algorithmus auch online verfügbar, ist dies von Blondel et al: http://perso.uclouvain.be/vincent.blondel/publications/08BG.pdf weiß, dass ich ihren Code online irgendwo ist)