Visualisierung sehr großer Linkgraphen

25

Ich bin auf der Suche nach einem Tool zur Visualisierung sehr großer Richtungsverbindungsdiagramme. Ich habe derzeit ~ 2 Millionen Knoten mit ~ 10 Millionen Kanten. Ich habe ein paar verschiedene Dinge ausprobiert, aber die meisten brauchen Stunden, um sogar 100k-Knotengraphen zu erstellen

Was ich versucht habe:
Ich habe einen Tag mit Gephi verbracht, aber das Hinzufügen von 80K-Knoten dauert ungefähr eine Stunde, und die Anwendung wird größtenteils unbrauchbar.

Irgendwelche Vorschläge?

Eine interaktive Visualisierung wäre von Vorteil.

visualization Madmaze
quelle
Es würde helfen, wenn Sie angeben, was Sie bereits versucht haben. Haben Sie Graphviz ausprobiert?
Wolfgang Bangerth
1
Graphviz ist das, was ich zuerst versuchen würde. Keine Ahnung, ob es mit so etwas klappt. Natürlich benötigen Sie etwas, das eine spärliche Darstellung für die Adjazenzmatrix verwendet, aber es scheint unvorstellbar, dass ein Softwarepaket dies nicht tun würde.
David Ketcheson
Ich gebe Graphviz jetzt eine
Chance
2
Haben Sie versucht, den Graphen als spärliche Matrix zu interpretieren und ihn mit MATLAB oder Octaves 'Spy'-Funktion zu visualisieren? 10 Millionen Einträge ungleich Null sind für mäßig leistungsfähige Desktops gut erreichbar. Dies würde Sie auch auf die Spektralhalbierung einstellen (das Auffinden von Partitionen Ihres Diagramms erleichtert Ihnen möglicherweise die Visualisierung).
Jack Poulson
1
Hast du dich umgesehen?
PyCthon

Antworten:

13

Graphviz sollte funktionieren. Ich glaube, dass die Bilder, die mit den Matrizen in der spärlichen Matrixsammlung der Universität von Florida assoziiert sind, mit sfdp, einem von Yifan Hu entwickelten kraftgerichteten Graphvisualisierungsalgorithmus, visualisiert wurden. Die meisten Matrizen in der Sammlung haben eine Rechenzeit, die mit dem Generieren einer entsprechenden Visualisierung verbunden ist, sodass Sie möglicherweise nach Matrizen suchen können, deren Diagramme ähnliche Eigenschaften aufweisen wie die, die Sie visualisieren möchten. Zum Beispiel wurden für ein Diagramm mit ~ 2,1 Millionen Knoten und ~ 3 Millionen Kanten ~ 36000 Sekunden oder 10 Stunden benötigt. Obwohl nicht klar ist, mit welcher Hardware das Diagramm erstellt wurde, ist es wahrscheinlich eine vernünftige Annahme, dass ein Desktop oder Laptop verwendet wurde, und die Zeiten geben Ihnen zumindest eine ungefähre Vorstellung davon, wie viel Zeit das Rendern des Diagramms in Anspruch nehmen kann. Hus Algorithmus scheint einer der modernsten Visualisierungsalgorithmen zu sein (er veröffentlichte ihn 2005), aber da er kein Experte auf diesem Gebiet ist, kann ich nicht darüber sprechen, ob es bessere Algorithmen gibt oder nicht. Dieser Algorithmus ist in Graphviz als Option enthalten und kann für große Diagramme wie das von Ihnen beschriebene verwendet werden.

Geoff Oxberry
quelle
Sehr gepflegt. Es sieht so aus, als würde Barnes-Hut verwendet, um Kräfte zwischen den Knoten des Graphen zu simulieren. Daher würde ich davon ausgehen, dass eine parallele FMM-Implementierung zu einer erheblichen Beschleunigung führen könnte. Andererseits scheint die Methode von Hu eine Mehrebenenstruktur ähnlich der von MeTiS zu haben, die sich nur schwer parallelisieren lässt.
Jack Poulson
Ja, als ich mir das Papier ansah, dachte ich auch, dass eine parallele FMM-Implementierung interessant sein könnte, aber ich war mir nicht sicher, wie praktisch dies sein würde, da ich nicht viel Erfahrung mit parallelen Algorithmen habe.
Geoff Oxberry
3
@ JackPoulson - Husten
Aron Ahmadia
@ GeoffOxberry - siehe Link oben
Aron Ahmadia
1
@JackPoulson - Sie werden feststellen, dass die erzwungenen Layoutalgorithmen sehr empfindlich auf das anfängliche Seeding reagieren. Andere Gruppen haben gute Arbeit geleistet, um das Problem für ästhetischere Layouts neu zu formulieren.
Aron Ahmadia
5

Siehe Graphinsight 1.2, kann problemlos mit Millionen von Knoten umgehen und ist interaktiv und in 3D.

Sie können auch Diagramme mit Millionen von Knoten und Kanten mit hocheffizienten algebraischen Methoden oder erzwungenen Methoden erstellen. Es ist in einer Testversion zur Evaluierung verfügbar ( Haftungsausschluss: Ich bin einer der Autoren des Programms ).

www.graphinsight.com

linello
quelle
1
@linelio - Danke für deine Antwort und willkommen bei scicomp! Bitte beachten Sie die Regeln zur Werbung und vergewissern Sie sich, dass Sie alle persönlichen Zusammenhänge offen legen, wenn Sie Empfehlungen aussprechen.
Aron Ahmadia
5

Hier sind einige Empfehlungen und Links, die im Laufe der Zeit gesammelt wurden:

  • Für 2M-Knoten ist es schwierig, etwas zu empfehlen, das Ihre Hardware nicht kennt, und möglicherweise ist eine gewisse Datenreduktion angebracht. Wenn Sie jedoch frei verfügbare Elemente verwenden, kann zGrViewer Ihren Anforderungen an die Visualisierung entsprechen (erfordert GraphViz).
  • Schlagen Sie, der Idee von @pyCthon folgend, vor, dass Sie sich auch VisIt ansehen, um mehr Interaktivität beim Plotten zu erhalten.
  • Ich besuche das igraphPaket für die statistische Sprache R erneut , das unter anderem saubere Layoutalgorithmen ( Fruchterman-Reingold und Kamada-Kawai ) enthält.
  • Die große Grafiklayout- Bibliothek ist jetzt in SourceForge verfügbar.
Hirschjäger
quelle
0

Wir haben http://www.github.com/graphistry/pygraphistry erstellt , um dies in den meisten Browsern und Notebooks zu ermöglichen. Die Idee ist, WebGL zu verwenden, um die großen Grafiken (Schwenken / Zoomen / usw.) zu rendern und den größten Teil der Echtzeitberechnung (Layout, Filter usw.) in eine GPU-Cloud zu verlagern. Es ähnelt Gephi oder Cytoscape, konzentriert sich jedoch mehr auf große Grafiken und Datenanalysen sowie auf die Integration in das Web und in Notizbücher.

Leo Meyerovich
quelle
0

Sie können "Tulip" [1] ausprobieren, ich denke, es kann sehr große Graphen verarbeiten (zumindest habe ich es mit 10K bis 100K Knoten versucht und es hat gut funktioniert).

[1] http://tulip.labri.fr/TulipDrupal/

BrunoLevy
quelle