15.3: Construyendo modelos de red con NetworkX
- Page ID
- 115855
Ahora que hemos terminado el curso choque anterior sobre terminologías teóricas gráficas, es momento de comenzar con el modelado computacional de redes. Como se previó briefly en las Secciones 5.4 y 12.2, hay un maravilloso módulo Python llamado NetworkX [27] para el modelado y análisis de redes. Es un kit de herramientas gratuito de análisis de redes ampliamente utilizado por los investigadores de la red. Si está utilizando Anaconda, NetworkX ya está instalado. Si está utilizando Enthought Canopy, aún puede instalar NetworkX fácilmente usando su Gestor de Paquetes. Puede encontrar la documentación de NetworkX en línea en http://networkx.github.io.
Quizás valga la pena mencionar por qué estamos eligiendo NetworkX sobre otras opciones. Primero, sus funciones están todas escritas en Python, y sus códigos fuente están todos disponibles en el sitio web anterior, por lo que puedes verificar los detalles de sus algoritmos e incluso modificar los códigos si quieres. En segundo lugar, NetworkX utiliza los “diccionarios” simples de Python para almacenar información sobre redes, que son completamente accesibles y flexible para almacenar información adicional que desea agregar. Esta propiedad es particularmente importante cuando implementamos modelos de simulación de redes dinámicas. Las estructuras de datos especializadas implementadas en otras herramientas de análisis de redes pueden no tener esta exibilidad.
Entonces, hablemos primero de la estructura de datos utilizada en NetworkX. Existen los siguientes cuatro tipos de datos diferentes (llamados “clases”) que ofrece NetworkX:
Graph Para gráficas simples no dirigidas (se permiten auto-bucles)
DiGraph Para gráficos simples dirigidos (se permiten auto-bucles)
MultiGraph Para multígrafos no dirigidos (se permiten autobucles y múltiples bordes)
MultiDigraph Para multígrafos dirigidos (se permiten autobucles y múltiples bordes)
Puede elegir uno de estos cuatro tipos de datos que se adapte a sus propósitos de modelado. En este libro de texto, utilizaremos Graph y DiGraph principalmente.
Puedes construir una gráfica propia manualmente. Aquí hay un ejemplo:
Aquí utilicé cadenas para los nombres de los nodos, pero el nombre de un nodo puede ser un número, una cadena, una lista o cualquier objeto “hashable” en Python. Por ejemplo, en el código de visualización del espacio de fase en la Sección 5.4, se utilizó una tupla para un nombre de cada nodo.
Creo que cada comando usado anteriormente para agregar o eliminar nodos/bordes es bastante autoexplicativo. Si no, siempre puede consultar la documentación en línea de NetworkX para obtener más información sobre cómo funciona cada comando. También hay varias otras formas de manipular un objeto gráfico, que no se detallan aquí.
Una vez que se ejecuta este código, puedes ver los resultados en la línea de comandos de Python, así:
La primera salida (“< networkx.classes.... >”) muestra que g es un objeto Graph. Para poder ver el contenido de los datos en el objeto, necesitamos usar algunos comandos. g.nodes () devuelve una lista de todos los nodos de la red, mientras que g.edges () devuelve una lista de todos los bordes. Compara estos resultados con los comandos que usamos anteriormente para verificar si las adiciones/remociones de nodo/borde se realizaron correctamente.
Esos nodos () y bordes () son funciones que leen los datos brutos dentro del objeto Graph g y luego producen una lista limpia de nodos o aristas. Pero NetworkX también le permite tener acceso directo a la estructura interna de datos brutos del objeto Graph. Los datos sobre los nodos se almacenan en un diccionario llamado nodo justo debajo de g:
Se trata de un diccionario cuyas claves y valores son los nombres de los nodos y sus propiedades, respectivamente. Las propiedades de cada nodo también se almacenan en un diccionario (inicialmente todas están vacías, como se muestra arriba), por lo que puedes agregar o modificar dinámicamente cualquier propiedad de nodo de la siguiente manera:
Utilizaremos este método para agregar estados dinámicos a los nodos en la Sección 16.2.
Del mismo modo, los datos sobre los bordes también se almacenan en un diccionario llamado edge bajo g:
Esto es un poco difícil de leer, así que permítanme insertar saltos de línea en los lugares apropiados para que la estructura de los datos sea más clara:
Ahora su estructura es mucho más clara. g.edge es un diccionario que describe los bordes en la red en el formato de lista de adyacencia. Cada entrada de g.edge es un par del nombre del nodo y un diccionario que contiene sus vecinos. Por ejemplo, la primera entrada dice que Jeff está conectado con Jane y Jill. Tenga en cuenta que las conexiones son perfectamente simétricas; si Jeff está conectado a Jane, entonces la entrada para Jane (en la última línea) también contiene a Jeff como su vecino. Dicha simetría es mantenida automáticamente por NetworkX, debido a que este objeto Graph es para gráficas no dirigidas.
Además, el nombre de cada vecino funciona como una clave asociada a otro diccionario en el que podemos almacenar propiedades de la conexión (inicialmente están todas vacías, como se muestra arriba). Por lo tanto, puede agregar o modificar dinámicamente cualquier propiedad de borde de la siguiente manera:
Nuevamente, la salida es reformateada para mejorar la legibilidad. Tenga en cuenta que las nuevas propiedades de borde ('confianza' entre Jeff y Jane; 'amor' entre Josh y Jess) se insertan correctamente en los diccionarios respectivos, manteniendo siempre la simetría entre nodos. Acabo de agregar True 'love' de Josh a Jess, que ha sido correspondido de Jess a Josh! Qué mundo tan hermoso. Todo esto es porque estamos usando un objeto Graph.
El objeto DiGraph se comporta de manera diferente. Está diseñado para representar gráficas dirigidas, por lo que todos los bordes se consideran unidireccionales. Las simetrías no se mantienen automáticamente, como se ilustra en el siguiente ejemplo:
El último mensaje de error significa que Jess no conoce a un tipo llamado Josh en este caso, porque la gráfica es asimétrica. La vida es dura.
Representar la red mostrada en el Ejercicio 15.1 como un objeto Graph de NetworkX.
Representa una pequeña red social a tu alrededor (digamos, 10 personas) como objeto Graph o DiGraph de NetworkX. A continuación, agregue propiedades a nodos y aristas, como:
• Propiedades del nodo: nombre completo, edad, trabajo, dirección, etc.
• Propiedades de borde: relación, peso de conexión, etc.
En los ejemplos anteriores, construimos manualmente modelos de red agregando o eliminando nodos y bordes. Pero NetworkX también tiene algunas funciones incorporadas que pueden generar redes de formas específicas con mayor facilidad. Aquí hay algunos ejemplos:
El último ejemplo (gráfico de Zachary Karate Club) es un famoso ejemplo clásico de redes sociales reportado por Wayne Zachary en la década de 1970 [59]. Se trata de una red de amistades entre 34 miembros de un club de karate en una universidad estadounidense. Las listas de borde de estos ejemplos son las siguientes:
Construye una gráfica generando una gráfica completa compuesta por 10 nodos, y luego conecta un nuevo nodo adicional a cada uno de los 10 nodos, usando un borde cada uno.
Crea el gráfico de Karate Club de Zachary usando la función incorporada de NetworkX e inspecciona sus nodos y bordes para ver si tienen propiedades no topológicas.