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
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.