Algorithmes de graphe

Introduction à l'analyse des réseaux en Python

Eric Ma

Data Carpentry instructor and author of nxviz package

Trouver des chemins

  • La recherche de chemin sert à
    • l'optimisation : p. ex. trajets de transport les plus courts
    • la modélisation : p. ex. propagation d'une maladie, diffusion d'information
  • Algorithme : parcours en largeur
Introduction à l'analyse des réseaux en Python

Parcours en largeur (BFS)

  • Exemple : plus court chemin entre deux nœuds

Un graphe d'une douzaine de nœuds. Deux nœuds reliés indirectement sont mis en évidence.

Introduction à l'analyse des réseaux en Python

Parcours en largeur (BFS)

  • Exemple : plus court chemin entre deux nœuds

Le même graphe, mais le nœud voisin de l'un des nœuds en évidence est aussi mis en évidence.

Introduction à l'analyse des réseaux en Python

Parcours en largeur (BFS)

  • Exemple : plus court chemin entre deux nœuds

Le même graphe, mais les nœuds voisins de tous les nœuds en évidence sont aussi mis en évidence.

Introduction à l'analyse des réseaux en Python

Parcours en largeur (BFS)

  • Exemple : plus court chemin entre deux nœuds

Le même graphe, mais un autre ensemble de nœuds voisins des nœuds déjà en évidence est aussi mis en évidence, ce qui signifie que le nœud cible est atteint.

Introduction à l'analyse des réseaux en Python

Rappel : Voisins

G

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

len(G.edges())

57

len(G.nodes())

20
Introduction à l'analyse des réseaux en Python

Rappel : Voisins

list(G.neighbors(1))

[10, 5, 14, 7]

list(G.neighbors(10))

[1, 19, 5, 17, 8, 9, 13, 14]
Introduction à l'analyse des réseaux en Python

Passons à la pratique !

Introduction à l'analyse des réseaux en Python

Preparing Video For Download...