Diseño de Gráficos Interactivos de un Millón de Nodos
Autores: Mi, Peng; Sun, Maoyuan; Masiane, Moeti; Cao, Yong; North, Chris
Idioma: Inglés
Editor: MDPI
Año: 2016
Acceso abierto
Artículo científico
2016
Diseño de Gráficos Interactivos de un Millón de Nodos
Categoría
Gestión y administración
Subcategoría
Gestión de la tecnología y la inovación
Palabras clave
Gráficas grandes
Comprensión
Algoritmos interactivos
Basados en GPU
Diseño dirigido por fuerzas
Escalabilidad
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 1
Citaciones: Sin citaciones
La comprensión de grandes grafos, específicamente aquellos con millones de nodos, es una tarea crucial en muchos campos. Los algoritmos automáticos de diseño de grafos, aumentados con interacción humana en tiempo real, pueden potencialmente apoyar la comprensión de grandes grafos. Sin embargo, diseñar algoritmos interactivos para lograr esto es un desafío. En este artículo, abordamos el problema de escalabilidad del diseño interactivo de grandes grafos y contribuimos con un nuevo algoritmo de diseño dirigido por fuerzas basado en GPU que explota la topología del grafo. Este algoritmo puede diseñar interactivamente grafos con millones de nodos y soportar interacción en tiempo real para explorar diseños alternativos de grafos. Los usuarios pueden manipular directamente el diseño de los vértices de manera dirigida por fuerzas. La complejidad del cálculo de fuerzas repulsivas tradicionales se reduce al aproximar cálculos basados en la estructura jerárquica de grafos agrupados de múltiples niveles. Evaluamos el rendimiento del algoritmo y demostramos el diseño con intervención humana en dos estudios de caso de comprensión. Además, resumimos las lecciones aprendidas para diseñar algoritmos de diseño de grandes grafos interactivos en la GPU.
Descripción
La comprensión de grandes grafos, específicamente aquellos con millones de nodos, es una tarea crucial en muchos campos. Los algoritmos automáticos de diseño de grafos, aumentados con interacción humana en tiempo real, pueden potencialmente apoyar la comprensión de grandes grafos. Sin embargo, diseñar algoritmos interactivos para lograr esto es un desafío. En este artículo, abordamos el problema de escalabilidad del diseño interactivo de grandes grafos y contribuimos con un nuevo algoritmo de diseño dirigido por fuerzas basado en GPU que explota la topología del grafo. Este algoritmo puede diseñar interactivamente grafos con millones de nodos y soportar interacción en tiempo real para explorar diseños alternativos de grafos. Los usuarios pueden manipular directamente el diseño de los vértices de manera dirigida por fuerzas. La complejidad del cálculo de fuerzas repulsivas tradicionales se reduce al aproximar cálculos basados en la estructura jerárquica de grafos agrupados de múltiples niveles. Evaluamos el rendimiento del algoritmo y demostramos el diseño con intervención humana en dos estudios de caso de comprensión. Además, resumimos las lecciones aprendidas para diseñar algoritmos de diseño de grandes grafos interactivos en la GPU.