Comenzaré con una respuesta que es absolutamente cierta y, sin embargo, no es útil, luego entraré en algunos de los detalles.
La mejor manera es la que revela la información que está buscando.
Como ya has descubierto, poner cualquier gráfico más grande que unos pocos cientos de nodos a través de un algoritmo de diseño dirigido por la fuerza de uso general te dará una bola de pelo. Solo hay un pequeño puñado de situaciones en las que este no es el caso porque eso es lo que son los gráficos grandes, especialmente aquellos que representan redes que son, en cierto sentido, sociales en lugar de geográficas.
- ¿Son defectuosos los números complejos?
- ¿Se puede descifrar algún código?
- ¿Cuándo son dos algoritmos isomorfos?
- ¿Por qué las matemáticas son mucho más difíciles que la programación?
- Me equivoqué completamente en mi examen de Matemática discreta. ¿Todavía podré ir a la escuela de posgrado?
Así que reformulemos la pregunta: ¿qué es lo que quieres aprender de este gráfico? Probablemente llegarás allí aplicando algún algoritmo al gráfico que extrae alguna propiedad subyacente y luego renderizándolo. Te ayuda el hecho de que varios miles de vértices son bastante pequeños en el mundo de las redes (1), por lo que razonablemente puedes esperar ejecutar todo tipo de cosas diferentes.
El resto de esta respuesta menciona solo un par de cosas que es posible que desee buscar. Hay libros completos y series de conferencias relacionadas con diferentes cosas que podría hacer, mucho más de lo que puedo cubrir en una respuesta, por lo que si no ve lo que necesita, le recomiendo hacer más preguntas y buscar imágenes del “gráfico”. visualización “y seleccionando ejemplos que te hablan. (2)
Si desea buscar una estructura simple que explique el conjunto, mire los métodos de engrosamiento de gráficos y la descomposición de k-core. Estos calcularán gráficos más pequeños que (con suerte) son representativos del más grande. El problema es que hay que tener mucho cuidado al afirmar que el gráfico más pequeño representa el más grande.
Si desea encontrar grupos de nodos estrechamente conectados dentro del gráfico, observe la detección de la comunidad. La centralidad (un concepto relacionado) puede ayudarlo a encontrar los nodos a través de los cuales pasa todo.
También puede ejecutar un algoritmo de reordenamiento de matriz (para minimizar el ancho de banda) en la matriz de adyacencia de su gráfico, luego trazar el resultado. Eso puede darle una idea aproximada de dónde están los grupos de nodos conectados e incluso los puentes entre ellos.
Si realmente, sin excusas, DEBE dibujar el gráfico completo, entregarlo a un algoritmo de diseño multinivel y esperar lo mejor.
Una vez que tenga la información que desea, todavía tiene la pregunta de cómo representarla. Si terminas con un gráfico de aproximadamente 500 nodos o menos, usa la herramienta que quieras, personalmente me gusta Gephi, pero elige lo que quieras.
Si ha calculado alguna propiedad sobre los nodos (como la pertenencia a la comunidad), codifique por color los nodos.
Si ha calculado una estructura más pequeña pero todavía quiere mostrar todo, use un algoritmo que presente primero la estructura central y luego decore con el resto del gráfico original.
En pocas palabras: no espere darle sentido al gráfico con solo representarlo. Encuentra algo que te interese y renderiza * eso *. ¡Sigue haciendo preguntas! Hay mucho que aprender aquí.
——-
Nota 1: Los gráficos realmente grandes en el sentido computacional tienen miles de millones de nodos y miles de millones de bordes. Piense en todo el gráfico social de Facebook, por ejemplo, o el gráfico de enlaces de la Web. Esto no quiere decir que su gráfico no sea grande, eso depende mucho de dónde proviene, solo que es lo suficientemente pequeño como para que una sola computadora pueda discutirlo.
Nota al pie 2: una vez que encuentre una visualización gráfica que lo inspire, observe cuidadosamente lo que le muestra. Pregúntese si eso se aplica a su gráfico. Si es así, ¡corre con él!
