Visualizando gráficos de enlaces muy grandes

25

Estoy buscando una herramienta para visualizar gráficos de enlaces direccionales muy grandes. Actualmente tengo ~ 2 millones de nodos con ~ 10 millones de bordes. He intentado algunas cosas diferentes, pero la mayoría toma horas incluso para hacer gráficos de 100k nodos

Lo que he intentado:
pasé un día con gephi, pero los nodos de 80K tardan aproximadamente una hora en agregarse y la aplicación se vuelve inútil.

¿Alguna sugerencia?

Una visualización interactiva sería una ventaja.

visualization laberinto
fuente
Sería útil si declaras lo que ya intentaste. ¿Le diste una oportunidad a Graphviz?
Wolfgang Bangerth
1
Graphviz es lo que intentaría primero. No tengo idea de si funcionará con algo de ese tamaño. Obviamente necesitará algo que use una representación escasa para la matriz de adyacencia, pero parece inimaginable que un paquete de software no lo haga.
David Ketcheson
Estoy dando Graphviz un tiro en este momento, se ve un poco más prometedor, pero yo no creo que permite la interacción
madmaze
2
¿Has intentado interpretar el gráfico como una matriz dispersa y visualizarlo con MATLAB o la función 'espía' de Octave? 10 millones de entradas distintas de cero están al alcance de los escritorios moderadamente potentes. Esto también lo prepararía para la bisección espectral (encontrar particiones de su gráfico podría facilitarle la visualización).
Jack Poulson
1
has mirado en visita?
pyCthon

Respuestas:

13

Graphviz debería funcionar. Creo que las imágenes asociadas con las matrices en la colección de matriz dispersa de se visualizaron usando sfdp, un algoritmo de visualización de gráficos dirigido por la fuerza desarrollado por Yifan Hu. La mayoría de las matrices de la colección tienen un tiempo de cálculo asociado con la generación de una visualización correspondiente, por lo que es posible que pueda buscar matrices cuyas gráficas tengan características similares a las que desea visualizar. Por ejemplo, un gráfico con ~ 2.1 millones de nodos y ~ 3 millones de bordes tomó Hu ~ 36000s para generar, o 10 horas la Universidad de Florida . Si bien no está claro qué hardware se usó para generar el gráfico, es probable que sea una suposición razonable de que se usó una computadora de escritorio o portátil, y los tiempos al menos le darían una idea aproximada de cuánto tiempo puede tomar procesar el gráfico. El algoritmo de Hu parece ser uno de los algoritmos de visualización más modernos (lo publicó en 2005), pero al no ser un experto en el campo, no puedo hablar de si existen o no mejores algoritmos. Este algoritmo se incluye con Graphviz como una opción, y está diseñado para usarse en gráficos grandes como el que usted describe.

Geoff Oxberry
fuente
Muy aseado. Parece que Barnes-Hut se está utilizando para simular fuerzas entre los nodos del gráfico, por lo que supongo que una implementación paralela de FMM podría generar una aceleración significativa. Por otro lado, el método de Hu parece tener una estructura multinivel similar a MeTiS, que tiende a ser difícil de paralelizar.
Jack Poulson
Sí, cuando miré el documento, también pensé que una implementación de FMM paralela podría ser interesante, pero no estaba seguro de lo práctico que sería, ya que no tengo mucha experiencia con algoritmos paralelos.
Geoff Oxberry
3
@JackPoulson - tos
Aron Ahmadia
@GeoffOxberry - ver enlace arriba
Aron Ahmadia
1
@JackPoulson: encontrará que los algoritmos de diseño dirigidos a la fuerza son bastante sensibles a la siembra inicial, hubo otro buen trabajo realizado por otros grupos para reformular el problema para diseños más estéticos.
Aron Ahmadia
5

Vea Graphinsight 1.2, puede manejar con millones de nodos fácilmente y es interactivo y en 3D.

También puede diseñar gráficos con millones de nodos y bordes con métodos algebraicos altamente eficientes o métodos dirigidos a la fuerza. Está disponible en versión de prueba para evaluación ( Descargo de responsabilidad: soy uno de los autores del programa ).

www.graphinsight.com

linello
fuente
1
@linelio - ¡Gracias por tu respuesta y bienvenido a scicomp! Consulte las reglas sobre la promoción y asegúrese de revelar claramente cualquier conexión personal al hacer recomendaciones.
Aron Ahmadia
5

Aquí hay algunas recomendaciones y enlaces recopilados a lo largo del tiempo:

  • Para los nodos de 2M es difícil recomendar algo que no conozca su hardware, y posiblemente se requiera una reducción de datos, pero tomando cosas que están disponibles gratuitamente, zGrViewer puede satisfacer sus necesidades de visualización (requiere GraphViz).
  • Siguiendo la idea de @pyCthon, sugiero que también eche un vistazo a VisIt para encontrar cierta interactividad en el trazado.
  • Estoy volviendo a visitar el igraphpaquete para el lenguaje estadístico R , que incluye algoritmos de diseño ( Fruchterman-Reingold y Kamada-Kawai ), entre otros.
  • La biblioteca de diseño gráfico grande ahora está en SourceForge.
Cazador de ciervos
fuente
0

Hemos estado construyendo http://www.github.com/graphistry/pygraphistry para permitir hacer esto desde la mayoría de los navegadores y portátiles. La idea es usar WebGL para representar los gráficos grandes (panorámica / zoom / etc.) y descargar la mayor parte del cómputo en tiempo real (diseño, filtro, etc.) a una nube de GPU. Es similar a Gephi o Cytoscape, pero con un mayor enfoque en gráficos grandes y análisis de datos, y se integra en la web y los cuadernos.

Leo Meyerovich
fuente