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
Introduction to Network Analysis in Python

Breadth-first search (BFS)

  • Example: Shortest path between two nodes

A graph with a dozen nodes. Two nodes that are indirectly connected are highlighted.

Introduction to Network Analysis in Python

Breadth-first search (BFS)

  • Example: Shortest path between two nodes

The same graph as last time, but the neighboring node to one of the highlighted nodes is also highlighted.

Introduction to Network Analysis in Python

Breadth-first search (BFS)

  • Example: Shortest path between two nodes

The same graph as last time, but the neighboring nodes to all the highlighted nodes are also highlighted.

Introduction to Network Analysis in Python

Breadth-first search (BFS)

  • Example: Shortest path between two nodes

The same graph as last time, but another set of neighboring nodes to the existing highlighted nodes are also highlighted, which means that the target node has been reached.

Introduction to Network Analysis in Python

Recall: Neighbors

G
<networkx.classes.graph.Graph at 0x10cc08828>
len(G.edges())
57
len(G.nodes())
20
Introduction to Network Analysis in Python

Recall: Neighbors

list(G.neighbors(1))
[10, 5, 14, 7]
list(G.neighbors(10))
[1, 19, 5, 17, 8, 9, 13, 14]
Introduction to Network Analysis in Python

Let's practice!

Introduction to Network Analysis in Python

Preparing Video For Download...