Análisis de redes con Python y NetworkX
Más sobre ciencia de datos: cienciadedatos.net
Introducción¶
Bienvenido a este artículo sobre el análisis de redes con Python. El análisis de redes, también conocido como ciencia de redes o teoría de grafos, es el estudio de sistemas complejos compuestos por entidades interconectadas. Con el auge del big data, el análisis de redes ha cobrado cada vez más importancia en diversos campos, como las ciencias sociales, la biología, las finanzas y la informática. Este artículo introduce, mediante de un ejemplo, los conceptos básicos del análisis de redes y su visualización. Se muestra cómo crear y manipular redes, medir sus propiedades y descubrir comunidades y patrones.
🖉 Nota
A continuación, se presenta una selección de los análisis más comunes que se realizan al trabajar con redes. Para obtener una comprensión más detallada de las técnicas utilizadas, se recomienda consultar Introducción a grafos y redes con Python . Este recurso proporciona una visión más exhaustiva y permite explorar en profundidad las técnicas y conceptos relacionados con grafos y redes en Python.Librerías¶
Librerías utilizadas en este documento.
# Librerías
# ======================================================================================
import networkx as nx
import netwulf as nw
import networkx.algorithms.community as nx_comm
import pandas as pd
import numpy as np
from sklearn.preprocessing import MinMaxScaler
import matplotlib.pyplot as plt
import matplotlib as mpl
from matplotlib.lines import Line2D
import matplotlib.colors as mcolors
import itertools
Datos¶
El conjunto de datos del club de karate de Zachary (Zachary's karate club) es un famoso conjunto de datos en el campo de la sociología y la ciencia de redes. Fue recopilado por el sociólogo Wayne W. Zachary mientras estudiaba la estructura social de un club de karate en una universidad estadounidense (1970 - 1972).
El conjunto de datos consta de 34 nodos que representan a los miembros del club y 78 ejes que representan las relaciones entre ellos registradas fuera del club. Durante el estudio surgió un conflicto entre el administrador "John A" (nodo 1) y el instructor "Sr. Hi" (nodo 34), que llevó a la división del club en dos. La mitad de los miembros formaron un nuevo club en torno al Sr. Hi; los miembros de la otra parte encontraron un nuevo instructor o abandonaron el kárate.
Este data set se ha convertido en un ejemplo clásico en la teoría de redes sociales debido a su simplicidad y a la claridad de su estructura, lo que lo convierte en un conjunto de datos ideal para enseñar y aprender los conceptos básicos del análisis de redes (identificación de comunidades y subgrupos, la centralidad y la importancia de los nodos, la dinámica de grupo...)
Si bien esta red se puede cargar directamente con networkx, se muestra cómo crear una red a partir de un csv con la información de las conexiones y otro con las características de cada nodo.
# Datos
# ======================================================================================
network = pd.read_csv(
'https://raw.githubusercontent.com/JoaquinAmatRodrigo/Estadistica-machine-learning-python/'
'master/data/network_zachary_karate.csv'
)
nodes_info = pd.read_csv(
'https://raw.githubusercontent.com/JoaquinAmatRodrigo/Estadistica-machine-learning-python/'
'master/data/node_attributes_zachary_karate.csv'
)
# Conexion de nodos
network.head(3)
# Información de nodos
nodes_info.head(3)
Creación de la red¶
Una vez que los datos han sido almacenados en DataFrame de pandas, se crea la red utilizando la función nx.from_pandas_edgelist.
# Creación de la red
# ======================================================================================
G = nx.from_pandas_edgelist(
df = network,
source = 'from',
target = 'to',
edge_attr = ['weight']
)
print(G)
Es posible añadir información (atributos) sobre cada nodo mediante un diccionario en el que la clave es el identificador del nodo y el valor el atributo de interés.
# Añadir atributos a los nodos
# ======================================================================================
nodes_attributes = nodes_info.set_index('id').to_dict('index')
nx.set_node_attributes(G, nodes_attributes)
Para acceder a la información asociada a cada nodo de la red se utiliza el método nodes(data=True).
# Mostrar la información de cada nodo
# ======================================================================================
dict(G.nodes(data=True))
# Acceder a la información de un nodo especifico (en este caso el nodo con id=1)
# ======================================================================================
G.nodes(data=True)[1]
Exploración gráfica¶
Una parte fundamental del análisis de redes es la exploración gráfica. Este proceso se vuelve más difícil a medida que la red aumenta de tamaño, sin embargo, en este ejemplo, la cantidad de nodos y conexiones es suficientemente pequeña para poder utilizar gráficos sencillos basados en matplotlib.
# Gráfico de la red
# ======================================================================================
fig, ax = plt.subplots(figsize=(8, 5))
nx.draw_spring(G, with_labels=True, ax=ax)
ax.set_title("Karate network");
Para poder sacar máximo partido al análisis visual de una red, es conveniente ajustar algunos elementos como el color y tamaño de los nodos y conexiones. En el siguiente gráfico se ajusta el tamaño de cada nodo en función del número de conexiones (grado) que tiene, el grosor de las conexiones en función de su peso (número de interacciones entre los dos sujetos) y se colorean por el grupo al que pertenecen.
# Gráfico de la red con información de los nodos
# ======================================================================================
fig, ax = plt.subplots(figsize=(9, 7))
# Posición de los nodos
pos = nx.spring_layout(G)
# Estetica de los enlaces
edges_width = list(nx.get_edge_attributes(G, 'weight').values())
edges_alpha = 0.1 + np.array(edges_width)/np.linalg.norm(np.array(edges_width), ord=2)
edge_colors = []
for u, v in G.edges():
group_u = nx.get_node_attributes(G, 'group')[u]
group_v = nx.get_node_attributes(G, 'group')[v]
if group_u != group_v:
edge_colors.append('blue')
elif group_u == "a":
edge_colors.append('orangered')
else:
edge_colors.append('slategrey')
# Estetica de los nodos
nodes_size = [150 * G.degree[node] for node in G.nodes()]
nodes_groups = list(nx.get_node_attributes(G, 'group').values())
nodes_color = ['orangered' if group == 'a' else 'slategrey' for group in nodes_groups]
# Legenda
custom_lines = [Line2D([0], [0], color='blue', alpha=0.5, lw=4),
Line2D([0], [0], color='orangered', alpha=0.5, lw=4),
Line2D([0], [0], color='slategrey', alpha=0.5, lw=4)]
ax.legend(custom_lines, ['Conexiones entre grupos', 'Miembros de A', 'Miembros de B'])
nx.draw_networkx_nodes(G, pos=pos, node_size=nodes_size, node_color=nodes_color, ax=ax)
nx.draw_networkx_labels(G, pos=pos, ax=ax)
nx.draw_networkx_edges(G, pos=pos, edgelist=G.edges, width=edges_width,
edge_color=edge_colors, alpha=edges_alpha, ax=ax);
Netwulf permite crear visualizaciones interactivas a partir de una red network. Con la función visualize se abre automáticamente una ventana del explorador donde puede editarse el gráfico de la red. Una vez que se tiene la visualización deseada, con el boton Post to Python se envía la información de vuelta a la sesión de python y se cierra el explorador.
⚠ Warning
El kernel de python se mantiene ocupado hasta que se presione Post to Python.Netwulf reconoce los atributos de nodo group y size, y el atributo de enlace weight. Si group no es un color (como "rojo" o "#4fba21") los colores de grupo se asignan aleatoriamente.
# Representación interactiva de la red con netwulf
# ======================================================================================
# Sobreescribir el valor de atributo 'group' con el color de los nodos
for k, v in G.nodes(data=True):
if v['group'] == 'a':
v['group'] = 'red'
else:
v['group'] = 'green'
grafico_red, config = nw.visualize(G)
El gráfico devuelto por nw.visualize puede ser representado utilizando matplotlib.
# Representación estática del gráfico devuelto por netwulf
# ======================================================================================
fig, ax = plt.subplots(figsize=(8, 5))
nw.draw_netwulf(grafico_red, fig=fig, ax=ax)
plt.show()
Para información más detallada sobre las funcionalidades de netwulf, consultar la documentación oficial.
Detección de vecinos (neighbors)¶
La detección de vecinos es una tarea frecuente en el análisis de grafos, y la librería NetworkX en Python ofrece fincionalidades que simplifican enormemente la identificación del vecindario de un nodo.
Para detectar los vecinos de un nodo específico, se puede utilizar la función neighbors() que devuelve un iterador sobre los nodos que son adyacentes al nodo especificado.
# Vecinos de orden 1 del nodo con id=1
# ======================================================================================
node = 1
neighbors = list(nx.neighbors(G, node))
print(neighbors)
Para detectar vecinos de un orden específico (n) se puede utilizar la función ego_graph(). Esta función devuelve el subgrafo inducido por los vecinos de un nodo dado hasta un orden especificado. Para grafos dirigidos D esto produce el vecindario de "salida" o sucesores. Si desea el vecindario de los predecesores, primero se tiene que invertir el grafo con D.reverse(). Si se desea ambas direcciones se tiene que indicar el argumento undirected=True.
# Vecinos de orden 2 del nodo con id=1
# ======================================================================================
node = 1
order = 2
ego = nx.ego_graph(G, node, radius=order)
neighbors = list(ego.nodes())
print(neighbors)
Análisis de centralidad¶
El análisis de centralidad es un conjunto de métodos utilizados en el análisis de redes para determinar la importancia o influencia relativa de los nodos de una red. La idea básica que subyace al análisis de centralidad es que determinados nodos de una red son más centrales que otros y, por tanto, tienen un mayor impacto en la estructura y la dinámica de la red.
Existen varios tipos de medidas de centralidad que pueden utilizarse para evaluar la importancia de los nodos de una red. Algunas de las más comunes son: la centralidad de grado, la centralidad de interrelación, la centralidad de proximidad y la centralidad de vector propio. En el siguiente apartado se describen brevemente y se muestra cómo calcularlas con networkx.
Grado (Degree)¶
El grado (degree) es una medida sencilla que se basa en el número de enlaces que tiene un nodo. Acorde a esta métrica, los nodos con un alto grado de centralidad son los que están conectados directamente a muchos otros nodos de la red.
# Degree de cada nodo
# ======================================================================================
degree = dict(nx.degree(G))
degree
Para una red dirigida, existen distintas nociones de grado en función de si se consideran las conexiones de salida o entrada de un nodo. Se denominan grado de salida (out-degree) y grado de entrada (in-degree), donde el grado de salida es el número conexiones de salida de un nodo, y el grado de entrada el número de conexiones de entrada.
Eigenvector¶
La centralidad basada en eigenvectors, también conocida como eigencentrality o prestige score es una medida que tiene en cuenta, no sólo el número de conexiones que tiene un nodo, sino también la importancia de los nodos a los que se conectan. Es decir, los nodos se consideran más importantes si están conectados a nodos que, a su vez, son importantes.
# Eigenvector de cada nodo
# ======================================================================================
eigenvector = nx.eigenvector_centrality(G)
eigenvector
PageRank¶
La métrica de PageRank está basada en el concepto de paseo aleatorio (random walks). Acorde a esta métrica, la importancia de un nodo es proporcional a la probabilidad límite de llegar a ducho nodo si se navega de forma aleatoria por la red.
# Pagerank de cada nodo
# ======================================================================================
pagerank = nx.pagerank(G, max_iter=100)
pagerank
Betweenness¶
El betweenness centrality de un nodo o enlace se define como el número de caminos más cortos del grafo que pasan por él dividido por el número total de caminos más cortos. Aquellos nodos y enlaces con alta centralidad pueden tener una influencia considerable dentro de una red por la cantidad de información que pasa por ellos.
# Betweenness de cada nodo
# ======================================================================================
betweenness = nx.betweenness.betweenness_centrality(G)
betweenness
Comparación metricas de centralidad¶
Son varias las métricas de centralidad que tratan de cuantificar la importancia de los nodos dentro de una red, y no todas ellas tienen por qué coincidir. Por esta razón, es conveniente calcular varias métricas y explorar en qué nodos coinciden y en cuáles no.
# Métricas de centralidad
# ======================================================================================
degree = pd.Series(dict(nx.degree(G)), name='degree')
eigenvector = pd.Series(nx.eigenvector_centrality(G), name='eigenvector')
pagerank = pd.Series(nx.pagerank(G), name='pagerank')
betweenness = pd.Series(nx.betweenness_centrality(G), name='betweenness')
centralidad = pd.concat([degree, eigenvector, pagerank, betweenness], axis=1)
centralidad.index.name = 'node'
centralidad.head(3)
# Top 3 nodos para cada métrica
# ======================================================================================
for col in centralidad.columns:
top_nodos = centralidad[col].sort_values(ascending=False).head(3).index.to_list()
top_nodos.sort()
print(f"Nodos con mayor {col}: {top_nodos}")
La mayoría de las métricas identifican a los nodos 1, 33, 34 como los más importantes.
# Representación del grafo coloreado por cada métrica de centralidad
# ======================================================================================
fig, axs = plt.subplots(1, 4, figsize=(9, 3.5))
# Posición de los nodos
pos = nx.kamada_kawai_layout(G)
# Mapa de colores
cmap = mpl.colormaps['Blues']
# Escalado de las métricas para pooder compararlas
scaler = MinMaxScaler(feature_range=(0, 1))
scaler.fit(centralidad)
centralidad_scaled = pd.DataFrame(
scaler.transform(centralidad),
columns=scaler.feature_names_in_
)
centralidad_scaled.head(3)
for i, metrica in enumerate(centralidad_scaled.columns):
node_size = 100 * centralidad_scaled[metrica] + 1
node_color = cmap(centralidad_scaled[metrica])
nx.draw_networkx_nodes(
G,
pos=pos,
node_size=node_size,
node_color=node_color,
linewidths=0.5,
edgecolors='black',
ax=axs[i]
)
nx.draw_networkx_edges(G, pos=pos, edgelist=G.edges, alpha=0.3, ax=axs[i])
axs[i].set_title(metrica)
axs[i].axis('off')
Concomponente conexo (connected component)¶
Un connected component de un grafo no dirigido es un conjunto de nodos en el que es posible llegar desde cualquier nodo $i$ de ese conjunto a cualquier otro nodo $j$ de ese mismo conjunto. Un grafo está totalmente conectado si tiene un único componente conectado.
# Identificar los componentes conectados del grafo y ordenarlos de mayor a menor
# ======================================================================================
[len(c) for c in sorted(nx.connected_components(G), key=len, reverse=True)]
En este caso solo hay un componente, que es del mismo tamaño que el grafo. Se trata de un grafo totalmente conectado, es decir, se puede llegar de cualquier nodo a otro.
# Crear una nueva red únicamente con el mayor de los componentes conectados
# ======================================================================================
largest_cc = max(nx.connected_components(G), key=len)
G_largest_cc = G.subgraph(largest_cc).copy()
print(G_largest_cc)
Detección de comunidades¶
Existen dos tipos principales de técnicas de detección de comunidades, aglomerativas y divisorias.
Los métodos aglomerativos generalmente comienzan con una red que contiene solo los nodos de la red original. Las conexiones (enlaces) se agregan una por una, dándole prioridad a las más fuertes sobre las más débiles. La fuerza de las conexiones, o peso, se calcula de manera diferente según la implementación específica del algoritmo.
Por otro lado, los métodos divisorios se basan en el proceso de eliminar enlaces de la red original de forma iterativa. Los enlaces más fuertes se eliminan antes que los más débiles. En cada paso, se repite el cálculo del peso del enlace, ya que el peso de los enlaces restantes cambia después de cada eliminación. Después de un cierto número de pasos, se obtienen agrupaciones de nodos densamente conectados, también conocidas como comunidades.
Dos de los algoritmos más empleados para encontrar comunidades son el algoritmo Girvan-Newman y el algoritmo de Louvain.
Algoritmo de Girvan-Newman¶
El algoritmo de Girvan-Newman se basa en la eliminación iterativa de los enlaces por los que pasa el mayor número de caminos más cortos de la red (mayor métrica de betweenness). Al eliminar enlaces uno a uno, la red se descompone en trozos más pequeños, las llamadas comunidades. El algoritmo Girvan-Newman puede dividirse en cuatro pasos principales:
Calcular la centralidad (betweenness) de cada enlace de la red.
Eliminar el enlace con mayor centralidad. Si todos son iguales, se elige aleatoriamente.
Calcular de nuevo la centralidad de los enlaces restantes.
Repetir los pasos 2-4 hasta que no queden enlaces.
En este ejemplo, se puede ver el aspecto de un grafo al que se asignan pesos a los enlaces en función del número de caminos más cortos que pasan por ellos. En la primera iteración, el algoritmo Girvan-Newman elimina el enlace entre los nodos C y D porque es el que tiene mayor peso.
El proceso se repite hasta que todos los nodos quedan aislados, no hay conexiones en la red.
El algoritmo de Girvan-Newman está disponible en la función girvan_newman() de la librería networkx. Esta función tiene 2 argumentos:
G: un grafo de networkx.most_valuable_edge: una función que recibe como input un grafo y devuelve un enlace. El enlace devuelto es eliminado de la red en cada iteración del algoritmo. Por defecto, se utiliza el enlace con mayornetworkx.edge_betweenness_centrality().
El resultado devuelto por la función es un generador. En cada iteración se obtiene una tupla de sets, donde cada set contiene los nodos que forman cada comunidad.
# Algoritmo Girvan-Newman
# ======================================================================================
communities_generator = nx_comm.girvan_newman(G, most_valuable_edge=None)
# Comunidades tras la primera iteración del algoritmo
# ======================================================================================
communities = next(communities_generator)
communities
Se pueden obtener los resultados de las n primeras iteraciones del algoritmo utilizando itertools.islice.
# Comunidades tras las 3 primeras iteraciones del algoritmo
# ======================================================================================
communities_generator = nx_comm.girvan_newman(G, most_valuable_edge=None)
for communities in itertools.islice(communities_generator, 3):
print(communities)
# Acceder a las comunidades generadas en una determinada iteración
# ======================================================================================
iteracion = 0
communities_generator = nx_comm.girvan_newman(G, most_valuable_edge=None)
communities = next(itertools.islice(communities_generator, iteracion, None))
communities
# Gráfico de la red coloreado por comunidades tras 1 iteraciones del algoritmo
# ======================================================================================
communities_generator = nx_comm.girvan_newman(G, most_valuable_edge=None)
communities = next(itertools.islice(communities_generator, 0, None))
color_pallet = list(mcolors.TABLEAU_COLORS.values())
node_colors = []
for node in G:
if node in communities[0]:
node_colors.append(color_pallet[0])
elif node in communities[1]:
node_colors.append(color_pallet[1])
else:
node_colors.append(color_pallet[2])
fig, ax = plt.subplots(figsize=(8, 5))
nx.draw(G, node_color=node_colors, with_labels=True, ax=ax)
plt.show()
Louvain Algorithm¶
El algoritmo de Louvain es uno de los algoritmos más populares y eficientes para detectar comunidades en grafos. Se basa en la idea de maximizar el número de enlaces dentro de una comunidad y minimizar el número de enlaces entre comunidades (optimización de modularidad). Su funcionamiento se divide en dos fases: una fase de agrupamiento y una fase de refinamiento.
Fase de agrupamiento
En la fase de agrupamiento, cada nodo se asigna a su propia comunidad. Luego, se itera sobre cada nodo del grafo y se calcula la ganancia en modularidad que se obtendría al mover el nodo a una comunidad diferente. Si se obtiene una ganancia positiva, se mueve el nodo a la comunidad correspondiente. Esto se repite hasta que ya no se pueden obtener ganancias adicionales.
Fase de refinamiento
La segunda fase consiste en construir una nueva red cuyos nodos son las comunidades encontradas en la primera fase. Los pesos de los enlaces entre los nuevos nodos se calculan sumando del peso de los enlaces entre los nodos de las dos comunidades correspondientes. Al final de esta fase, se obtiene una partición del grafo con comunidades más compactas y mejor definidas que las obtenidas en la fase de agrupamiento.
Las dos fases anteriores se ejecutan hasta que no se obtiene ninguna ganancia de modularidad (o es inferior a un umbral). El resultado final es una partición del grafo en comunidades.
🖉 Nota
Para obtener una comprensión más detallada del algoritmo de louvain, se recomienda consultar Detección de comunidades en grafos y redes con python.# Louvain Algorithm
# ======================================================================================
communities = nx_comm.louvain_communities(G, weight='weight ', resolution=0.5)
communities
Suele ser más útil almacenar los resultados en forma de diccionario donde, cada nodo tiene asociado el identificador de la comunidad a la que pertenece.
communities_map = {}
for i in range(len(communities)):
communities_map.update(dict.fromkeys(communities[i], i))
# Gráfico de la red coloreado por comunidades
# ======================================================================================
color_pallet = list(mcolors.TABLEAU_COLORS.values())
node_colors = []
for node in G:
node_colors.append(color_pallet[communities_map[node]])
fig, ax = plt.subplots(figsize=(8, 5))
nx.draw(G, node_color=node_colors, with_labels=True)
plt.show()
Camino más corto (shortest path)¶
En teoría de grafos, el camino más corto de un grafo es el camino entre dos nodos que tiene la suma mínima de pesos de sus conexiones (aristas). Los pesos de las aristas pueden representar diversos factores, como la distancia, el coste o el tiempo.
Para encontrar el camino más corto en un grafo, se pueden utilizar varios algoritmos, entre los que se incluyen:
Algoritmo de Dijkstra: Este algoritmo funciona para grafos con pesos de arista no negativos y encuentra el camino más corto desde un nodo origen a todos los demás nodos del grafo.
shortest_path(G, smethod='dijkstra')Algoritmo de Bellman-Ford: A diferencia del algoritmo de Dijkstra, este algoritmo puede trabajar con grafos con pesos de arista negativos. Encuentra el camino más corto desde un nodo origen a todos los demás nodos del grafo.
shortest_path(G, smethod='bellman-ford')Algoritmo A (A-star*): Este algoritmo utiliza una función heurística además de los pesos de las aristas para guiar la búsqueda del camino más corto. Se suele utilizar en problemas de búsqueda de caminos, como en los sistemas de navegación GPS.
Algoritmo Floyd. El algoritmo de Floyd es apropiado para encontrar los caminos más cortos en grafos densos o grafos con pesos negativos cuando falla el algoritmo de Dijkstra. Este algoritmo también puede fallar si hay ciclos negativos.
floyd_warshall(G, weight='weight')Algoritmo Johnson. El algoritmo de Johnson es adecuado incluso para grafos con pesos negativos. Funciona utilizando el algoritmo de Bellman-Ford para calcular una transformación del grafo de entrada que elimina todos los pesos negativos, lo que permite utilizar el algoritmo de Dijkstra en el grafo transformado. Se trata por lo tanto de una combinacioón de los los algoritmos de Dijkstra y Bellman-Ford.
johnson(G, weight='weight').
# Camino más corto entre los nodos 17 y 27
# ======================================================================================
shortest_path = nx.shortest_path(G, source=17, target=27, method='dijkstra')
shortest_path
# Resaltar el camino más corto en el grafo
# ======================================================================================
fig, ax = plt.subplots(figsize=(8, 5))
# Crear un subgrafo con los nodos del camino más corto
sub_graph = G.subgraph(shortest_path)
# Posición de los nodos
pos = nx.spring_layout(G)
# Crear un grafo con los nodos del camino más corto en rojo y el resto en gris
nx.draw_networkx_edges(G, pos=pos, edge_color="gray")
nx.draw_networkx_nodes(G, pos=pos, node_color="gray")
nx.draw_networkx_labels(G, pos=pos, labels={node: node for node in G.nodes()})
nx.draw_networkx_edges(sub_graph, pos=pos, edge_color="red")
nx.draw_networkx_nodes(sub_graph, pos=pos, node_color="red")
nx.draw_networkx_labels(sub_graph, pos=pos, labels={node: node for node in shortest_path})
ax.set_title("Camino más corto entre los nodos 17 y 27")
plt.show();
Información de sesión¶
import session_info
session_info.show(html=False)
%%html
¿Cómo citar este documento?
Análisis de redes con Python y NetworkX by Joaquín Amat Rodrigo and Fernando Carazo, available under a CC BY-NC-SA 4.0 at https://www.cienciadedatos.net/documentos/pygml03-analisis-redes-python-networkx.html 
¿Te ha gustado el artículo? Tu ayuda es importante
Mantener un sitio web tiene unos costes elevados, tu contribución me ayudará a seguir generando contenido divulgativo gratuito. ¡Muchísimas gracias! 😊
Este contenido, creado por Fernando Carazo y Joaquín Amat Rodrigo, tiene licencia Attribution-NonCommercial-ShareAlike 4.0 International.