Grafenalgoritmen

Introductie tot netwerkanalyse in Python

Eric Ma

Data Carpentry instructor and author of nxviz package

Paden vinden

  • Padvinden is belangrijk voor
    • Optimalisatie: bijv. kortste transportpaden
    • Modelleren: bijv. ziektespreiding, informatieoverdracht
  • Algoritme: breadth-first search (BFS)
Introductie tot netwerkanalyse in Python

Breadth-first search (BFS)

  • Voorbeeld: kortste pad tussen twee knopen

Een graaf met een dozijn knopen. Twee indirect verbonden knopen zijn gemarkeerd.

Introductie tot netwerkanalyse in Python

Breadth-first search (BFS)

  • Voorbeeld: kortste pad tussen twee knopen

Dezelfde graaf als zojuist, maar de buur van een van de gemarkeerde knopen is ook gemarkeerd.

Introductie tot netwerkanalyse in Python

Breadth-first search (BFS)

  • Voorbeeld: kortste pad tussen twee knopen

Dezelfde graaf als zojuist, maar de buren van alle gemarkeerde knopen zijn ook gemarkeerd.

Introductie tot netwerkanalyse in Python

Breadth-first search (BFS)

  • Voorbeeld: kortste pad tussen twee knopen

Dezelfde graaf als zojuist, maar nog een set buren van de bestaande gemarkeerde knopen is ook gemarkeerd, waardoor de doelknoop is bereikt.

Introductie tot netwerkanalyse in Python

Herhaling: Buren

G

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

len(G.edges())

57

len(G.nodes())

20
Introductie tot netwerkanalyse in Python

Herhaling: Buren

list(G.neighbors(1))

[10, 5, 14, 7]

list(G.neighbors(10))

[1, 19, 5, 17, 8, 9, 13, 14]
Introductie tot netwerkanalyse in Python

Laten we oefenen!

Introductie tot netwerkanalyse in Python

Preparing Video For Download...