2008-10-26 19 views
69

Necesito consejos para representar un gráfico no dirigido con 178,000 nodos y 500,000 bordes. He probado Neato, Tulip y Cytoscape. Neato ni siquiera se acerca remotamente, y Tulip y Cytoscape afirman que pueden manejarlo pero no parecen poder hacerlo. (Tulip no hace nada y Cytoscape dice que está trabajando, y luego simplemente se detiene.)Visualizar gráfico no dirigido que es demasiado grande para GraphViz?

Me gustaría simplemente un archivo de formato vectorial (ps o pdf) con un diseño remotamente razonable de los nodos.

+51

Dibuja un cuadrado pequeño y colorea todo en negro. :-) Lo siento, no pude resistirme. – tvanfosson

+0

¿Qué tipo de datos representa este gráfico? Tal vez, ¿puedes simplificarlo automáticamente? Es solo mi suposición: no tengo información sobre los datos representados, por lo que es difícil de adivinar. De todos modos, muchos nodos y bordes no serán muy expresivos en una sola hoja de papel ... – avp

+1

¿Cuán grande es el PDF que está esperando, algo en mosaico en varias hojas de A3? –

Respuesta

0

Una herramienta de Windows que puede visualizar gráficos es pajek, genera una salida de eps, sin embargo, no sé si puede leer sus datos.

1

Puede ofrecer una versión desinfectada del archivo a los desarrolladores de esas herramientas como un escenario de depuración, si todo lo demás falla.

4

Mathematica podría muy bien manejarlo, pero tengo que admitir que mi primera reacción fue en la línea del comentario que decía "toma una hoja de papel y pégalo de color negro". ¿No hay forma de reducir la densidad del gráfico?

Un posible problema es que parece que está buscando el diseño, no solo la representación. No tengo conocimiento sobre las características de Big O de los diseños implementados por varias herramientas, pero intuitivamente supongo que podría tomar un tiempo largo para disponer esa cantidad de datos.

+4

Mathematica no maneja bien los gráficos muy grandes, ni siquiera la versión 8 con muchos integrados -en funciones de procesamiento de gráficos. La mayor dificultad es que no expone el algoritmo de diseño independientemente del trazado, y su representación gráfica es demasiado lenta como para manejar cómodamente estos muchos bordes. – Szabolcs

0

Hay una lista de las aplicaciones aquí: http://www.mkbergman.com/?p=414

morsa y LGL son dos herramientas supuestamente adecuado para grandes gráficos. Sin embargo, parece que ambos requieren que los gráficos se ingresen como archivos de texto en su propio formato especial, lo que podría ser un problema.

3

¿Tiene que ser realmente exacto?

Dependiendo de lo que intente lograr, podría ser suficiente con graficar el 10% o el 1% del volumen de datos. (Por supuesto, también podría ser completamente inútil, pero todo depende de para qué sirve la visualización)

20

Sugiero que primero haga un preprocesamiento de los datos, por ejemplo, colapsando nodos en clústeres y luego visualizando los clústeres. El colapso reducirá la cantidad de nodos y facilitará que algoritmos como Kamada-Kawai o Fruchterman-Reingold representen el gráfico resultante.

Si realmente necesita visualizar 500,000 nodos, entonces puede considerar usar un diseño circular simple. Esto será fácil de renderizar sin los problemas que tienen los algoritmos basados ​​en la fuerza.Eche un vistazo a Circos: http://mkweb.bcgsc.ca/circos/

Circos es una visualización gráfica desarrollada por personas de la bioinformática que está diseñada para visualizar genomas y otros conjuntos de datos extremadamente grandes y complejos.

Es un paquete basado en PERL, espero que no sea problemático.

1

Large Graph Layout (LGL) proyecto me ayudó mucho con un ptoblema similar. Maneja el diseño y tiene una pequeña aplicación java para dibujar diseños producidos en 2D. No hay salida de vector fuera de la caja por lo que tendrá que dibujar el gráfico usted mismo (dadas las coordenadas del nodo producidas por LGL)

+0

El enlace está roto a partir de 7/2013 – samoz

0

También puede probar NAViGaTOR (revelación: soy uno de los desarrolladores de ese software) . Hemos visualizado gráficos con hasta 1,7 millones de bordes con éxito. Aunque estas redes tan grandes son difíciles de manipular (la interfaz de usuario se ralentizará). Sin embargo, utiliza OpenGL para la visualización, por lo que parte de la carga se transfiere a la tarjeta gráfica.

También tenga en cuenta que deberá subir la configuración de la memoria en el cuadro de diálogo Archivo-> Preferencias antes de poder abrir con éxito una red tan grande.

Finalmente, como la mayoría de las otras respuestas indican, es mejor reorganizar sus datos en algo más pequeño y más significativo.

11

Pruebe Gephi, tiene un nuevo complemento de diseño llamado OpenOrd que se adapta a millones de nodos.

26

Graphviz en sí proporciona una solución para la representación de gráficos de gran tamaño.

Es decir, Graphviz incluye sfdp, una versión multiescala de fdp (también en graphviz, similar a neato) para el diseño de grandes gráficos no dirigidos que ha sido útil para dibujar gráficos grandes (70k nodos, 500k bordes) en mi proyecto.

Puede encontrar documentación de este software en el sitio web graphviz sí en http://www.graphviz.org/

Más información, un documento que describe las técnicas y ejemplos subyacentes se puede encontrar aquí: http://yifanhu.net/PUB/graph_draw_small.pdf

+0

Esta fue la solución más simple a la falla de networkx/graphviz, ¡gracias! – styts

+1

El enlace al documento ahora está roto. ¿Podría incluir el título del documento para que otros puedan rastrearlo en el futuro? – JustinJDavies

+0

Creo que esta es la nueva ubicación del periódico: http://www2.research.att.com/~yifanhu/PUB/graph_draw_small.pdf "Dibujo de gráficos dirigidos por fuerza eficientes y de alta calidad" por Yifan Hu. Puede encontrar más información aquí: http://www2.research.att.com/~yifanhu/SOFTWARE/SFDP/index.html –

0

En primer lugar, me gustaría a la sugerencia de los segundos aliekens para probar sfdp. Es la versión a gran escala de Neato.

Como OJW sugiere que también podría trazar los nodos en R2. Tus bordes realmente proveen lo que él llama un "orden natural". En particular, puede trazar los componentes del segundo y tercer vectores propios del gráfico normalizado Laplaciano. Esta es la matriz L en this wikipedia page about spectral clustering. Debería poder escribir esta matriz sin entender el álgebra lineal detrás de ella. Luego, ha reducido su problema para calcular aproximadamente los primeros vectores propios de una gran matriz dispersa. Esto se realiza tradicionalmente mediante métodos iterativos y se implementa en paquetes de álgebra lineal estándar. Este método debería escalar hasta gráficos muy grandes.

16

He tenido buenos resultados utilizando la biblioteca graph-tool en python. El siguiente gráfico tiene 1.490 nodos y 19.090 bordes: tardó alrededor de 5 minutos en renderizar en mi computadora portátil.

datos

political blogging network

El gráfico proviene de la red de blogs política descrita por adámica y la mirada en el enlace “The political blogosphere and the 2004 US Election” pdf here. Si amplía, puede ver las URL del blog para cada nodo.

zoomed

Aquí está el código que solía dibujar (blog http://ryancompton.net/2014/10/22/stochastic-block-model-based-edge-bundles-in-graph-tool/):

import graph_tool.all as gt 
import math 

g = gt.collection.data["polblogs"] # http://www2.scedu.unibo.it/roversi/SocioNet/AdamicGlanceBlogWWW.pdf 
print(g.num_vertices(), g.num_edges()) 

#reduce to only connected nodes 
g = gt.GraphView(g,vfilt=lambda v: (v.out_degree() > 0) and (v.in_degree() > 0)) 
g.purge_vertices() 

print(g.num_vertices(), g.num_edges()) 

#use 1->Republican, 2->Democrat 
red_blue_map = {1:(1,0,0,1),0:(0,0,1,1)} 
plot_color = g.new_vertex_property('vector<double>') 
g.vertex_properties['plot_color'] = plot_color 
for v in g.vertices(): 
    plot_color[v] = red_blue_map[g.vertex_properties['value'][v]] 

#edge colors 
alpha=0.15 
edge_color = g.new_edge_property('vector<double>') 
g.edge_properties['edge_color']=edge_color 
for e in g.edges(): 
    if plot_color[e.source()] != plot_color[e.target()]: 
     if plot_color[e.source()] == (0,0,1,1): 
      #orange on dem -> rep 
      edge_color[e] = (255.0/255.0, 102/255.0, 0/255.0, alpha) 
     else: 
      edge_color[e] = (102.0/255.0, 51/255.0, 153/255.0, alpha)    
    #red on rep-rep edges 
    elif plot_color[e.source()] == (1,0,0,1): 
     edge_color[e] = (1,0,0, alpha) 
    #blue on dem-dem edges 
    else: 
     edge_color[e] = (0,0,1, alpha) 

state = gt.minimize_nested_blockmodel_dl(g, deg_corr=True) 
bstack = state.get_bstack() 
t = gt.get_hierarchy_tree(bstack)[0] 
tpos = pos = gt.radial_tree_layout(t, t.vertex(t.num_vertices() - 1), weighted=True) 
cts = gt.get_hierarchy_control_points(g, t, tpos) 
pos = g.own_property(tpos) 
b = bstack[0].vp["b"] 

#labels 
text_rot = g.new_vertex_property('double') 
g.vertex_properties['text_rot'] = text_rot 
for v in g.vertices(): 
    if pos[v][0] >0: 
     text_rot[v] = math.atan(pos[v][1]/pos[v][0]) 
    else: 
     text_rot[v] = math.pi + math.atan(pos[v][1]/pos[v][0]) 

gt.graph_draw(g, pos=pos, vertex_fill_color=g.vertex_properties['plot_color'], 
      vertex_color=g.vertex_properties['plot_color'], 
      edge_control_points=cts, 
      vertex_size=10, 
      vertex_text=g.vertex_properties['label'], 
      vertex_text_rotation=g.vertex_properties['text_rot'], 
      vertex_text_position=1, 
      vertex_font_size=9, 
      edge_color=g.edge_properties['edge_color'], 
      vertex_anchor=0, 
      bg_color=[0,0,0,1], 
      output_size=[4024,4024], 
      output='polblogs_blockmodel.png') 
2

BioFabric (www.BioFabric.org) es otra herramienta para visualizar gráficos grandes. Debería poder manejar la red descrita (178,000 nodos y 500,000 bordes) OK, aunque el diseño inicial puede tomar un tiempo. Con las redes de aquí (del conjunto de datos Colección Stanford Red grande) es la Red de Web de Stanford, que tiene 281,903 nodos y 2,312,497 bordes: escalabilidad

Stanford Web Network de BioFabric se debe al hecho de que representa los nodos no como puntos, pero como lineas horizontales. Los bordes se muestran como líneas verticales. Para cierta intuición sobre cómo funciona esto, está el Super-Quick BioFabric Demo, que es una red pequeña que se anima con D3.

La aplicación principal está escrita en Java. Por el momento, solo puede exportar imágenes PNG, no archivos PDF. Existe una opción de exportación de PDF desde RBioFabric, aunque es una implementación muy simple que aún no puede manejar redes realmente grandes.

Descripción completa: BioFabric es una herramienta que escribí.

Cuestiones relacionadas