Algorithmes de graphes

Introduction à l’analyse de réseaux en Python

Eric Ma

Data Carpentry instructor and author of nxviz package

Trouver des chemins

  • La recherche de chemins sert à
    • Optimisation : p. ex. plus courts trajets
    • Modélisation : p. ex. propagation, diffusion d’infos
  • Algorithme : parcours en largeur (BFS)
Introduction à l’analyse de réseaux en Python

Parcours en largeur (BFS)

  • Exemple : plus court chemin entre deux nœuds

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

Introduction à l’analyse de réseaux en Python

Parcours en largeur (BFS)

  • Exemple : plus court chemin entre deux nœuds

Le même graphe, mais le voisin d’un des nœuds surlignés est aussi mis en évidence.

Introduction à l’analyse de réseaux en Python

Parcours en largeur (BFS)

  • Exemple : plus court chemin entre deux nœuds

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

Introduction à l’analyse de 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 voisins des nœuds surlignés est aussi mis en évidence, ce qui signifie que le nœud cible est atteint.

Introduction à l’analyse de réseaux en Python

Rappel : Voisins

G

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

len(G.edges())

57

len(G.nodes())

20
Introduction à l’analyse de 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 de réseaux en Python

Passons à la pratique !

Introduction à l’analyse de réseaux en Python

Preparing Video For Download...