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

Question

Necesito ser capaz de 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 el más eficiente, en términos de memoria y velocidad, forma de hacer esto?

A dicto de dicts es más flexible y más simple de implementar, pero intuitivamente espero que una lista de listas sea más rápida. La opción de la lista también requeriría que guardo los datos de separarse de la estructura, mientras que predice permitirían algo por el estilo:

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

¿Qué sugieres?

---

Sí, debería haber sido un poco más claro en lo que quiero decir 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 visita los nodos para que pueda extraer la información y medir las métricas que me interesan.

No había considerado convertir cada nodo en una clase (las propiedades son las mismas para todos los nodos) pero parece ¿Así 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.

Answer 1

Yo recomendaría encarecidamente que vea NetworkX. Es un caballo de batalla probado en la batalla y la primera herramienta a la que recurren la mayoría de los tipos de "investigación" cuando necesitan analizar los datos basados ​​en la red. He manipulado gráficos con cientos de miles de bordes sin problemas en una computadora portátil. Su característica rica y muy fácil de usar. Se encontrará enfocándose más en el problema en cuestión que en los detalles en la implementación subyacente.

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

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

Visualizations también son sencillos:

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

Answer 2

Un diccionario también puede contener gastos generales, dependiendo de la implementación real. Por lo general, una tabla hash contiene un número primo de nodos disponibles para empezar, aunque solo use 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?

Yo diría que lo que significa "eficiente" depende de muchas cosas, como:

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

creo que usted encontrará que una estructura de datos que es rápida, generalmente, c consume más memoria que una que es lenta. Este no es siempre el caso, pero la mayoría de las estructuras de datos parece seguir esto.

Un diccionario puede ser fácil de usar y proporcionarle un acceso relativamente uniformemente rápido, lo más probable es que use más memoria de la que, como sugiere, enumera. Las listas, sin embargo, generalmente tienden a contener más sobrecarga al insertar datos en ella, a menos que preasignen los nodos X, en los que volverán a usar más memoria.

Mi sugerencia, en general, sería simplemente utilizar el método que parezca más natural para usted, y luego hacer una "prueba de estrés" del sistema, agregarle una cantidad sustancial de datos y ver si se convierte un problema.

También podría considerar agregar una capa de abstracción a su sistema, para que no tenga que cambiar la interfaz de programación si posteriormente necesita cambiar la estructura interna de datos.

Answer 3

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

Answer 4

Según tengo entendido, el acceso aleatorio es en tiempo constante tanto para los dictados como para las listas de Python, la diferencia es que solo se puede hacer un acceso aleatorio de índices enteros con listas. Supongo que necesita buscar un nodo por su etiqueta, por lo que quiere un dictado de dicts.

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

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

Answer 5

Como ya se mencionó, NetworkX es muy ir od, con otra opción siendo 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.

Answer 6

Aunque esta pregunta ahora 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 metaprogramación de plantillas, usando Boost Graph Library. 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 órdenes de magnitud mejores que el código python típico, sin sacrificar la facilidad de uso. Lo uso constantemente para trabajar con gráficos muy grandes.

Answer 7

Sin duda, NetworkX es la mejor estructura de datos hasta ahora para el gráfico. Viene con utilidades como funciones auxiliares, estructuras de datos y algoritmos, generadores de secuencias aleatorias, decoradores, pedidos de Cuthill-Mckee, administradores de contexto

NetworkX es excelente porque funciona para gráficos, dígrafos y multigrafos. Puede escribir gráficos de varias maneras: Lista de adyacencia, Lista de adyacencia de líneas múltiples, Lista de bordes, GEXF, GML. Funciona con Pickle, GraphML, JSON, SparseGraph6, etc.

Tiene implimentation de diversos algoritmos radimade incluyendo: aproximación, bipartito, Límite, Centralidad, Camarilla, Clustering, colorear, Componentes, Conectividad, Ciclos, Dirigido acíclicos gráficos, medidas de distancias, conjunto dominante, Euler, el isomorfismo, Enlace Análisis, Predicción de enlace, Coincidencia, Árbol de expansión mínimo, Club rico, Trayectos más cortos, Recorrido, Árbol.