Graph-Algorithmen

Einstieg in die Netzwerkanalyse mit Python

Eric Ma

Data Carpentry instructor and author of nxviz package

Pfade finden

  • Pfadsuche ist wichtig für
    • Optimierung: z. B. kürzeste Transportwege
    • Modellierung: z. B. Krankheitsausbreitung, Informationsfluss
  • Algorithmus: Breadth-First Search (BFS)
Einstieg in die Netzwerkanalyse mit Python

Breadth-First Search (BFS)

  • Beispiel: Kürzester Pfad zwischen zwei Knoten

Ein Graph mit einem Dutzend Knoten. Zwei indirekt verbundene Knoten sind hervorgehoben.

Einstieg in die Netzwerkanalyse mit Python

Breadth-First Search (BFS)

  • Beispiel: Kürzester Pfad zwischen zwei Knoten

Der gleiche Graph wie zuvor, aber der Nachbarknoten eines der hervorgehobenen Knoten ist ebenfalls hervorgehoben.

Einstieg in die Netzwerkanalyse mit Python

Breadth-First Search (BFS)

  • Beispiel: Kürzester Pfad zwischen zwei Knoten

Der gleiche Graph wie zuvor, aber die Nachbarknoten aller hervorgehobenen Knoten sind ebenfalls hervorgehoben.

Einstieg in die Netzwerkanalyse mit Python

Breadth-First Search (BFS)

  • Beispiel: Kürzester Pfad zwischen zwei Knoten

Der gleiche Graph wie zuvor, aber ein weiterer Satz von Nachbarknoten der vorhandenen hervorgehobenen Knoten ist ebenfalls hervorgehoben, wodurch der Zielknoten erreicht wird.

Einstieg in die Netzwerkanalyse mit Python

Wiederholung: Nachbarn

G

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

len(G.edges())

57

len(G.nodes())

20
Einstieg in die Netzwerkanalyse mit Python

Wiederholung: Nachbarn

list(G.neighbors(1))

[10, 5, 14, 7]

list(G.neighbors(10))

[1, 19, 5, 17, 8, 9, 13, 14]
Einstieg in die Netzwerkanalyse mit Python

Lass uns üben!

Einstieg in die Netzwerkanalyse mit Python

Preparing Video For Download...