Wizualizacja bardzo dużych wykresów linków

25

Szukam narzędzia do wizualizacji bardzo dużych grafów linków kierunkowych. Obecnie mam ~ 2 miliony węzłów z ~ 10 milionami krawędzi. Próbowałem kilku różnych rzeczy, ale większość zajmuje nawet godziny, aby zrobić nawet 100 000 wykresów węzłów

Co próbowałem:
spędziłem dzień z gephi, ale dodanie węzłów 80K zajmuje około godziny, a aplikacja staje się w większości bezużyteczna.

Jakieś sugestie?

Interaktywna wizualizacja byłaby plusem.

visualization madmaze
źródło
Byłoby pomocne, gdybyś stwierdził, co już próbowałeś. Dałeś szansę Graphvizowi?
Wolfgang Bangerth,
1
Najpierw spróbuję Graphviz. Nie mam pojęcia, czy będzie to działać z czymś takiego rozmiaru. Oczywiście potrzebujesz czegoś, co używa rzadkiej reprezentacji macierzy przylegania, ale wydaje się niewyobrażalne, że pakiet oprogramowania nie.
David Ketcheson,
Daję teraz szansę Graphvizowi, wygląda to trochę bardziej obiecująco, ale nie sądzę, że pozwala na interakcję
madmaze
2
Czy próbowałeś interpretować wykres jako rzadką macierz i wizualizować go za pomocą MATLAB lub funkcji „szpiegowskiej” Octave'a? 10 milionów niezerowych wpisów znajduje się w zasięgu umiarkowanie wydajnych komputerów stacjonarnych. Ustawiłoby to również cię na bisekcję spektralną (znalezienie partycji wykresu może ułatwić ci wizualizację).
Jack Poulson,
1
zaglądałeś na wizytę?
pyCthon

Odpowiedzi:

13

Graphviz powinien działać. Uważam, że obrazy związane z matrycami w kolekcji rzadkich matryc University of Florida zostały zwizualizowane za pomocą sfdp, algorytmu wizualizacji grafu kierowanego siłą opracowanego przez Yifana Hu. Większość macierzy w kolekcji ma czas obliczeniowy związany z generowaniem odpowiedniej wizualizacji, więc możesz być w stanie wyszukać macierze, których wykresy mają cechy podobne do tych, które chcesz wizualizować. Na przykład, wykres z ~ 2,1 miliona węzłów i ~ 3 milionami krawędzi zajęło Hu ~ 36000s, czyli 10 godzin. Chociaż nie jest jasne, jakiego sprzętu użyto do wygenerowania wykresu, prawdopodobnie rozsądne jest przypuszczenie, że użyto komputera stacjonarnego lub laptopa, a czasy przynajmniej dałoby przybliżone wyobrażenie o tym, ile czasu może zająć renderowanie wykresu. Algorytm Hu wydaje się być jednym z najnowocześniejszych algorytmów wizualizacyjnych (opublikował go w 2005 r.), Ale nie będąc ekspertem w tej dziedzinie, nie mogę powiedzieć, czy istnieją lepsze algorytmy. Algorytm ten jest dołączony do Graphviz jako opcja i jest przeznaczony do stosowania na dużych wykresach, takich jak ten, który opisujesz.

Geoff Oxberry
źródło
Bardzo schludny. Wygląda na to, że Barnes-Hut jest używany do symulacji sił między węzłami wykresu, więc zakładam, że równoległa implementacja FMM może przynieść znaczne przyspieszenie. Z drugiej strony wydaje się, że metoda Hu ma wielopoziomową strukturę podobną do MeTiS, która jest trudna do zrównoleglenia.
Jack Poulson,
Tak, kiedy spojrzałem na artykuł, pomyślałem również, że równoległa implementacja FMM może być interesująca, ale nie byłam pewna, jak praktyczna byłaby, ponieważ nie mam dużego doświadczenia z równoległymi algorytmami.
Geoff Oxberry
3
@JackPoulson - kaszel
Aron Ahmadia
@GeoffOxberry - patrz link powyżej
Aron Ahmadia
1
@JackPoulson - Przekonasz się, że algorytmy układu kierowanego siłą są dość wrażliwe na początkowe inicjowanie, inne grupy wykonały dobrą pracę, aby przeformułować problem w celu uzyskania bardziej estetycznych układów.
Aron Ahmadia,
5

Zobacz Graphinsight 1.2, może z łatwością obsługiwać milion węzłów i jest interaktywny oraz w 3D.

Możesz także układać wykresy z milionem węzłów i krawędzi za pomocą wysokowydajnych metod algebraicznych lub metod ukierunkowanych siłowo. Jest dostępny w wersji próbnej do oceny ( Oświadczenie: Jestem jednym z autorów programu ).

www.graphinsight.com

linello
źródło
1
@linelio - Dziękujemy za odpowiedź i zapraszamy do scicomp! Przeczytaj zasady dotyczące promocji i upewnij się, że podczas ujawniania rekomendacji wyraźnie ujawniasz swoje osobiste powiązania.
Aron Ahmadia
5

Oto niektóre rekomendacje i linki zebrane w czasie:

  • W przypadku węzłów 2M trudno jest polecić cokolwiek, co nie zna twojego sprzętu, i być może trzeba zmniejszyć ilość danych, ale biorąc pod uwagę rzeczy, które są swobodnie dostępne, zGrViewer może zaspokoić twoje potrzeby wizualizacji (wymaga GraphViz).
  • Zgodnie z pomysłem @pyCthon zasugeruj, abyś również spojrzał na VisIt, aby zobaczyć interaktywność podczas kreślenia.
  • Odwiedzam ponownie igraphpakiet dla języka statystycznego R , który obejmuje między innymi zgrabne algorytmy układu ( Fruchterman-Reingold i Kamada-Kawai ).
  • Biblioteka dużego układu graficznego jest teraz dostępna w SourceForge.
Łowca jeleni
źródło
0

Tworzymy http://www.github.com/graphistry/pygraphistry, aby umożliwić to w większości przeglądarek i notebooków. Pomysł polega na użyciu WebGL do renderowania dużych wykresów (panoramowanie / powiększanie / itp.) I przeniesienia większości obliczeń w czasie rzeczywistym (układ, filtr itp.) Do chmury GPU. Jest podobny do Gephi lub Cytoscape, ale z większym naciskiem na duże wykresy i analizę danych oraz integrację z Internetem i notebookami.

Leo Meyerovich
źródło
0

Możesz wypróbować „Tulipana” [1], myślę, że może on obsługiwać dość duże wykresy (przynajmniej wypróbowałem go z węzłami od 10 do 100 000 i działało dobrze).

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

BrunoLevy
źródło