Memvisualisasikan grafik tautan yang sangat besar

25

Saya mencari alat untuk memvisualisasikan grafik tautan searah yang sangat besar. Saat ini saya memiliki ~ 2 juta node dengan ~ 10 juta tepi. Saya telah mencoba beberapa hal yang berbeda, tetapi kebanyakan membutuhkan waktu berjam-jam untuk bahkan melakukan grafik simpul 100k

Apa yang saya coba:
Saya menghabiskan satu hari dengan gephi, tetapi 80 ribu node membutuhkan waktu sekitar satu jam untuk ditambahkan dan aplikasi menjadi tidak berguna.

Ada saran?

Visualisasi interaktif akan menjadi nilai tambah.

visualization madmaze
sumber
Akan membantu jika Anda menyatakan apa yang sudah Anda coba. Apakah Anda mencoba Graphviz?
Wolfgang Bangerth
1
Graphviz adalah apa yang akan saya coba pertama kali. Tidak tahu apakah itu akan bekerja dengan sesuatu yang sebesar itu. Jelas Anda akan membutuhkan sesuatu yang menggunakan representasi jarang untuk matriks adjacency, tetapi tampaknya tidak terbayangkan bahwa paket perangkat lunak tidak akan.
David Ketcheson
Saya memberikan Graphviz suntikan sekarang, itu terlihat sedikit lebih menjanjikan, tapi saya rasa itu tidak memungkinkan untuk interaksi
madmaze
2
Sudahkah Anda mencoba menafsirkan grafik sebagai matriks jarang dan memvisualisasikannya dengan MATLAB atau fungsi 'mata-mata' Oktaf? 10 juta entri bukan nol berada dalam jangkauan desktop yang cukup kuat. Ini juga akan mengatur Anda untuk membagi dua spektral (menemukan partisi grafik Anda mungkin membuatnya lebih mudah bagi Anda untuk memvisualisasikannya).
Jack Poulson
1
sudahkah Anda melihat kunjungan?
pyCthon

Jawaban:

13

Graphviz harus bekerja. Saya percaya bahwa gambar yang terkait dengan matriks dalam koleksi matriks University of Florida jarang divisualisasikan menggunakan sfdp, algoritma visualisasi grafik gaya-diarahkan yang dikembangkan oleh Yifan Hu. Sebagian besar matriks dalam koleksi memiliki waktu komputasi yang terkait dengan menghasilkan visualisasi yang sesuai, sehingga Anda mungkin dapat mencari matriks yang grafiknya memiliki karakteristik yang mirip dengan yang ingin Anda visualisasikan. Sebagai contoh, grafik dengan ~ 2,1 juta node dan ~ 3 juta edge membutuhkan Hu ~ 36000s untuk menghasilkan, atau 10 jam. Meskipun tidak jelas perangkat keras apa yang digunakan untuk menghasilkan grafik, mungkin merupakan perkiraan yang masuk akal bahwa desktop atau laptop digunakan, dan waktu setidaknya akan memberi Anda gambaran kasar tentang berapa banyak waktu yang dibutuhkan untuk membuat grafik. Algoritma Hu tampaknya menjadi salah satu algoritma visualisasi canggih (ia menerbitkannya pada 2005), tetapi tidak menjadi ahli di bidangnya, saya tidak dapat berbicara apakah ada algoritma yang lebih baik atau tidak. Algoritma ini disertakan dengan Graphviz sebagai opsi, dan dirancang untuk digunakan pada grafik besar seperti yang Anda gambarkan.

Geoff Oxberry
sumber
Sangat rapi. Sepertinya Barnes-Hut sedang digunakan untuk mensimulasikan kekuatan antara node grafik, jadi saya akan berasumsi bahwa implementasi FMM paralel mungkin menghasilkan percepatan yang signifikan. Di sisi lain, metode Hu tampaknya memiliki struktur bertingkat yang mirip dengan MeTiS, yang cenderung sulit diparalelkan.
Jack Poulson
Ya, ketika saya melihat makalahnya, saya juga berpikir implementasi FMM paralel mungkin menarik, tetapi saya tidak yakin seberapa praktisnya, karena saya tidak punya banyak pengalaman dengan algoritma paralel.
Geoff Oxberry
3
@JackPoulson - cough
Aron Ahmadia
@ GeoffOxberry - lihat tautan di atas
Aron Ahmadia
1
@JackPoulson - Anda akan menemukan bahwa algoritma tata letak yang diarahkan secara paksa cukup sensitif terhadap penyemaian awal, ada beberapa pekerjaan bagus yang dilakukan oleh kelompok lain untuk merumuskan kembali masalah untuk tata letak yang lebih estetis.
Aron Ahmadia
5

Lihat Graphinsight 1.2, dapat menangani jutaan node dengan mudah dan interaktif dan dalam 3D.

Anda juga dapat mengatur grafik dengan jutaan node dan tepi dengan metode aljabar efisien tinggi atau metode gaya terarah. Ini tersedia dalam versi percobaan untuk evaluasi ( Penafian: Saya adalah salah satu penulis program ).

www.graphinsight.com

linello
sumber
1
@linelio - Terima kasih atas jawaban Anda dan selamat datang di scicomp! Harap lihat peraturan tentang promosi dan pastikan bahwa Anda dengan jelas mengungkapkan koneksi pribadi ketika membuat rekomendasi.
Aron Ahmadia
5

Berikut adalah beberapa rekomendasi dan tautan yang dikumpulkan dari waktu ke waktu:

  • Untuk node 2M sulit untuk merekomendasikan apa pun yang tidak mengetahui perangkat keras Anda, dan mungkin beberapa pengurangan data dilakukan, tetapi mengambil barang-barang yang tersedia secara bebas, zGrViewer mungkin sesuai dengan kebutuhan Anda untuk visualisasi (memerlukan GraphViz).
  • Mengikuti ide @pyCthon, menyarankan Anda juga melihat VisIt untuk beberapa interaktivitas dalam merencanakan.
  • Saya mengunjungi kembali igraphpaket untuk bahasa statistik R , yang mencakup algoritma tata letak yang rapi ( Fruchterman-Reingold dan Kamada-Kawai ), antara lain.
  • Pustaka Layout Grafik Besar sekarang ada di SourceForge.
Pemburu rusa
sumber
0

Kami telah membuat http://www.github.com/graphistry/pygraphistry untuk memungkinkan melakukan hal ini dari sebagian besar browser dan notebook. Idenya adalah menggunakan WebGL untuk merender grafik besar (pan / zoom / dll.), Dan melepas sebagian besar komputasi waktu nyata (tata letak, filter, dll.) Ke cloud GPU. Ini mirip dengan Gephi atau Cytoscape, tetapi dengan lebih fokus pada grafik besar dan analisis data, dan mengintegrasikan ke dalam web dan notebook.

Leo Meyerovich
sumber
0

Anda dapat mencoba "Tulip" [1], saya pikir itu dapat menangani grafik yang cukup besar (setidaknya saya mencobanya dengan 10K hingga 100K node dan itu bekerja dengan baik).

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

BrunoLevy
sumber