Visualisierung eines ungerichteten Diagramms, das für GraphViz zu groß ist?

Ich benötige Ratschläge zum Rendern eines ungerichteten Diagramms mit 178.000 Knoten und 500.000 Kanten. Ich habe Neato, Tulip und Cytoscape ausprobiert. Neato kommt nicht einmal annähernd in die Nähe, und Tulip und Cytoscape behaupten, sie könnten damit umgehen, scheinen es aber nicht zu können. (Tulip tut nichts und Cytoscape behauptet zu arbeiten und hört dann einfach auf.)

Ich möchte nur eine Vektorformatdatei (ps oder pdf) mit einem entfernt vernünftigen Layout der Knoten.

Graphviz selbst bietet eine Lösung zum Rendern großer Grafiken.

Graphviz enthält nämlich sfdpeine mehrskalige Version von fdp (auch in graphviz, ähnlich wie ordentlich) für das Layout großer ungerichteter Diagramme, die zum Zeichnen großer Diagramme (70.000 Knoten, 500.000 Kanten) in meinem Projekt hilfreich war.

Die Dokumentation zu dieser Software finden Sie auf der graphviz-Website selbst unter http://www.graphviz.org/.

Weitere Informationen, ein Dokument, das die zugrunde liegenden Techniken und Beispiele beschreibt, finden Sie hier: http://yifanhu.net/PUB/graph_draw_small.pdf

Ich schlage vor, dass Sie zuerst eine Vorverarbeitung der Daten durchführen, z. B. Knoten zu Clustern reduzieren und dann die Cluster visualisieren. Durch das Reduzieren wird die Anzahl der Knoten verringert und Algorithmen wie Kamada-Kawai oder Fruchterman-Reingold können das resultierende Diagramm leichter rendern.

Wenn Sie wirklich 500.000 Knoten visualisieren müssen, können Sie ein einfaches kreisförmiges Layout verwenden. Dies ist ohne die Probleme, die zwangsbasierte Algorithmen haben, einfach zu rendern. Schauen Sie sich Circos an: http://mkweb.bcgsc.ca/circos/

Circos ist eine von Bioinformatikern entwickelte Graphvisualisierung, die auf die Visualisierung von Genomen und anderen extrem großen und komplexen Datensätzen zugeschnitten ist.

Es ist ein PERL-basiertes Paket, ich hoffe, das ist nicht problematisch.

Ich habe gute Ergebnisse mit der Graph-Tool- Bibliothek in Python erzielt . Das folgende Diagramm hat 1.490 Knoten und 19.090 Kanten - das Rendern auf meinem Laptop dauerte ungefähr 5 Minuten.

Die Grafikdaten stammen aus dem politischen Blogging-Netzwerk, das Adamic und Glance im PDF-Link „Die politische Blogosphäre und die US-Wahlen 2004“ hier beschrieben haben . Wenn Sie hineinzoomen, sehen Sie die Blog-URLs für jeden Knoten.

Hier ist der Code, mit dem ich ihn gezeichnet habe (Blog http://ryancompton.net/2014/10/22/stochastic-block-model-based-edge-bundles-in-graph-tool/ ):

import graph_tool.all as gt
import math

g = gt.collection.data["polblogs"] #  http://www2.scedu.unibo.it/roversi/SocioNet/AdamicGlanceBlogWWW.pdf
print(g.num_vertices(), g.num_edges())

#reduce to only connected nodes
g = gt.GraphView(g,vfilt=lambda v: (v.out_degree() > 0) and (v.in_degree() > 0) )
g.purge_vertices()

print(g.num_vertices(), g.num_edges())

#use 1->Republican, 2->Democrat
red_blue_map = {1:(1,0,0,1),0:(0,0,1,1)}
plot_color = g.new_vertex_property('vector<double>')
g.vertex_properties['plot_color'] = plot_color
for v in g.vertices():
    plot_color[v] = red_blue_map[g.vertex_properties['value'][v]]

#edge colors
alpha=0.15
edge_color = g.new_edge_property('vector<double>')
g.edge_properties['edge_color']=edge_color
for e in g.edges():
    if plot_color[e.source()] != plot_color[e.target()]:
        if plot_color[e.source()] == (0,0,1,1):
            #orange on dem -> rep
            edge_color[e] = (255.0/255.0, 102/255.0, 0/255.0, alpha)
        else:
            edge_color[e] = (102.0/255.0, 51/255.0, 153/255.0, alpha)            
    #red on rep-rep edges
    elif plot_color[e.source()] == (1,0,0,1):
        edge_color[e] = (1,0,0, alpha)
    #blue on dem-dem edges
    else:
        edge_color[e] = (0,0,1, alpha)

state = gt.minimize_nested_blockmodel_dl(g, deg_corr=True)
bstack = state.get_bstack()
t = gt.get_hierarchy_tree(bstack)[0]
tpos = pos = gt.radial_tree_layout(t, t.vertex(t.num_vertices() - 1), weighted=True)
cts = gt.get_hierarchy_control_points(g, t, tpos)
pos = g.own_property(tpos)
b = bstack[0].vp["b"]

#labels
text_rot = g.new_vertex_property('double')
g.vertex_properties['text_rot'] = text_rot
for v in g.vertices():
    if pos[v][0] >0:
        text_rot[v] = math.atan(pos[v][1]/pos[v][0])
    else:
        text_rot[v] = math.pi + math.atan(pos[v][1]/pos[v][0])

gt.graph_draw(g, pos=pos, vertex_fill_color=g.vertex_properties['plot_color'], 
            vertex_color=g.vertex_properties['plot_color'],
            edge_control_points=cts,
            vertex_size=10,
            vertex_text=g.vertex_properties['label'],
            vertex_text_rotation=g.vertex_properties['text_rot'],
            vertex_text_position=1,
            vertex_font_size=9,
            edge_color=g.edge_properties['edge_color'],
            vertex_anchor=0,
            bg_color=[0,0,0,1],
            output_size=[4024,4024],
            output='polblogs_blockmodel.png')

Probieren Sie Gephi aus , es hat ein neues Layout-Plugin namens OpenOrd , das auf Millionen von Knoten skaliert werden kann.

Mathematica könnte sehr wahrscheinlich damit umgehen, aber ich muss zugeben, dass meine erste Reaktion im Sinne des Kommentars lautete: "Nimm ein Stück Papier und färbe es schwarz." Gibt es keine Möglichkeit, die Dichte des Diagramms zu verringern?

Ein mögliches Problem ist, dass Sie anscheinend nach Layout suchen und nicht nur nach Rendering. Ich habe keine Kenntnis über die Big O-Eigenschaften der Layouts, die von verschiedenen Tools implementiert wurden, aber intuitiv würde ich vermuten, dass es lange dauern kann, so viele Daten zu erstellen.

Muss es wirklich genau sein?

Je nachdem, was Sie erreichen möchten, reicht es möglicherweise aus, nur 10% oder 1% des Datenvolumens grafisch darzustellen. (Natürlich kann es auch völlig nutzlos sein, aber alles hängt davon ab, wofür die Visualisierung gedacht ist.)

BioFabric ( www.BioFabric.org ) ist ein weiteres Tool zur Visualisierung großer Grafiken. Das beschriebene Netzwerk (178.000 Knoten und 500.000 Kanten) sollte in Ordnung sein, obwohl das anfängliche Layout eine Weile dauern kann. Die hier gezeigte Netzwerkshow (aus der Stanford Large Network Dataset Collection) ist das Stanford Web Network mit 281.903 Knoten und 2.312.497 Kanten:

Die Skalierbarkeit von BioFabric beruht auf der Tatsache, dass Knoten nicht als Punkte, sondern als horizontale Linien dargestellt werden. Die Kanten werden dann als vertikale Linien angezeigt. Für eine Vorstellung davon , wie dies funktioniert, gibt es die Super-Quick BioFabric-Demo , ein kleines Netzwerk, das mit D3 animiert wird.

Die primäre Anwendung ist in Java geschrieben. Derzeit können nur PNG-Bilder exportiert werden, keine PDFs. Es gibt eine PDF- Exportoption von RBioFabric , obwohl dies eine sehr einfache Implementierung ist, die noch keine wirklich großen Netzwerke verarbeiten kann.

Vollständige Offenlegung: BioFabric ist ein Tool, das ich geschrieben habe.

Ich gehe davon aus, dass Edge-Clustering ( http://www.visualcomplexity.com/vc/project_details.cfm?id=679&index=679&domain= ) helfen würde. Diese Technik bündelt verwandte Kanten und reduziert so die visuelle Komplexität des Diagramms. Möglicherweise müssen Sie den Algorithmus jedoch selbst implementieren.

Sie können den Entwicklern dieser Tools möglicherweise eine bereinigte Version der Datei als Debugging-Szenario anbieten, wenn alles andere fehlschlägt.

Sie können aiSee ausprobieren: http://www.aisee.com/manual/unix/56.htm

Schauen Sie sich die Java / Jython-basierte GUESS an: http://graphexploration.cond.org/

Das LGL- Projekt (Large Graph Layout) hat mir bei einem ähnlichen Problem sehr geholfen. Es verwaltet das Layout und verfügt über eine kleine Java-App zum Zeichnen von erstellten Layouts in 2D. Keine Vektorausgabe sofort verfügbar, daher müssen Sie das Diagramm selbst zeichnen (angesichts der von LGL erzeugten Knotenkoordinaten).

Ein Windows-Tool, das Diagramme visualisieren kann, ist pajek . Es generiert eine EPS-Ausgabe. Ich weiß jedoch nicht, ob es Ihre Daten lesen kann.

Hier finden Sie eine Liste der Apps: http://www.mkbergman.com/?p=414

Walross und LGL sind zwei Werkzeuge, die angeblich für große Grafiken geeignet sind. Beide scheinen jedoch die Eingabe von Diagrammen als Textdateien in ihrem eigenen speziellen Format zu erfordern, was möglicherweise schmerzhaft ist.

Ich glaube nicht, dass Sie sich der Visualisierung in einem flachen Layout annähern können.

Ich bin fasziniert von hyperbolischen Graphen, die in diesem Forschungsbericht seit einiger Zeit beschrieben werden. Probieren Sie die Software von SourceForge aus .

Eine andere Idee besteht darin, die Knoten mithilfe einer TreeMap grafisch darzustellen, wie bei Panopticode dargestellt .

Sie können auch NAViGaTOR ausprobieren (Offenlegung: Ich bin einer der Entwickler für diese Software). Wir haben damit erfolgreich Grafiken mit bis zu 1,7 Millionen Kanten visualisiert. Obwohl so große Netzwerke schwer zu manipulieren sind (die Benutzeroberfläche wird verzögert). Es wird jedoch OpenGL für die Visualisierung verwendet, sodass ein Teil des Overheads auf die Grafikkarte übertragen wird.

Beachten Sie auch, dass Sie die Speichereinstellungen im Dialogfeld Datei-> Einstellungen erhöhen müssen, bevor Sie ein so großes Netzwerk erfolgreich öffnen können.

Wie die meisten anderen Antworten zeigen, ist es besser, wenn Sie Ihre Daten in etwas Kleineres und Bedeutenderes umorganisieren.

Erstens möchte ich dem Vorschlag von aliekens folgen, sfdp auszuprobieren. Es ist die großformatige Version von Neato.

Wie OJW vorschlägt, können Sie die Knoten auch einfach in R2 zeichnen. Ihre Kanten liefern tatsächlich das, was er als "natürliche Ordnung" bezeichnet. Insbesondere können Sie die Komponenten des zweiten und dritten Eigenvektors des normalisierten Laplace-Graphen darstellen. Dies ist die Matrix Lauf dieser Wikipedia-Seite über spektrale Clusterbildung . Sie sollten in der Lage sein, diese Matrix aufzuschreiben, ohne die dahinter stehende lineare Algebra zu verstehen. Dann haben Sie Ihr Problem auf die ungefähre Berechnung der ersten Eigenvektoren einer großen Matrix mit geringer Dichte reduziert. Dies geschieht traditionell mit iterativen Methoden und wird in Standardpaketen für lineare Algebra implementiert. Diese Methode sollte auf sehr große Diagramme skaliert werden.