Clustered Graphs Visualisierungstechniken

Question

Ich brauche einen relativ großen Graphen (6K Knoten, 8K Kanten) sichtbar zu machen, die die folgenden Eigenschaften hat:

• verschiedene Cluster. Etwa 50-100 pro Cluster-Knoten und moderate Vernetzung auf Clusterebene
• Minimal (5-10 Inter-Cluster-Flanken pro Cluster) Zusammenschaltbarkeit zwischen Clustern

globale Kantenüberlappung Let = die Randüberlappungen durch direkte Visualisierung verursacht ein Graph von Clustern = {A, B, C, D, E}, Kanten = {Pentagram dieser Cluster, der übrigens nicht planar ist und definitiv Randüberlappungen erzeugt, wenn Sie ihn direkt zeichnen}

Lassen Sie Local Edge Overlap = die oben genannten, aber {A, B, C, D, E} sind nur Knoten.

Ich brauche Graphen mit der oben in eine Art und Weise sichtbar zu machen, die folgenden Anforderungen

• No globale Kantenüberlappung erfüllt (dh Kante durch Inter-Cluster-Eigenschaften verursacht überlappt, nicht in Ordnung)
• Local Überlappungskante innerhalb eines Clusters ist in Ordnung

Jeder hat Gedanken, wie man am besten ein Diagramm mit den oben genannten Anforderungen visualisiert?

Eine Lösung für die globale Kantenüberlappung besteht darin, sicherzustellen, dass ein Cluster A während der Visualisierung nur maximal 1 direkte Kante zu einem anderen Cluster (B) haben kann. Alle zusätzlichen Inter-Cluster-Kanten zwischen Cluster A -> C, A -> D, ... sind getrennt und zusätzliche Knoten/Kanten A -> A_C, C -> C_A, A -> A_D, D -> D_A ... sind erstellt.

Wer hat irgendwelche Gedanken?

Answer 1

Prefuse hat einige gute Graphzeichnung link text Algorithmen eingebaut und es scheint ziemlich große Graphen relativ gut zu behandeln. Sie könnten versuchen, Flow Map Layout, die auf Prefuse gebaut ist.

Answer 2

Ich habe nicht zu viele Graph-Visualisierungswerkzeuge gesehen, die das Trennen von Clustern innerhalb eines Graphen visuell unterstützen. Eine Option könnte sein, einen Blick auf WilmaScope zu werfen. Es scheint Unterstützung für clusterbasierte Layouts zu haben.

Answer 3

Angesichts Ihrer Ziele, denke ich, dass die Fruchterman-Reingold algorithm eine ziemlich gute Arbeit der Vermeidung von Kantenüberlappung tut. Siehe zum Beispiel dieses screenshot eines Netzwerks, das aus mehreren Komponenten besteht, die unter Verwendung des Fruchterman-Reingold-Algorithmus gezeichnet wurden. hat eingebaute Unterstützung für diesen Algorithmus (wie glaube ich Networkx) und ist wirklich schnell.

Answer 4

Organisches Layout verwaltet relativ gut gruppierte Graphen im yFiles-Framework. Versuchen Sie zuerst in yEd, um zu sehen, ob es was benötigt. Es ist wahrscheinlich sinnvoll, Aliasgruppen mit verschachtelten Diagrammen für jeden Cluster zu verwenden. Das organische Layout verfügt über eine Funktion namens Gruppenlayout-Richtlinie, die verwendet werden kann, wenn das Layout unter Verwendung unterschiedlicher Prinzipien für Inter-Cluster- und Intra-Cluster-Kanten mit inkrementeller Layoutgestaltung erfolgen soll. Mit etwas Aufwand kann man Graph in GraphML übersetzen, um manuelle Arbeit zu vermeiden.

Answer 5

Es gibt ein Programm auf der Oberseite von Prefuse namens SocialAction. Sie müssen den Code vom Autor anfordern, aber er führt viele statistische Analysen für Sie durch, z. B. die Identifizierung von Untergraphen.Ich habe es in einem Diagramm mit mehr als 18.000 Knoten verwendet, und obwohl es in diesem Maßstab sehr langsam ist, funktioniert es immer noch.

Answer 6

Obwohl es albern sein könnte, an dieser Stelle zu fragen, hatten Sie http://www.graphviz.org/ ausprobiert?