2010-11-01 13 views
12

Ich habe eine Reihe von Paketen für Graph-Layout (Graphviz, Gephi, Cytoscape, NetworkX, um einige der häufiger zu nennen) und keiner von ihnen schien zu sehen Skalierung auf diese Art von Größe. Welche Techniken gibt es, um Graphen dieser Größe zu visualisieren oder sie auf etwas überschaubarer zu reduzieren?Large Scale Graph Visualisierung (50K Knoten, 100M gewichtete Kanten)

+0

Meine Vermutung ist, dass der Hauptberechnungsengpaß die Dichte ist. Haben Sie versucht, zuerst in "Super Vertices" zu gruppieren, stattdessen diese zu plotten? https://docs.google.com/viewer?url=http://www.elsevier.com/authored_subject_sections/P05/misc/Schaeffer.pdf – spenthil

+0

Ich habe versucht, etwas aus meinen Rändern auszudünnen, aber ich tue es nicht wirklich wollen, w/r/t Knoten zu begleichen. Das könnte aber für einen Multiskalen-Algorithmus nützlich sein - danke! – sbirch

Antwort

11

Gephi ‚s OpenOrd Visualisierung Plugin kann Millionen von Knoten Layout.

+0

Ja, Gephi sieht sehr cool aus. Gibt es etwas für .NET, das eingebettet werden kann und keine Abhängigkeiten zu Java hat und auf Millionen von Knoten skalieren kann? –

0

Ich habe das Visualisierungs-Toolkit Processing zur Visualisierung von Netzwerken von etwa 30K Knoten verwendet. Es wird keine Probleme beim Rendern Ihrer Knoten haben, aber Sie müssen einige Ihrer Kanten entfernen, vielleicht diejenigen mit dem geringsten Gewicht entfernen (wenn es gewichtet ist) oder, wie anderswo vorgeschlagen, einen Hypergraphen konstruieren.

Es gibt derzeit keine Netzwerkbibliothek für die Verarbeitung, es gibt also keinen Zugriff auf Layoutalgorithmen usw. Sie müssen es selbst implementieren, aber es ist ziemlich schnell. Ich habe darüber nachgedacht, eine Bibliothek zu veröffentlichen, um diese Art der Visualisierung zu unterstützen.

http://www.processing.org

0

Tulip ist genau dafür geeignet, aber das Rendering ist nicht sehr schnell, sobald Sie zu einer hohen Anzahl von Knoten und Kanten kommen.