Wizualizacja grafów

Michał Stachurski

Wizualizacja grafów

dużych (kilka tysięcy lub kilkadziesiąt tysięcy wierzchołków)

Wizualizacja grafów

ustalanie pozycji wierzchołków na płaszczyźnie
ustalenie wyglądu elementów grafu i stworzenie obrazu (animacji)

Layout grafu

Fruchterman-Reingold

wierzchołki - odpychające się cząsteczki, krawędzie - sprężyny
globalna temperatura układu
O(N²⁾ - do 1000 wierzchołków

źródło: https://gephi.org/tutorials/gephi-tutorial-layouts.pdf

OpenOrd

bazuje na Fruchterman-Reingold
symulowane wyżarzanie
przecinanie długich krawędzi
O(N*log(N)) - do 1 000 000 wierzchołków

źródło: https://gephi.org/tutorials/gephi-tutorial-layouts.pdf

OpenOrd

Inne algorytmy layoutu

wielopoziomowe/hierarchiczne
układ kołowy
układ drzewa

Narzędzia

Gephi

The Open Graph Viz Platform Gephi is an interactive visualization and exploration platform for all kinds of networks and complex systems, dynamic and hierarchical graphs.

Gephi

grafy do 1 000 000 wierzchołków i krawędzi
dynamiczne grafy
pluginy (metryki, layouty, filtry, źródła danych)
interfejs bazujący na NetBeans UI
obsługa Neo4j
różnorodność algorytmów layoutu

Cytoscape

głównie dla biologów
różnorodność algorytmów layoutu
wiele opcji dostosowania wyglądu grafu

Biblioteki

GraphStream

A Dynamic Graph Library

GraphStream

biblioteka dla Javy
zapewnia reprezentację statycznych i dynamicznych grafów:
- w pamięci
- na ekranie
- w plikach
zmiany w czasie mogą dotyczyć zarówno topologii grafu (dodanie/usunięcie wierzchołków/krawędzi) jak i dowolnych atrybutów wierzchołków lub krawędzi
CSS do definiowania wyglądu grafu
tylko jeden algorytm liczenia layoutu grafu

JUNG

Java Universal Network/Graph Framework

Biblioteka Javy z algorytmami grafowymi (layout, metryki, scoring, ...) oraz prostym modułem wizualizacji

GEXF

Format XML reprezentacji grafu

atrybuty
grafy dynamiczne
grafy hierarchiczne
wizualizacja: układ, kolory, ...
obsługiwany przez Gephi i GraphStream

Protovis

dziękuję

← → #