Graph algorithms

Introduction to Network Analysis in Python

Eric Ma

Data Carpentry instructor and author of nxviz package

Finding paths

• Pathfinding is important for
  • Optimization: e.g. shortest transport paths
  • Modeling: e.g. disease spread, information passing
• Algorithm: Breadth-first search

Breadth-first search (BFS)

• Example: Shortest path between two nodes

Breadth-first search (BFS)

• Example: Shortest path between two nodes

Breadth-first search (BFS)

• Example: Shortest path between two nodes

Breadth-first search (BFS)

• Example: Shortest path between two nodes

Recall: Neighbors

G

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

len(G.edges())

57

len(G.nodes())

20

Recall: Neighbors

list(G.neighbors(1))

[10, 5, 14, 7]

list(G.neighbors(10))

[1, 19, 5, 17, 8, 9, 13, 14]

Let's practice!

Introduction to Network Analysis in Python