¿Cuál es la estructura de datos de gráficos más eficiente en Python?

Necesito poder manipular un gráfico grande (10 ^ 7 nodos) en python. Los datos correspondientes a cada nodo / borde son mínimos, por ejemplo, un pequeño número de cadenas. ¿Cuál es la forma más eficiente, en términos de memoria y velocidad , de hacer esto?

Un dict de dictados es más flexible y más fácil de implementar, pero intuitivamente espero que una lista de listas sea más rápida. La opción de lista también requeriría que mantuviera los datos separados de la estructura, mientras que los dicts permitirían algo por el estilo

graph[I][J]["Property"]="value" 

¿Qué sugieres?


Sí, debería haber sido un poco más claro a lo que me refiero con eficiencia. En este caso particular, lo digo en términos de recuperación de acceso aleatorio.

Cargar los datos en la memoria no es un gran problema. Eso se hace de una vez por todas. La parte que consume mucho tiempo es visitar los nodos para que pueda extraer la información y medir las métricas que me interesan.

¿No había considerado hacer de cada nodo una clase (las propiedades son las mismas para todos los nodos) pero parece que eso agregaría una capa adicional de sobrecarga? Esperaba que alguien tuviera alguna experiencia directa con un caso similar que pudieran compartir. Después de todo, los gráficos son una de las abstracciones más comunes en CS.

Yo recomendaría encarecidamente que mires NetworkX . Es un caballo de guerra probado en la batalla y la primera herramienta que la mayoría de los tipos de “investigación” buscan cuando necesitan hacer análisis de datos basados ​​en la red. He manipulado gráficos con cientos de miles de bordes sin problemas en una notebook. Su característica es rica y muy fácil de usar. Usted se encontrará enfocándose más en el problema en cuestión que en los detalles de la implementación subyacente.

Ejemplo de generación y análisis de gráficos aleatorios de Erdős-Rényi

 """ Create an G{n,m} random graph with n nodes and m edges and report some properties. This graph is sometimes called the Erd##[m~Qs-Rényi graph but is different from G{n,p} or binomial_graph which is also sometimes called the Erd##[m~Qs-Rényi graph. """ __author__ = """Aric Hagberg (hagberg@lanl.gov)""" __credits__ = """""" # Copyright (C) 2004-2006 by # Aric Hagberg # Dan Schult # Pieter Swart # Distributed under the terms of the GNU Lesser General Public License # http://www.gnu.org/copyleft/lesser.html from networkx import * import sys n=10 # 10 nodes m=20 # 20 edges G=gnm_random_graph(n,m) # some properties print "node degree clustering" for v in nodes(G): print v,degree(G,v),clustering(G,v) # print the adjacency list to terminal write_adjlist(G,sys.stdout) 

Las visualizaciones también son directas:

introduzca la descripción de la imagen aquí

Más visualización: http://jonschull.blogspot.com/2008/08/graph-visualization.html

Aunque esta pregunta ya es bastante antigua, creo que vale la pena mencionar mi propio módulo de Python para la manipulación de gráficos, llamado graph-tool . Es muy eficiente, ya que las estructuras de datos y los algoritmos se implementan en C ++, con metaprogtwigs de plantilla, utilizando la biblioteca de gráficos de Boost. Por lo tanto, su rendimiento (tanto en el uso de la memoria como en el tiempo de ejecución) es comparable a una biblioteca C ++ pura, y puede ser de una magnitud superior a la del código típico de Python, sin sacrificar la facilidad de uso. Yo mismo lo uso constantemente para trabajar con gráficos muy grandes.

Como ya se mencionó, NetworkX es muy bueno, con otra opción que es igraph . Ambos módulos tendrán la mayoría (si no todas) las herramientas de análisis que probablemente necesite, y ambas bibliotecas se usan de forma rutinaria con redes grandes.

Un diccionario también puede contener gastos generales, dependiendo de la implementación real. Para empezar, una tabla hash contiene un número primo de nodos disponibles, aunque es posible que solo uses un par de nodos.

A juzgar por su ejemplo, “Propiedad”, ¿sería mejor con un enfoque de clase para el nivel final y las propiedades reales? ¿O los nombres de las propiedades cambian mucho de un nodo a otro?

Diría que lo que significa “eficiente” depende de muchas cosas, como:

  • velocidad de actualizaciones (insertar, actualizar, eliminar)
  • velocidad de recuperación de acceso aleatorio
  • velocidad de recuperación secuencial
  • memoria usada

Creo que encontrará que una estructura de datos que es rápida generalmente consumirá más memoria que una que es lenta. Este no es siempre el caso, pero la mayoría de las estructuras de datos parecen seguir esto.

Es posible que un diccionario sea fácil de usar y le brinde un acceso relativamente rápido y uniforme; lo más probable es que use más memoria que, como sugiere, las listas. Sin embargo, las listas generalmente tienden a contener más sobrecarga cuando se insertan datos en ella, a menos que se reasignen los nodos X, en los que volverán a usar más memoria.

Mi sugerencia, en general, sería simplemente usar el método que le parezca más natural, y luego realizar una “prueba de esfuerzo” del sistema, agregarle una cantidad sustancial de datos y ver si se convierte en un problema.

También podría considerar agregar una capa de abstracción a su sistema, de modo que no tenga que cambiar la interfaz de progtwigción si más adelante necesita cambiar la estructura de datos interna.

Como lo entiendo, el acceso aleatorio está en tiempo constante tanto para los dictados como para las listas de Python, la diferencia es que solo se puede hacer acceso aleatorio de índices enteros con listas. Supongo que necesita buscar un nodo por su etiqueta, por lo que desea un dictado de dictados.

Sin embargo, en el frente del rendimiento, cargarlo en la memoria puede no ser un problema, pero si usa demasiado, terminará cambiando al disco, lo que matará el rendimiento incluso de los dicts altamente eficientes de Python. Trate de mantener el uso de memoria lo más bajo posible. Además, la memoria RAM es increíblemente barata en este momento; Si haces mucho este tipo de cosas, no hay razón para no tener al menos 4GB.

Si desea obtener consejos sobre cómo reducir el uso de la memoria, brinde más información sobre el tipo de información que está rastreando para cada nodo.

Hacer una estructura basada en clases probablemente tendría más sobrecarga que la estructura basada en dict, ya que en las clases de python realmente usan dicts cuando se implementan.

Sin duda, NetworkX es la mejor estructura de datos hasta ahora para el gráfico. Viene con utilidades como funciones de ayuda, estructuras de datos y algoritmos, generadores de secuencia aleatoria, decoradores, ordenamiento de Cuthill-Mckee, gestores de contexto.

NetworkX es grandioso porque le encantan los gráficos, dígrafos y multigráficos. Puede escribir gráficos de varias formas: Lista de adyacencia, Lista de adyacencia multilínea, Lista de bordes, GEXF, GML. Funciona con Pickle, GraphML, JSON, SparseGraph6, etc.

Cuenta con la implementación de varios algoritmos de radimade que incluyen: aproximación, bipartito, límite, centralidad, camarilla, agrupación, coloración, componentes, conectividad, ciclos, gráficos acíclicos dirigidos, medidas de distancia, conjuntos dominantes, eulerianos, isomorfismo, análisis de enlaces, predicción de enlaces, comparación , Árbol de expansión mínima, Club rico, Rutas más cortas, Traversal, Árbol.