Algoritmos de grafos

Introducción al análisis de redes en Python

Eric Ma

Data Carpentry instructor and author of nxviz package

Encontrar rutas

  • Encontrar rutas es clave para
    • Optimización: p. ej., rutas de transporte más cortas
    • Modelado: p. ej., propagación de enfermedades, difusión de información
  • Algoritmo: Búsqueda en anchura
Introducción al análisis de redes en Python

Búsqueda en anchura (BFS)

  • Ejemplo: ruta más corta entre dos nodos

Un grafo con una docena de nodos. Dos nodos conectados indirectamente están resaltados.

Introducción al análisis de redes en Python

Búsqueda en anchura (BFS)

  • Ejemplo: ruta más corta entre dos nodos

El mismo grafo de antes, pero el nodo vecino de uno de los nodos resaltados también está resaltado.

Introducción al análisis de redes en Python

Búsqueda en anchura (BFS)

  • Ejemplo: ruta más corta entre dos nodos

El mismo grafo de antes, pero los nodos vecinos de todos los nodos resaltados también están resaltados.

Introducción al análisis de redes en Python

Búsqueda en anchura (BFS)

  • Ejemplo: ruta más corta entre dos nodos

El mismo grafo de antes, pero otro conjunto de nodos vecinos de los ya resaltados también está resaltado, lo que indica que se alcanzó el nodo objetivo.

Introducción al análisis de redes en Python

Recuerda: Vecinos

G

<networkx.classes.graph.Graph at 0x10cc08828>

len(G.edges())

57

len(G.nodes())

20
Introducción al análisis de redes en Python

Recuerda: Vecinos

list(G.neighbors(1))

[10, 5, 14, 7]

list(G.neighbors(10))

[1, 19, 5, 17, 8, 9, 13, 14]
Introducción al análisis de redes en Python

¡Vamos a practicar!

Introducción al análisis de redes en Python

Preparing Video For Download...