Grafos
(˵Φ ω Φ˵) Están por todas partes, pensás todo el tiempo en grafos una vez que los aprendés
- ¿Qué es un grafo?
- ¿Para qué sirven?
- NetworkX
- Tipos de grafos
- Algoritmos comunes
- Componentes conectadas
- El camino más corto
- Árbol recubridor mínimo
- Pagerank
- Intermediación
- Pandas
- Práctica
Este es el material de una clase que doy en Digital House en el curso de ciencia de datos.
- Red — grafo, graph
- Nodos — vértices, nodes
- Conexiones — aristas, bordes, edges
Es una estructura de datos útil para representar:
- redes sociales
- máquinas de estado
- moléculas
- mapas conceptuales
- estructura del lenguaje
- redes de transporte
- y mucho más...
NetworkX es un paquete de Python para la creación, manipulación, y el estudio de la estructura, dinámica, y las funciones de las redes complejas.
!pip install --upgrade networkx
%matplotlib inline
import networkx as nx
G = nx.Graph()
G.add_node('Buenos Aires')
G.add_node('Córdoba')
G.add_node('Mendoza')
nx.draw(G)
G.add_edge('Buenos Aires', 'Córdoba', distancia=647)
G.add_edge('Buenos Aires', 'Mendoza', distancia=948)
G.add_edge('Córdoba', 'Mendoza', distancia=682)
nx.draw(G)
G.add_edge('Tucumán','Salta', distancia=227)
nx.draw(G)
- Subgrafo: subconjunto de nodos y conexiones.
- Componente conectada: grupo de nodos conectados.
G.nodes
G.edges
G.degree['Mendoza']
pos=nx.planar_layout(G)
# dibujar etiquetas
nx.draw_networkx_labels(G, pos=pos)
# dibujar nodos
nx.draw_networkx_nodes(G, pos=pos)
# dibujar conexiones
nx.draw_networkx_edges(G, pos=pos);
Graficar grafos no es una tarea sencilla y NetworkX lo deja en mano de otras aplicaciones, como Gephi.
Grafo de ejemplo: Familias florentinas
Familias que se disputaron el control político de la ciudad de Florencia alrededor de 1430. Dos facciones fueron dominantes en la disputa: Medicis y Strozzis.
Dataset de uniones maritales y de negocio entre familias.
Fuente: Padgett, J. F., & Ansell, C. K. (1993). Robust Action and the Rise of the Medici, 1400-1434. American Journal of Sociology, 98(6), 1259-1319.
G = nx.florentine_families_graph()
nx.draw_networkx(G)
G.nodes
for sub_graph in nx.connected_components(G):
print(sub_graph)
El camino más corto
https://en.wikipedia.org/wiki/Shortest_path_problem
- Camino: secuencia de nodos conectados.
Aplicaciones
- Google Maps
nx.shortest_path(G, source='Medici', target='Strozzi', weight=None)
Árbol recubridor mínimo
https://en.wikipedia.org/wiki/Minimum_spanning_tree
Aplicaciones
- Tendido de redes
mst = nx.minimum_spanning_tree(G, weight=None)
nx.draw_networkx(mst)
rank = nx.pagerank(G, weight=None)
sorted(rank.items(), key=lambda item: item[1], reverse=True)[:5]
Ejemplo de uso en aprendizaje automático: Red de influencia de inversores.
rank = nx.betweenness_centrality(G, weight=None)
sorted(rank.items(), key=lambda item: item[1], reverse=True)[:5]
nx.algorithms.community.modularity_max.greedy_modularity_communities(G)
Índice Adamic/Adar
https://en.wikipedia.org/wiki/Adamic/Adar_index
Aplicaciones
- Recomendación de contactos
- Recomendación de productos
predicciones = nx.adamic_adar_index(G, ebunch=[('Medici', 'Strozzi'), ('Medici', 'Pazzi')])
for predicción in predicciones:
print(predicción)
import pandas as pd
URL = 'http://cdn.buenosaires.gob.ar/datosabiertos/datasets/bicicletas-publicas/recorridos-realizados-2019.csv'
ARCHIVO = 'muestreo_recorridos.csv.gz'
df = pd.read_csv(ARCHIVO, low_memory=False)
df.info()
df.head()
El DataFrame debe contener al menos dos columnas con nombres de nodos (origen y destino) y cero o más columnas con atributos de las conexiones.
Cada fila se procesa como una conexión.
df['minutos_viaje'] = pd.to_timedelta(df.duracion_recorrido, unit='minute', errors='coerce')
pre_grafo = df.groupby(['nombre_estacion_origen','nombre_estacion_destino']) \
.minutos_viaje \
.mean(numeric_only=False) \
.to_frame() \
.reset_index()
pre_grafo.head()
estaciones = nx.convert_matrix.from_pandas_edgelist(
pre_grafo,
source='nombre_estacion_origen',
target='nombre_estacion_destino',
edge_attr='minutos_viaje',
create_using=nx.MultiDiGraph
)
nx.draw(estaciones)
😱 😱 😱
Ideas
-
https://medium.com/@fcatalano/bicisendas-en-buenos-aires-a29f62bc9e7c — "La red de bicicletas fue diagramada como un grafo dirigido. Esto, porque nos interesaba representar los recorridos realizados respetando el sentido de los viajes."
- Análisis exploratorio del dataset
- Análisis de in-degree y out-degree
-
https://towardsdatascience.com/buenos-aires-bicycle-lanes-ii-1a40b13ccc25 — "[...] we built a graph where two users shared a link if and only if at least one of them had taken a bicycle at approximately the same time from the same station, and returned them together (also to the same station)."
- Distribución grados
- Análisis exploratorio del grafo
-
https://medium.com/@martinpalazzo/buenos-aires-bicycle-lanes-iii-d0ca4539e767 — "The first step to understand the communities of stations is to build a network where each node is a station and each edge between station is the quantity of bicycle journeys."
- Modularidad