tutorial nodesep mac graph-theory graphviz graph-layout

graph-theory - nodesep - graphviz>& lt



¿Visualizando un gráfico no dirigido que es demasiado grande para GraphViz? (17)

¿Necesita ser realmente preciso?

Dependiendo de lo que intente lograr, podría ser suficiente 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)

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).

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

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. El programa de la red aquí (de Stanford Large Network Dataset Collection) es Stanford Web Network, que tiene 281,903 nodos y 2,312,497 bordes:

La escalabilidad de BioFabric se debe al hecho de que representa los nodos no como puntos, sino como líneas horizontales. Los bordes se muestran como líneas verticales. Para tener un poco de intuición sobre cómo funciona esto, está la demostración Super-Quick BioFabric , que es una pequeña red 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.

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

Es muy probable que Mathematica lo maneje, pero debo admitir que mi primera reacción fue similar a la del comentario que decía "toma una hoja de papel y colorea el papel en negro". ¿No hay forma de reducir la densidad del gráfico?

Un posible problema es que parece estar buscando el diseño, no solo el renderizado. No tengo conocimiento acerca de las características de Big O de los diseños implementados por varias herramientas, pero intuitivamente supongo que podría tomar mucho tiempo diseñar esa cantidad de datos.

Graphviz en sí proporciona una solución para representar gráficos grandes.

A saber, 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 grandes gráficos (70k nodos, 500k bordes) en mi proyecto.

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

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

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

Walrus y LGL son dos herramientas supuestamente adecuadas para gráficos grandes. 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.

He obtenido buenos resultados al utilizar la biblioteca de 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.

Los datos del gráfico provienen de la red de blogs políticos descrita por Adamic y Glance en el enlace pdf "The political blogosphere and the 2004 US Election" here . Si amplía, puede ver las URL del blog para cada nodo.

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'')

Le 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 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.

Primero, quisiera hacer una segunda sugerencia de aliekens para probar sfdp. Es la versión a gran escala de Neato.

Como OJW sugiere, también podrías 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 esta página wikipedia sobre la agrupación espectral . 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.

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

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.

También puedes 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 señala la mayoría de las otras respuestas, es mejor que reorganices tus datos en algo más pequeño y más significativo.

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

El proyecto Large Graph Layout (LGL) 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)