¿Cuál es el motor gráfico de red dirigido a la fuerza más rápido para grandes conjuntos de datos?

Question

Actualmente tenemos un gráfico de red actualizado dinámicamente con alrededor de 1.500 nodos y 2,000 bordes. Está en constante crecimiento. Nuestro motor de diseño actual usa Prefuse - el diseño dirigido a la fuerza en particular - y toma aproximadamente 10 minutos con un servidor fuerte para obtener un diseño agradable y estable.

He mirado algoritmo de policía de San Francisco un poco GraphViz 's, pero no han probado todavía ...

¿Hay alternativas más rápidas que debo mirar?

• que no se preocupan por la apariencia visual de los nodos y bordes - procesamos que por separado - sólo poner x, y en los nodos.
• Necesitamos poder jugar con las propiedades de diseño para partes específicas del gráfico, por ejemplo, aplicando muelles más ajustados o flojos para ciertos nodos.

Gracias de antemano, y por favor comenten si necesitan información más específica para responder!

EDIT: Estoy particularmente buscando comparaciones de velocidad entre las opciones de motor de diseño. ¡Los puntos de referencia, los ejemplos específicos, o simplemente la experiencia personal serían suficientes!

Answer 1

Me gustaría echar un vistazo a OGDF, específicamente http://www.ogdf.net/doku.php/tech:howto:frcl No he utilizado OGDF, pero sí sé que Fast multipolar multinivel es un buen algoritmo performant y cuando usted está tratando con los tipos de tiempos de ejecución que participan en el diseño fuerza dirigida con la cantidad de nodos que quieras, eso importa mucho. Por qué, entre otras razones, ese algoritmo es asombroso: Método Multipolar rápido. El método multipolar rápido es una aproximación de multiplicación matricial que reduce el tiempo de ejecución O() de la multiplicación de matrices para una aproximación en un grado pequeño. Idealmente, tendrías código de algo como esto: http://mgarland.org/files/papers/layoutgpu.pdf pero no puedo encontrarlo en ningún lado; tal vez una solución CUDA no esté de tu lado de todos modos.

Buena suerte.

Answer 2

Me gustaría echarle un vistazo a http://neo4j.org/ su código abierto que es beneficioso en su caso para que pueda personalizarlo para sus necesidades. La cuenta de github se puede encontrar here.

Answer 3

El Gephi Toolkit podría ser lo que necesita: algunos diseños son muy rápida pero con una buena calidad: http://gephi.org/toolkit/

30 secondes a 2 minutos son suficientes para diseño de un gráfico de este tipo, dependiendo de su máquina. Puede usar el diseño ForAtlas o el diseño Multinivel Yifan Hu.

Por muy grandes gráficos (+ 50K nodos y enlaces) 500K, el diseño Wil OpenOrd

Answer 4

escribí un gráfico basado en JavaScript dibujo biblioteca VivaGraph.js.

Calcula el diseño y representa el gráfico con 2K + vértices, 8.5K bordes en ~ 10-15 segundos. Si no necesita renderizar una parte, debería ser aún más rápido.

Aquí hay un video que lo demuestra en acción: WebGL Graph Rendering With VivaGraphJS.

Demostración en línea está disponible here. Se requiere WebGL para ver la demostración, pero no es necesario para calcular los diseños de gráficos. La biblioteca también funciona bajo node.js, por lo tanto podría usarse como un servicio.

Ejemplo de uso de la API (diseño solamente):

var graph = Viva.Graph.graph(), 
    layout = Viva.Graph.Layout.forceDirected(graph); 

graph.addLink(1, 2); 
layout.run(50); // runs 50 iterations of graph layout 

// print results: 
graph.forEachNode(function(node) { console.log(node.position); }) 

Espero que esto ayude :)

Answer 5

En un escenario comercial, también puede ser que desee mirar a la familia de las bibliotecas de diseño y visualización de gráficos yFiles .

Incluso el JavaScript version de él puede realizar diseños para miles de nodos y bordes con diferentes estilos de disposición. El estilo de diseño "orgánico" es una implementación de un algoritmo de diseño dirigido por fuerza de naturaleza similar a la utilizada en la aplicación de navegador de Neo4j. Pero hay muchos más algoritmos de disposición disponibles que pueden proporcionar mejores visualizaciones para ciertos tipos de estructuras de gráficos y diagramas. Dependiendo de la configuración y la estructura del problema, algunos de los algoritmos toman solo unos segundos, mientras que las implementaciones más complejas también pueden hacer que su motor de JavaScript se ponga de rodillas. Las variantes basadas en Java y .NET todavía funcionan un poco mejor, a partir de hoy, pero los motores de JavaScript se están poniendo al día.

Puede jugar con estos algoritmos y configuraciones en this online demo.

^{Descargo de responsabilidad: Yo trabajo para yWorks, que es el fabricante de estas bibliotecas, pero no represento a mi empleador en SO.}